Consideremos el siguiente problema para comprender los árboles de segmentos sin recursividad.
Tenemos una array arr[0 . . . n-1]. Deberíamos poder,
- Encuentre la suma 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. Necesitamos hacer arr[i] = x donde 0 <= i <= n-1.
Una solución simple es ejecutar un ciclo de l a r y calcular la suma de los elementos en el rango dado. Para actualizar un valor, simplemente haga arr[i] = x. La primera operación toma el tiempo O(n) y la segunda operación toma el tiempo O(1) .
Otra solución es crear otra array y almacenar la suma desde el principio hasta i en el i-ésimo índice de esta array. La suma de un rango dado ahora se puede calcular en tiempo O(1), pero la operación de actualización ahora toma tiempo O(n). Esto funciona bien si la cantidad de operaciones de consulta es grande y hay muy pocas actualizaciones.
¿Qué pasa si el número de consultas y actualizaciones es igual? ¿Podemos realizar ambas operaciones en tiempo O (log n) una vez dada la array? Podemos usar un árbol de segmentos para realizar ambas operaciones en tiempo O (Iniciar sesión). Hemos discutido la implementación completa de los árboles de segmentos en nuestra publicación anterior . En esta publicación, discutiremos la implementación más fácil y eficiente de los árboles de segmentos que en la publicación anterior.
Considere la array y el árbol de segmentos como se muestra a continuación:
Puede ver en la imagen de arriba que la array original está en la parte inferior y tiene un índice de 0 con 16 elementos. El árbol contiene un total de 31 Nodes donde los Nodes hoja o los elementos del arreglo original comienzan desde el Node 16. Entonces, podemos construir fácilmente un árbol de segmentos para este arreglo usando un arreglo de tamaño 2*N donde N es el número de elementos en la array original. Los Nodes hoja comenzarán desde el índice N en esta array y subirán hasta el índice (2*N – 1). Por lo tanto, el elemento en el índice i en la array original estará en el índice (i + N) en la array del árbol de segmentos. Ahora, para calcular los padres, comenzaremos desde el índice (N – 1) y nos moveremos hacia arriba. Para el índice i, el hijo de la izquierda estará en (2 * i) y el hijo de la derecha estará en el índice (2*i + 1). Entonces, los valores en los Nodes en (2 * i) y (2*i + 1) se combinan en el i-ésimo Node para construir el árbol.
Como puede ver en la figura anterior, podemos consultar en este árbol en un intervalo [L,R) con el índice izquierdo (L) incluido y el derecho (R) excluido.
Implementaremos todas estas operaciones de multiplicación y suma utilizando operadores bit a bit.
Echemos un vistazo a la implementación completa:
C++
#include <bits/stdc++.h>
using namespace std;
// limit for array size
const int N = 100000;
int n; // array size
// Max size of tree
int tree[2 * N];
// function to build the tree
void build( int arr[])
{
// insert leaf nodes in tree
for (int i=0; i<n; i++)
tree[n+i] = arr[i];
// build the tree by calculating parents
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i<<1] + tree[i<<1 | 1];
}
// function to update a tree node
void updateTreeNode(int p, int value)
{
// set value at position p
tree[p+n] = value;
p = p+n;
// move upward and update parents
for (int i=p; i > 1; i >>= 1)
tree[i>>1] = tree[i] + tree[i^1];
}
// function to get sum on interval [l, r)
int query(int l, int r)
{
int res = 0;
// loop to find the sum in the range
for (l += n, r += n; l < r; l >>= 1, r >>= 1)
{
if (l&1)
res += tree[l++];
if (r&1)
res += tree[--r];
}
return res;
}
// driver program to test the above function
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
// n is global
n = sizeof(a)/sizeof(a[0]);
// build tree
build(a);
// print the sum in range(1,2) index-based
cout << query(1, 3)<<endl;
// modify element at 2nd index
updateTreeNode(2, 1);
// print the sum in range(1,2) index-based
cout << query(1, 3)<<endl;
return 0;
}
Java
import java.io.*;
public class GFG {
// limit for array size
static int N = 100000;
static int n; // array size
// Max size of tree
static int []tree = new int[2 * N];
// function to build the tree
static void build( int []arr)
{
// insert leaf nodes in tree
for (int i = 0; i < n; i++)
tree[n + i] = arr[i];
// build the tree by calculating
// parents
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i << 1] +
tree[i << 1 | 1];
}
// function to update a tree node
static void updateTreeNode(int p, int value)
{
// set value at position p
tree[p + n] = value;
p = p + n;
// move upward and update parents
for (int i = p; i > 1; i >>= 1)
tree[i >> 1] = tree[i] + tree[i^1];
}
// function to get sum on
// interval [l, r)
static int query(int l, int r)
{
int res = 0;
// loop to find the sum in the range
for (l += n, r += n; l < r;
l >>= 1, r >>= 1)
{
if ((l & 1) > 0)
res += tree[l++];
if ((r & 1) > 0)
res += tree[--r];
}
return res;
}
// driver program to test the
// above function
static public void main (String[] args)
{
int []a = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12};
// n is global
n = a.length;
// build tree
build(a);
// print the sum in range(1,2)
// index-based
System.out.println(query(1, 3));
// modify element at 2nd index
updateTreeNode(2, 1);
// print the sum in range(1,2)
// index-based
System.out.println(query(1, 3));
}
}
// This code is contributed by vt_m.
Python3
# Python3 Code Addition # limit for array size N = 100000; # Max size of tree tree = [0] * (2 * N); # function to build the tree def build(arr) : # insert leaf nodes in tree for i in range(n) : tree[n + i] = arr[i]; # build the tree by calculating parents for i in range(n - 1, 0, -1) : tree[i] = tree[i << 1] + tree[i << 1 | 1]; # function to update a tree node def updateTreeNode(p, value) : # set value at position p tree[p + n] = value; p = p + n; # move upward and update parents i = p; while i > 1 : tree[i >> 1] = tree[i] + tree[i ^ 1]; i >>= 1; # function to get sum on interval [l, r) def query(l, r) : res = 0; # loop to find the sum in the range l += n; r += n; while l < r : if (l & 1) : res += tree[l]; l += 1 if (r & 1) : r -= 1; res += tree[r]; l >>= 1; r >>= 1 return res; # Driver Code if __name__ == "__main__" : a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]; # n is global n = len(a); # build tree build(a); # print the sum in range(1,2) index-based print(query(1, 3)); # modify element at 2nd index updateTreeNode(2, 1); # print the sum in range(1,2) index-based print(query(1, 3)); # This code is contributed by AnkitRai01
C#
using System;
public class GFG {
// limit for array size
static int N = 100000;
static int n; // array size
// Max size of tree
static int []tree = new int[2 * N];
// function to build the tree
static void build( int []arr)
{
// insert leaf nodes in tree
for (int i = 0; i < n; i++)
tree[n + i] = arr[i];
// build the tree by calculating
// parents
for (int i = n - 1; i > 0; --i)
tree[i] = tree[i << 1] +
tree[i << 1 | 1];
}
// function to update a tree node
static void updateTreeNode(int p, int value)
{
// set value at position p
tree[p + n] = value;
p = p + n;
// move upward and update parents
for (int i = p; i > 1; i >>= 1)
tree[i >> 1] = tree[i] + tree[i^1];
}
// function to get sum on
// interval [l, r)
static int query(int l, int r)
{
int res = 0;
// loop to find the sum in the range
for (l += n, r += n; l < r;
l >>= 1, r >>= 1)
{
if ((l & 1) > 0)
res += tree[l++];
if ((r & 1) > 0)
res += tree[--r];
}
return res;
}
// driver program to test the
// above function
static public void Main ()
{
int []a = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12};
// n is global
n = a.Length;
// build tree
build(a);
// print the sum in range(1,2)
// index-based
Console.WriteLine(query(1, 3));
// modify element at 2nd index
updateTreeNode(2, 1);
// print the sum in range(1,2)
// index-based
Console.WriteLine(query(1, 3));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// limit for array size
let N = 100000;
let n; // array size
// Max size of tree
let tree = new Array(2 * N);
tree.fill(0);
// function to build the tree
function build(arr)
{
// insert leaf nodes in tree
for (let i = 0; i < n; i++)
tree[n + i] = arr[i];
// build the tree by calculating
// parents
for (let i = n - 1; i > 0; --i)
tree[i] = tree[i << 1] +
tree[i << 1 | 1];
}
// function to update a tree node
function updateTreeNode(p, value)
{
// set value at position p
tree[p + n] = value;
p = p + n;
// move upward and update parents
for (let i = p; i > 1; i >>= 1)
tree[i >> 1] = tree[i] + tree[i^1];
}
// function to get sum on
// interval [l, r)
function query(l, r)
{
let res = 0;
// loop to find the sum in the range
for (l += n, r += n; l < r;
l >>= 1, r >>= 1)
{
if ((l & 1) > 0)
res += tree[l++];
if ((r & 1) > 0)
res += tree[--r];
}
return res;
}
let a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
// n is global
n = a.length;
// build tree
build(a);
// print the sum in range(1,2)
// index-based
document.write(query(1, 3) + "</br>");
// modify element at 2nd index
updateTreeNode(2, 1);
// print the sum in range(1,2)
// index-based
document.write(query(1, 3));
</script>
Producción:
5 3
¡Sí! Eso es todo. La implementación completa del árbol de segmentos incluye las funciones de consulta y actualización en un número menor de líneas de código que el recursivo anterior. Ahora entendamos cómo funciona cada una de las funciones:
1. La imagen deja en claro que los Nodes de hoja se almacenan en i+n, por lo que podemos insertar claramente todos los Nodes de hoja directamente.
2. El siguiente paso es construir el árbol y lleva O(n) tiempo. El padre siempre tiene un índice menor que sus hijos, por lo que solo procesamos todos los Nodes en orden decreciente, calculando el valor del Node padre. Si el código dentro de la función de compilación para calcular los padres parece confuso, puede ver este código. Es equivalente a eso dentro de la función de compilación.
tree[i]=tree[2*i]+tree[2*i+1]
3. Actualizar un valor en cualquier posición también es sencillo y el tiempo necesario será proporcional a la altura del árbol. Solo actualizamos valores en los padres del Node dado que se está cambiando. Entonces, para obtener el padre, simplemente subimos al Node padre, que es p/2 o p>>1, para el Node p. p^1 convierte (2*i) en (2*i + 1) y viceversa para obtener el segundo hijo de p.
4. Calcular la suma también funciona en tiempo O(log(n)). Si trabajamos a través de un intervalo de [3,11), necesitamos calcular solo para los Nodes 19,26,12 y 5 en ese orden.
La idea detrás de la función de consulta es si debemos incluir un elemento en la suma o si debemos incluir su padre. Miremos la imagen una vez más para una comprensión adecuada. Considere que L es el borde izquierdo de un intervalo y R es el borde derecho del intervalo [L,R). Está claro a partir de la imagen que si L es impar, entonces significa que es el hijo derecho de su padre y nuestro intervalo incluye solo a L y no al padre. Así que simplemente incluiremos este Node para sumar y pasar al padre de su siguiente Node haciendo L = (L+1)/2. Ahora, si L es par, entonces es el hijo izquierdo de su padre y el intervalo también incluye a su padre a menos que interfieran los bordes derechos. Se aplican condiciones similares al borde derecho también para un cálculo más rápido. Detendremos esta iteración una vez que los bordes izquierdo y derecho se encuentren.
Las complejidades de tiempo teóricas tanto de la implementación anterior como de esta implementación son las mismas, pero en la práctica se encuentra que es mucho más eficiente ya que no hay llamadas recursivas. Simplemente iteramos sobre los elementos que necesitamos. Además, esto es muy fácil de implementar.
Complejidades de tiempo:
- Construcción del árbol: O( n )
- Consulta en rango: O (Iniciar sesión)
- Actualización de un elemento: O( Log n ).
Espacio auxiliar: O(2*N)
Este artículo es una contribución de Striver . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA