Suma de rango y actualización en array: árbol de segmentos usando pila

Dada una array arr[] de N enteros. La tarea es hacer las siguientes operaciones: 
 

1. Agregue un valor X a todo el elemento del índice A al B donde 0 ≤ A ≤ B ≤ N-1 .
2. Encuentre la suma del elemento del índice L a R donde 0 ≤ L ≤ R ≤ N-1 antes y después de la actualización dada a la array anterior.

Ejemplo: 
 

Entrada: arr[] = {1, 3, 5, 7, 9, 11}, L = 1, R = 3, A = 1, B = 5, X = 10 
Salida: 
Suma de valores en el rango dado = 15 
Actualizado suma de valores en el rango dado = 45 
Explicación: 
La suma de valores en el rango 1 a 3 es 3 + 5 + 7 = 15. 
arr[] después de sumar 10 del índice 1 a 5 es arr[] = {1, 13, 15 , 17, 19, 21} 
La suma de los valores en el rango de 1 a 3 después de la actualización es 13 + 15 + 17 = 45.
Entrada: arr[] = { 11, 32, 5, 7, 19, 11, 8}, L = 2, R = 6, A = 1, B = 5, X = 16 
Salida: 
Suma de valores en el rango dado = 50 
Suma actualizada de valores en el rango dado = 114 
Explicación: 
La suma de los valores en el rango de 2 a 6 es 5 + 7 + 19 + 11 + 8 = 50. 
arr[] después de sumar 16 del índice 1 a 5 es arr[] = {11, 48, 21, 23, 35, 27 , 8} 
La suma de los valores en el rango de 2 a 6 después de la actualización es 21 + 23 + 35 + 27 + 8 = 114. 
 

Enfoque: En  este artículo se analiza el
enfoque recursivo que utiliza un árbol de segmentos para el problema dado. En esta publicación, analizaremos un enfoque que utiliza la estructura de datos de pila para evitar la recursividad . A continuación se muestran los pasos para implementar Segment Tree usando Stack : 

 

1. La idea es usar tupla para almacenar el estado que tiene el número de Node y los índices de rango en la Pila .
2. Para el árbol de segmento de construcción : 
   • Empuje el Node raíz a la pila como una tupla: 
      

Stack S;
start = 0, end = arr_size - 1
S.emplace(1, start, end)

•  
• Extraiga el elemento de la pila y haga lo siguiente hasta que la pila quede vacía: 
  1. Si el índice inicial es igual al índice final, entonces llegamos al Node hoja y actualizamos el valor en la array del árbol de segmentos como valor en el índice actual en la array dada.
  2. De lo contrario, inserte la tupla de bandera con el Node actual como S.emplace (current_node, INF, INF) para invertir el orden de evaluación e inserte la tupla con valor para el hijo izquierdo y derecho como: 
      

mid = (start + end) / 2 
st.emplace(curr_node * 2, start, mid) 
st.emplace(curr_node * 2 + 1, mid + 1, end) 
 

1.  
2. Si el índice inicial y el índice final son los mismos que INF , actualice el valor del árbol de segmentos en el índice actual como: 
    

El valor en el índice actual se actualiza como valor en el hijo izquierdo y el hijo derecho: 
árbol[curr_node] = árbol[2*curr_node] + árbol[2*curr_node + 1] 
 

1.  
2. Para el árbol de actualización : 
   • Empuje el Node raíz a la pila como se hizo para construir Segment Tree .
   • Extraiga el elemento de la pila y haga lo siguiente hasta que la pila quede vacía: 
     1. Si el Node actual tiene alguna actualización pendiente, primero actualice al Node actual.
     2. Si los rangos del Node actual se encuentran completamente en el rango de consulta de actualización, actualice el Node actual con ese valor.
     3. Si los rangos de Nodes actuales se superponen con el rango de consulta de actualización, siga el enfoque anterior y empuje la tupla para el niño izquierdo y el niño derecho en la pila .
     4. Actualice la consulta utilizando el resultado del niño izquierdo y derecho anterior.
3. Para la consulta de actualización : 
   • Empuje el Node raíz a la pila como se hizo para construir Segment Tree .
   • Extraiga el elemento de la pila y haga lo siguiente hasta que la pila quede vacía: 
     1. Si los rangos de Nodes actuales se encuentran fuera de la consulta dada, continúe con la siguiente iteración.
     2. Si los rangos de Nodes actuales se encuentran completamente en el rango de consulta de actualización, actualice el resultado con el valor de Node actual.
     3. Si los rangos de Nodes actuales se superponen con el rango de consulta de actualización, siga el enfoque anterior y empuje la tupla para el niño izquierdo y el niño derecho en la pila .
     4. Actualice el resultado utilizando el valor obtenido del Node secundario izquierdo y derecho.

A continuación se muestra la implementación del enfoque anterior:
 

#include"bits/stdc++.h"
using namespace std;
  
constexpr static int MAXSIZE = 1000;
constexpr static int INF
    = numeric_limits<int>::max();
  
// Segment Tree array
int64_t tree[MAXSIZE];
  
// Lazy Update array
int64_t lazy[MAXSIZE];
  
// This tuple will hold tree state
// the stacks
using QueryAdaptor
    = tuple<int64_t,
            int64_t,
            int64_t>;
  
// Build our segment tree
void build_tree(int64_t* arr,
                int64_t arr_size)
{
    
    // Stack will use to update
    // the tree value
    stack<QueryAdaptor> st;
  
    // Emplace the root of the tree
    st.emplace(1, 0, arr_size - 1);
  
    // Repeat until empty
    while (!st.empty()) {
  
        // Take the indexes at the
        // top of the stack
        int64_t currnode, curra, currb;
  
        // value at the top of the
        // stack
        tie(currnode, curra, currb) = st.top();
  
        // Pop the value from the
        // stack
        st.pop();
  
        // Flag with INF ranges are merged
        if (curra == INF && currb == INF) {
            tree[currnode] = tree[currnode * 2]
                             + tree[currnode * 2 + 1];
        }
  
        // Leaf node
        else if (curra == currb) {
            tree[currnode] = arr[curra];
        }
  
        else {
  
            // Insert flag node inverse
            // order of evaluation
            st.emplace(currnode, INF, INF);
            int64_t mid = (curra + currb) / 2;
  
            // Push children
            st.emplace(currnode * 2,
                       curra, mid);
            st.emplace(currnode * 2 + 1,
                       mid + 1, currb);
        }
    }
}
  
// A utility function that propagates
// updates lazily down the tree
inline void push_down(int64_t node,
                      int64_t a,
                      int64_t b)
{
    if (lazy[node] != 0) {
        tree[node] += lazy[node] * (b - a + 1);
  
        if (a != b) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
  
        lazy[node] = 0;
    }
}
  
// Iterative Range_Update function to
// add val to all elements in the
// range i-j (inclusive)
void update_tree(int64_t arr_size,
                 int64_t i,
                 int64_t j,
                 int64_t val)
{
  
    // Initialize the stack
    stack<QueryAdaptor> st;
  
    // Emplace the root of the tree
    st.emplace(1, 0, arr_size - 1);
  
    // Work until empty
    while (!st.empty()) {
  
        // Take the indexes at the
        // top of the stack
        int64_t currnode, curra, currb;
        tie(currnode, curra, currb) = st.top();
        st.pop();
  
        // Flag with INF ranges are merged
        if (curra == INF && currb == INF) {
            tree[currnode] = tree[currnode * 2]
                             + tree[currnode * 2 + 1];
        }
  
        // Traverse the previous updates
        // down the tree
        else {
            push_down(currnode, curra, currb);
  
            // No overlap condition
            if (curra > currb || curra > j
                || currb < i) {
                continue;
            }
  
            // Total overlap condition
            else if (curra >= i && currb <= j) 
            {
                
                // Update lazy array
                tree[currnode] += val * (currb - curra + 1);
  
                if (curra != currb) {
                    lazy[currnode * 2] += val;
                    lazy[currnode * 2 + 1] += val;
                }
            }
  
            // Partial Overlap
            else 
            {
                
                // Insert flag node inverse
                // order of evaluation
                st.emplace(currnode, INF, INF);
  
                int64_t mid = (curra + currb) / 2;
  
                // Push children
                st.emplace(currnode * 2,
                           curra, mid);
                st.emplace(currnode * 2 + 1,
                           mid + 1, currb);
            }
        }
    }
}
  
// A function that find the sum of
// all elements in the range i-j
int64_t query(int64_t arr_size,
              int64_t i,
              int64_t j)
{
    
    // Initialize stack
    stack<QueryAdaptor> st;
  
    // Emplace root of the tree
    st.emplace(1, 0, arr_size - 1);
  
    int64_t result = 0;
  
    while (!st.empty()) 
    {
  
        // Take the indexes at the
        // top of the stack
        int64_t currnode, curra, currb;
        tie(currnode, curra, currb) = st.top();
        st.pop();
  
        // Traverse the previous updates
        // down the tree
        push_down(currnode, curra, currb);
  
        // No overlap
        if (curra > currb || curra > j
            || currb < i) {
            continue;
        }
  
        // Total Overlap
        else if (curra >= i && currb <= j) {
            result += tree[currnode];
        }
  
        // Partial Overlap
        else {
            std::int64_t mid = (curra + currb) / 2;
  
            // Push children
            st.emplace(currnode * 2,
                       curra, mid);
            st.emplace(currnode * 2 + 1,
                       mid + 1, currb);
        }
    }
  
    return result;
}
  
// Driver Code
int main()
{
    
    // Initialize our trees with 0
    memset(tree, 0, sizeof(int64_t) * MAXSIZE);
    memset(lazy, 0, sizeof(int64_t) * MAXSIZE);
  
    int64_t arr[] = { 1, 3, 5, 7, 9, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
  
    // Build segment tree from given array
    build_tree(arr, n);
  
    // Print sum of values in array
    // from index 1 to 3
    cout << "Sum of values in given range = "
         << query(n, 1, 3)
         << endl;
  
    // Add 10 to all nodes at indexes
    // from 1 to 5
    update_tree(n, 1, 5, 10);
  
    // Find sum after the value is updated
    cout << "Updated sum of values in given range = "
         << query(n, 1, 3)
         << endl;
  
    return 0;
}

// Java implementation of the approach
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
class GFG 
{
  
    static final int MAXSIZE = 1000;
    static final int INF = (int) Double.POSITIVE_INFINITY;
  
    // Segment Tree array
    static int[] tree = new int[MAXSIZE];
  
    // Lazy Update array
    static int[] lazy = new int[MAXSIZE];
  
    // Build our segment tree
    static void build_tree(int[] arr, int arr_size) 
    {
        
        // Stack will use to update
        // the tree value
        Stack<List<Integer>> st = new Stack<>();
  
        // push the root of the tree
        st.push(Arrays.asList(1, 0, arr_size - 1));
  
        // Repeat until empty
        while (!st.isEmpty())
        {
  
            // Take the indexes at the
            // top of the stack
            int currnode, curra, currb;
  
            // value at the top of the
            // stack
            List<Integer> temp = st.peek();
            currnode = temp.get(0);
            curra = temp.get(1);
            currb = temp.get(2);
  
            // Pop the value from the
            // stack
            st.pop();
  
            // Flag with INF ranges are merged
            if (curra == INF && currb == INF) 
            {
                tree[currnode] = tree[currnode * 2] + 
                  tree[currnode * 2 + 1];
            }
  
            // Leaf node
            else if (curra == currb) 
            {
                tree[currnode] = arr[curra];
            }
  
            else {
  
                // Insert flag node inverse
                // order of evaluation
                st.push(Arrays.asList(currnode, INF, INF));
  
                int mid = (curra + currb) / 2;
  
                // Push children
                st.push(Arrays.asList(currnode * 2, curra, mid));
                st.push(Arrays.asList(currnode * 2 + 1, mid + 1, currb));
            }
        }
    }
  
    // A utility function that propagates
    // updates lazily down the tree
    static void push_down(int node, int a, int b)
    {
        if (lazy[node] != 0) 
        {
            tree[node] += lazy[node] * (b - a + 1);
  
            if (a != b)
            {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
  
            lazy[node] = 0;
        }
    }
  
    // Iterative Range_Update function to
    // add val to all elements in the
    // range i-j (inclusive)
    static void update_tree(int arr_size, int i, 
                            int j, int val)
    {
  
        // Initialize the stack
        Stack<List<Integer>> st = new Stack<>();
  
        // push the root of the tree
        st.push(Arrays.asList(1, 0, arr_size - 1));
  
        // Work until empty
        while (!st.isEmpty()) 
        {
  
            // Take the indexes at the
            // top of the stack
            int currnode, curra, currb;
            List<Integer> temp = st.peek();
            currnode = temp.get(0);
            curra = temp.get(1);
            currb = temp.get(2);
            st.pop();
  
            // Flag with INF ranges are merged
            if (curra == INF && currb == INF)
            {
                tree[currnode] = tree[currnode * 2] + 
                  tree[currnode * 2 + 1];
            }
  
            // Traverse the previous updates
            // down the tree
            else
            {
                push_down(currnode, curra, currb);
  
                // No overlap condition
                if (curra > currb || curra > j || currb < i)
                {
                    continue;
                }
  
                // Total overlap condition
                else if (curra >= i && currb <= j)
                {
                    
                    // Update lazy array
                    tree[currnode] += val * (currb - curra + 1);
  
                    if (curra != currb)
                    {
                        lazy[currnode * 2] += val;
                        lazy[currnode * 2 + 1] += val;
                    }
                }
  
                // Partial Overlap
                else 
                {
                    
                    // Insert flag node inverse
                    // order of evaluation
                    st.push(Arrays.asList(currnode, INF, INF));
  
                    int mid = (curra + currb) / 2;
  
                    // Push children
                    st.push(Arrays.asList(currnode * 2, curra, mid));
                    st.push(Arrays.asList(currnode * 2 + 1,
                                          mid + 1, currb));
                }
            }
        }
    }
  
    // A function that find the sum of
    // all elements in the range i-j
    static int query(int arr_size, int i, int j) 
    {
        
        // Initialize stack
        Stack<List<Integer>> st = new Stack<>();
  
        // push root of the tree
        st.push(Arrays.asList(1, 0, arr_size - 1));
  
        int result = 0;
  
        while (!st.isEmpty()) 
        {
  
            // Take the indexes at the
            // top of the stack
            int currnode, curra, currb;
            List<Integer> temp = st.peek();
            currnode = temp.get(0);
            curra = temp.get(1);
            currb = temp.get(2);
            st.pop();
  
            // Traverse the previous updates
            // down the tree
            push_down(currnode, curra, currb);
  
            // No overlap
            if (curra > currb || curra > j || currb < i)
            {
                continue;
            }
  
            // Total Overlap
            else if (curra >= i && currb <= j)
            {
                result += tree[currnode];
            }
  
            // Partial Overlap
            else
            {
                int mid = (curra + currb) / 2;
  
                // Push children
                st.push(Arrays.asList(currnode * 2, curra, mid));
                st.push(Arrays.asList(currnode * 2 + 1, mid + 1, currb));
            }
        }
  
        return result;
    }
  
    // Driver Code
    public static void main(String[] args) 
    {
  
        // Initialize our trees with 0
        Arrays.fill(tree, 0);
        Arrays.fill(lazy, 0);
  
        int arr[] = { 1, 3, 5, 7, 9, 11 };
        int n = arr.length;
  
        // Build segment tree from given array
        build_tree(arr, n);
  
        // Print sum of values in array
        // from index 1 to 3
        System.out.printf("Sum of values in given range = %d\n", query(n, 1, 3));
  
        // Add 10 to all nodes at indexes
        // from 1 to 5
        update_tree(n, 1, 5, 10);
  
        // Find sum after the value is updated
        System.out.printf("Updated sum of values in given range = %d\n", query(n, 1, 3));
    }
}
  
// This code is contributed by sanjeev2552

Sum of values in given range = 15
Updated sum of values in given range = 45

Complejidad del tiempo: 
 

• Para la construcción del árbol : O(N), hay (2n-1) Nodes en el árbol y el valor de cada Node se calcula una vez.
• Para consulta : O (log N), para consultar una suma, procesamos como máximo cuatro Nodes en cada nivel y el número de niveles es log N.
• Para Actualizar : O(log N), para actualizar el árbol con propagación perezosa es O(Log N), ya que actualizamos la raíz del árbol y luego actualizamos solo la parte del árbol cuyos rangos se superponen en cada nivel.

Tema relacionado: Árbol de segmentos