Árbol de segmentos iterativos (consulta de rango mínimo)

Hemos discutido la implementación del árbol de segmentos recursivos . En esta publicación, se analiza la implementación iterativa.
Consideremos el siguiente problema para comprender los árboles de segmentos.
Tenemos una array arr[0 . . . n-1]. Deberíamos poder 
1 Encontrar el mínimo de elementos del índice l a r donde 0 <= l <= r <= n-1 
2 Cambiar el valor de un elemento específico de la array a un nuevo valor x. Necesitamos hacer arr[i] = x donde 0 <= i <= n-1.
Ejemplos: 
 

Input : 2, 6, 7, 5, 18, 86, 54, 2
        minimum(2, 7)  
        update(3, 4)
        minimum(2, 6) 
Output : Minimum in range 2 to 7 is 2.
         Minimum in range 2 to 6 is 4.

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ínimo 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ínimo 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. 
 

C++

// CPP Program to implement iterative segment
// tree.
#include <bits/stdc++.h>
#define ll long long
 
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 minimum in a given range */
    for (int i = n - 1; i >= 1; i--)
        segtree[i] = min(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] = min(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
        minimum at each height. */
    // change the index to leaf node first
    left += n;
    right += n;
 
    // initialize minimum to a very high value
    int mi = (int)1e9;
 
    while (left < right) {
 
        // if left index in odd
        if (left & 1) {
            mi = min(mi, segtree[left]);
 
            // make left index even
            left++;
        }
 
        // if right index in odd
        if (right & 1) {
 
            // make right index even
            right--;
 
            mi = min(mi, segtree[right]);
        }
 
        // move to the next higher level
        left /= 2;
        right /= 2;
    }
    return mi;
}
 
// 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 minimum in the range left to right
    int left = 0, right = 5;
    cout << "Minimum in range " << left << " to "
         << right << " is "<< range_query(segtree, left,
                                  right + 1, n) << "\n";
 
    // update the value of index 3 to 1
    int index = 3, value = 1;
 
    // a[3] = 1;
    // Contents of array : {2, 6, 10, 1, 7, 28, 9, 11, 6, 33}
    update(segtree, index, value, n); // point update
 
    // compute minimum in the range left to right
    left = 2, right = 6;
    cout << "Minimum in range " << left << " to "
         << right << " is " << range_query(segtree,
                      left, right + 1, n) << "\n";
 
    return 0;
}

Java

// Java Program to implement iterative segment
// tree.
import java.io.*;
import java.util.*;
 
class GFG
{
 
    static void construct_segment_tree(int[] segtree,
                                        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 minimum in a given range
        */
        for (int i = n - 1; i >= 1; i--)
            segtree[i] = Math.min(segtree[2 * i], segtree[2 * i + 1]);
    }
 
    static void update(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] = Math.min(segtree[2 * pos],
                                segtree[2 * pos + 1]);
        }
    }
 
    static int range_query(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
        * minimum at each height. */
        // change the index to leaf node first
        left += n;
        right += n;
 
        // initialize minimum to a very high value
        int mi = (int) 1e9;
 
        while (left < right)
        {
 
            // if left index in odd
            if ((left & 1) == 1)
            {
                mi = Math.min(mi, segtree[left]);
 
                // make left index even
                left++;
            }
 
            // if right index in odd
            if ((right & 1) == 1)
            {
 
                // make right index even
                right--;
 
                mi = Math.min(mi, segtree[right]);
            }
 
            // move to the next higher level
            left /= 2;
            right /= 2;
        }
        return mi;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] a = {2, 6, 10, 4, 7, 28, 9, 11, 6, 33};
        int n = a.length;
 
        /*
        * Construct the segment tree by assigning
        * the values to the internal nodes
        */
        int[] segtree = new int[2 * n];
        construct_segment_tree(segtree, a, n);
 
        // compute minimum in the range left to right
        int left = 0, right = 5;
        System.out.printf("Minimum in range %d to %d is %d\n",
                           left, right, range_query(segtree,
                           left, right + 1, n));
 
        // update the value of index 3 to 1
        int index = 3, value = 1;
         
        // a[3] = 1;
        // Contents of array : {2, 6, 10, 1, 7, 28, 9, 11, 6, 33}
        update(segtree, index, value, n); // point update
 
        // compute minimum in the range left to right
        left = 2;
        right = 6;
        System.out.printf("Minimum in range %d to %d is %d\n",
                           left, right, range_query(segtree,
                           left, right + 1, n));
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 program to implement
# iterative segment tree.
def construct_segment_tree(segtree, a, n):
     
    # assign values to leaves of
    # the segment tree
    for i in range(n):
        segtree[n + i] = a[i];
     
    # assign values to remaining nodes
    # to compute minimum in a given range
    for i in range(n - 1, 0, -1):
        segtree[i] = min(segtree[2 * i],
                         segtree[2 * i + 1])
                         
def range_query(segtree, left, right, n):
    left += n
    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 minimum at each height change
        the index to leaf node first """
    mi = 1e9 # initialize minimum to a very high value
    while (left < right):
        if (left & 1): # if left index in odd
                mi = min(mi, segtree[left])
                left = left + 1
        if (right & 1): # if right index in odd
                right -= 1
                mi = min(mi, segtree[right])
                 
        # move to the next higher level
        left = left // 2
        right = right // 2
    return mi
 
def 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] = min(segtree[2 * pos],
                           segtree[2 * pos + 1])
 
# Driver Code    
 
# Elements in list
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 for i in range(2 * n)]
construct_segment_tree(segtree, a, n);
left = 0
right = 5 #compute minimum in the range left to right
print ("Minimum in range", left, "to", right, "is",
        range_query(segtree, left, right + 1, n))
 
# update the value of index 3 to 1
index = 3
value = 1
 
# a[3] = 1;
# Contents of array : {2, 6, 10, 1, 7, 28, 9, 11, 6, 33}
update(segtree, index, value, n); # point update
left = 2
right = 6 # compute minimum in the range left to right
print("Minimum in range", left, "to", right, "is",
       range_query(segtree, left, right + 1, n))
        
# This code is contributed by sarthak Raghuwanshi

C#

// C# Program to implement iterative segment
// tree.
using System;
 
class GFG
{
 
    static void construct_segment_tree(int[] segtree,
                                        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 minimum in a given range
        */
        for (int i = n - 1; i >= 1; i--)
            segtree[i] = Math.Min(segtree[2 * i],
                            segtree[2 * i + 1]);
    }
 
    static void update(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] = Math.Min(segtree[2 * pos],
                                segtree[2 * pos + 1]);
        }
    }
 
    static int range_query(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
        * minimum at each height. */
        // change the index to leaf node first
        left += n;
        right += n;
 
        // initialize minimum to a very high value
        int mi = (int) 1e9;
 
        while (left < right)
        {
 
            // if left index in odd
            if ((left & 1) == 1)
            {
                mi = Math.Min(mi, segtree[left]);
 
                // make left index even
                left++;
            }
 
            // if right index in odd
            if ((right & 1) == 1)
            {
 
                // make right index even
                right--;
 
                mi = Math.Min(mi, segtree[right]);
            }
 
            // move to the next higher level
            left /= 2;
            right /= 2;
        }
        return mi;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] a = {2, 6, 10, 4, 7, 28, 9, 11, 6, 33};
        int n = a.Length;
 
        /*
        * Construct the segment tree by assigning
        * the values to the internal nodes
        */
        int[] segtree = new int[2 * n];
        construct_segment_tree(segtree, a, n);
 
        // compute minimum in the range left to right
        int left = 0, right = 5;
        Console.Write("Minimum in range {0} to {1} is {2}\n",
                        left, right, range_query(segtree,
                        left, right + 1, n));
 
        // update the value of index 3 to 1
        int index = 3, value = 1;
         
        // a[3] = 1;
        // Contents of array : {2, 6, 10, 1, 7, 28, 9, 11, 6, 33}
        update(segtree, index, value, n); // point update
 
        // compute minimum in the range left to right
        left = 2;
        right = 6;
        Console.Write("Minimum in range {0} to {1} is {2}\n",
                        left, right, range_query(segtree,
                        left, right + 1, n));
    }
}
 
// This code is contributed by Rajput-Ji

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 (var i = 0; i < n; i++)
        segtree[n + i] = a[i];
    /*
    * assign values to internal nodes
    * to compute minimum in a given range
    */
    for (var i = n - 1; i >= 1; i--)
        segtree[i] = Math.min(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.min(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
    * minimum at each height. */
    // change the index to leaf node first
    left += n;
    right += n;
    // initialize minimum to a very high value
    var mi = 1000000000;
    while (left < right)
    {
     
        // if left index in odd
        if ((left & 1) == 1)
        {
            mi = Math.min(mi, segtree[left]);
            // make left index even
            left++;
        }
        // if right index in odd
        if ((right & 1) == 1)
        {
            // make right index even
            right--;
            mi = Math.min(mi, segtree[right]);
        }
        // move to the next higher level
        left /= 2;
        right /= 2;
    }
    return mi;
}
 
// Driver Code
var a = [2, 6, 10, 4, 7, 28, 9, 11, 6, 33];
var n = a.length;
/*
* Construct the segment tree by assigning
* the values to the internal nodes
*/
var segtree = Array(2*n).fill(0);
construct_segment_tree(segtree, a, n);
 
// compute minimum in the range left to right
var left = 0, right = 5;
document.write(`Minimum in range ${left} to ${right} is ${range_query(segtree,left, right + 1, n)}<br>`)
 
// update the value of index 3 to 1
var index = 3, value = 1;
 
// a[3] = 1;
// Contents of array : {2, 6, 10, 1, 7, 28, 9, 11, 6, 33}
update(segtree, index, value, n); // point update
 
// compute minimum in the range left to right
left = 2;
right = 6;
document.write(`Minimum in range ${left} to ${right} is ${range_query(segtree, left, right + 1, n)}<br>`);
 
// This code is contributed by rutvik_56.
</script>
Producción: 

Minimum in range 0 to 5 is 2
Minimum in range 2 to 6 is 1

 

Tiempo Complejidad : (n log n) 
Espacio Auxiliar : (n)
 

Publicación traducida automáticamente

Artículo escrito por jaideeppyne1997 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 *