Árbol de segmentos iterativos (consulta de rango máximo con actualización de Node)

Dada una array arr[0 . . . n-1]. La tarea es realizar la siguiente operación: 

  • Encuentre el máximo de elementos del índice l a r donde 0 <= l <= r <= n-1.
  • Cambia el valor de un elemento específico de la array a un nuevo valor x. Dados i y x, cambie A[i] por x, 0 <= i <= n-1.

Ejemplos: 

Entrada: a[] = {2, 6, 7, 5, 18, 86, 54, 2} 
Consulta 1: máximo (2, 7) 
Consulta 2: actualización (3, 90) 
Consulta 3: máximo (2, 6) 
Salida: 
máximo en el rango de 2 a 7 es 86. 
El máximo en el rango de 2 a 6 es 90. 

Hemos discutido la implementación del árbol de segmentos recursivos . En esta publicación, implementación iterativase discute. La versión iterativa del árbol de segmentos básicamente usa el hecho de que para un índice i, el hijo izquierdo = 2 * i y el hijo derecho = 2 * i + 1 en el árbol. El padre para un índice i en la array del árbol de segmentos se puede encontrar por padre = i / 2. Por lo tanto, podemos viajar fácilmente hacia arriba y hacia abajo a través de los niveles del árbol uno por uno. Al principio, calculamos el máximo en los rangos mientras construimos el árbol a partir de los Nodes hoja y subimos a través de los niveles uno por uno. Usamos el mismo concepto al procesar las consultas para encontrar el máximo en un rango. Dado que hay niveles (log n) en el peor de los casos, la consulta lleva tiempo log n. Para la actualización de un índice en particular a un valor dado, comenzamos a actualizar el árbol de segmentos a partir de los Nodes hoja y actualizamos todos los Nodes que se ven afectados por la actualización del Node actual subiendo gradualmente a través de los niveles en cada iteración. La actualización también requiere tiempo de registro porque allí tenemos que actualizar todos los niveles a partir del Node de hoja donde actualizamos el valor exacto en el índice exacto proporcionado por el usuario.

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

C++

// C++ Program to implement
// iterative segment tree.
#include <bits/stdc++.h>
using namespace std;
  
void construct_segment_tree(vector<int>& segtree,
                            vector<int>& a, int n)
{
    // assign values to leaves of the segment tree
    for (int i = 0; i < n; i++)
        segtree[n + i] = a[i];
  
    /* assign values to internal nodes
    to compute maximum in a given range */
    for (int i = n - 1; i >= 1; i--)
        segtree[i] = max(segtree[2 * i],
                         segtree[2 * i + 1]);
}
  
void update(vector<int>& segtree, int pos, int value,
            int n)
{
    // change the index to leaf node first
    pos += n;
  
    // update the value at the leaf node
    // at the exact index
    segtree[pos] = value;
  
    while (pos > 1) {
  
        // move up one level at a time in the tree
        pos >>= 1;
  
        // update the values in the nodes in
        // the next higher level
        segtree[pos] = max(segtree[2 * pos],
                           segtree[2 * pos + 1]);
    }
}
  
int range_query(vector<int>& segtree, int left, int
                                                    right,
                int n)
{
    /* Basically the left and right indices will move
        towards right and left respectively and with
        every each next higher level and compute the 
        maximum at each height. */
    // change the index to leaf node first
    left += n;
    right += n;
  
    // initialize maximum to a very low value
    int ma = INT_MIN;
  
    while (left < right) {
  
        // if left index in odd
        if (left & 1) {
            ma = max(ma, segtree[left]);
  
            // make left index even
            left++;
        }
  
        // if right index in odd
        if (right & 1) {
  
            // make right index even
            right--;
  
            ma = max(ma, segtree[right]);
        }
  
        // move to the next higher level
        left /= 2;
        right /= 2;
    }
    return ma;
}
  
// Driver code
int main()
{
    vector<int> a = { 2, 6, 10, 4, 7, 28, 9, 11, 6, 33 };
    int n = a.size();
  
    /* Construct the segment tree by assigning 
    the values to the internal nodes*/
    vector<int> segtree(2 * n);
    construct_segment_tree(segtree, a, n);
  
    // compute maximum in the range left to right
    int left = 1, right = 5;
    cout << "Maximum in range " << left << " to "
         << right << " is " << range_query(segtree, left,
                                           right + 1, n)
         << "\n";
  
    // update the value of index 5 to 32
    int index = 5, value = 32;
  
    // a[5] = 32;
    // Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, 6, 33}
    update(segtree, index, value, n);
  
    // compute maximum in the range left to right
    left = 2, right = 8;
    cout << "Maximum in range " << left << " to "
         << right << " is " << range_query(segtree,
                                           left, right + 1, n)
         << "\n";
  
    return 0;
}

Python3

# Python Program to implement
# iterative segment tree.
  
from sys import maxsize
INT_MIN = -maxsize
  
def construct_segment_tree(a: list, n: int):
    global segtree
  
    # assign values to leaves of the segment tree
    for i in range(n):
        segtree[n + i] = a[i]
  
    # assign values to internal nodes
    # to compute maximum in a given range */
    for i in range(n - 1, 0, -1):
        segtree[i] = max(segtree[2 * i], segtree[2 * i + 1])
  
def update(pos: int, value: int, n: int):
    global segtree
  
    # change the index to leaf node first
    pos += n
  
    # update the value at the leaf node
    # at the exact index
    segtree[pos] = value
  
    while pos > 1:
  
        # move up one level at a time in the tree
        pos //= 2
  
        # update the values in the nodes in
        # the next higher level
        segtree[pos] = max(segtree[2 * pos], segtree[2 * pos + 1])
  
def range_query(left: int, right: int, n: int) -> int:
    global segtree
  
    # Basically the left and right indices will move
    # towards right and left respectively and with
    # every each next higher level and compute the
    # maximum at each height.
    # change the index to leaf node first
    left += n
    right += n
  
    # initialize maximum to a very low value
    ma = INT_MIN
    while left < right:
  
        # if left index in odd
        if left & 1:
            ma = max(ma, segtree[left])
  
            # make left index even
            left += 1
  
        # if right index in odd
        if right & 1:
  
            # make right index even
            right -= 1
  
            ma = max(ma, segtree[right])
  
        # move to the next higher level
        left //= 2
        right //= 2
    return ma
  
  
# Driver Code
if __name__ == "__main__":
    a = [2, 6, 10, 4, 7, 28, 9, 11, 6, 33]
    n = len(a)
  
    # Construct the segment tree by assigning
    # the values to the internal nodes
    segtree = [0] * (2 * n)
    construct_segment_tree(a, n)
  
    # compute maximum in the range left to right
    left = 1
    right = 5
    print("Maximum in range %d to %d is %d" %
        (left, right, range_query(left, right + 1, n)))
  
    # update the value of index 5 to 32
    index = 5
    value = 32
  
    # a[5] = 32;
    # Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, 6, 33}
    update(index, value, n)
  
    # compute maximum in the range left to right
    left = 2
    right = 8
    print("Maximum in range %d to %d is %d" %
        (left, right, range_query(left, right + 1, n)))
  
# This code is contributed by
# sanjeev2552

Javascript

<script>
  
// Javascript program to implement 
// iterative segment tree.
function construct_segment_tree(segtree, a, n)
{
      
    // Assign values to leaves of the segment tree
    for(let i = 0; i < n; i++)
        segtree[n + i] = a[i];
  
    // Assign values to internal nodes
    // to compute maximum in a given range 
    for(let i = n - 1; i >= 1; i--)
        segtree[i] = Math.max(segtree[2 * i],
                              segtree[2 * i + 1]);
}
  
function update(segtree, pos, value, n)
{
      
    // Change the index to leaf node first
    pos += n;
  
    // Update the value at the leaf node
    // at the exact index
    segtree[pos] = value;
  
    while (pos > 1) 
    {
          
        // Move up one level at a time in the tree
        pos >>= 1;
  
        // Update the values in the nodes in
        // the next higher level
        segtree[pos] = Math.max(segtree[2 * pos],
                                segtree[2 * pos + 1]);
    }
}
  
function range_query(segtree, left, right, n)
{
      
    /* Basically the left and right indices will move
        towards right and left respectively and with
        every each next higher level and compute the 
        maximum at each height. */
    // change the index to leaf node first
    left += n;
    right += n;
  
    // Initialize maximum to a very low value
    let ma = Number.MIN_VALUE;
  
    while (left < right)
    {
          
        // If left index in odd
        if ((left & 1) != 0)
        {
            ma = Math.max(ma, segtree[left]);
  
            // Make left index even
            left++;
        }
  
        // If right index in odd
        if ((right & 1) > 0) 
        {
              
            // Make right index even
            right--;
  
            ma = Math.max(ma, segtree[right]);
        }
  
        // Move to the next higher level
        left = parseInt(left / 2, 10);
        right = parseInt(right / 2, 10);
    }
    return ma;
}
  
// Driver code
let a = [ 2, 6, 10, 4, 7, 28, 9, 11, 6, 33 ];
let n = a.length;
  
// Construct the segment tree by assigning 
// the values to the internal nodes
let segtree = new Array(2 * n);
construct_segment_tree(segtree, a, n);
  
// Compute maximum in the range left to right
let left = 1, right = 5;
document.write("Maximum in range " + left + 
               " to " + right + " is " + 
               range_query(segtree, left, right + 1, n) + "</br>");
  
// Update the value of index 5 to 32
let index = 5, value = 32;
  
// a[5] = 32;
// Contents of array : {2, 6, 10, 4, 7, 32, 9, 11, 6, 33}
update(segtree, index, value, n);
  
// Compute maximum in the range left to right
left = 2, right = 8;
document.write("Maximum in range " + left + 
               " to " + right + " is " + 
               range_query(segtree, left, right + 1, n) + "</br>");
  
// This code is contributed by divyesh072019
  
</script>
Producción: 

Maximum in range 1 to 5 is 28
Maximum in range 2 to 8 is 32

 

Complejidad de Tiempo: (N * log N) 
Espacio Auxiliar: O(N)
 

Tema relacionado: Árbol de segmentos

Publicación traducida automáticamente

Artículo escrito por akash1295 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *