Árbol de segmentos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de octubre de 2016; la verificación requiere 41 ediciones .

Un árbol de segmentos es una estructura de datos que le permite encontrar el valor de alguna función asociativa en un segmento arbitrario de una matriz para asintótica . Las funciones más utilizadas son suma, producto, máximo y mínimo. $F$ $a[i],a[i+1],\puntos,a[j]$ $O(\log n)$ $F$

Descripción de la estructura

El árbol de segmentos es un árbol con raíz, cuyas hojas son los elementos del arreglo original, y los otros vértices tienen 2 hijos cada uno. A cada vértice se le asigna un intervalo que es la unión de los intervalos de sus hijos (si el vértice tiene hijos), o un intervalo que contiene un elemento específico del arreglo (para las hojas). Además, para cada vértice se almacena el valor de alguna función asociativa en un intervalo dado. Este árbol tendrá una altura logarítmica ya que el número de niveles no excederá $F$ ${\ estilo de visualización \ registro _ {2} n}$

Árbol de segmentos en memoria

Deje que nuestra matriz tenga elementos: . $a$ $norte$ $a[0],a[1],\puntos,a[n-1]$

Elijamos tal que . Complementemos nuestra matriz de la derecha con elementos neutros para que su longitud sea igual a . Luego, para almacenar el árbol de segmentos construido sobre los elementos de la matriz , necesitamos una matriz de celdas. $h$ ${\ estilo de visualización 2 ^ {h} \ geq n}$ ${\ estilo de visualización 2 ^ {h}}$ $a$ $b$ ${\ estilo de visualización 2^{h+1}}$

No usaremos la celda cero en el arreglo , y las celdas de la primera a la -ésima corresponderán a los vértices del árbol binario con los números correspondientes. Usualmente, la numeración de los vértices del árbol de segmentos se usa en el orden de recorrido en anchura , es decir, la raíz del árbol tiene el número 1, y los hijos izquierdo y derecho del vértice con el número tienen números y respectivamente. Con esta numeración, el vértice con el número en corresponderá al segmento , es decir, el número se almacenará en la celda . $b$ ${\ estilo de visualización (2^{h+1}-1)}$ $v$ ${\ estilo de visualización 2v}$ ${\ estilo de visualización 2v+1}$ ${\ estilo de visualización 2 ^ {k} + u}$ ${\displaystyle 0\leq u<2^{k))$ ${\ estilo de visualización [u2^{hk};(u+1)2^{hk}-1]}$ $b[2^{k}+u]$ $f(a[u2^{hk}],a[u2^{hk}+1],\dots,a[(u+1)2^{hk}-1])$

Más adelante en el artículo se utilizará esta numeración de los vértices del árbol de segmentos. Como alternativa, puede numerar los vértices en el orden de recorrido de profundidad , luego los hijos izquierdo y derecho del vértice tendrán números y , donde es el segmento correspondiente al vértice . Al mismo tiempo, si construye un árbol de segmentos inmediatamente de acuerdo con la matriz original y no lo expande a una longitud (en tal árbol, no todas las longitudes de los segmentos serán potencias de dos y no todas las hojas estarán ubicadas en el máximo profundidad), entonces todas las celdas de la matriz serán suficientes para almacenarlo . Al almacenar un árbol, cuyos vértices están numerados en orden de recorrido en ancho, la longitud de la matriz puede alcanzar . $v$ ${\ estilo de visualización v+1}$ $v+2(\lpiso {\dfrac {L+R}{2}}\rpiso -L+1)$ ${\ estilo de visualización [L; R]}$ $v$ $a$ ${\ estilo de visualización 2 ^ {h}}$ $2n$ $b$ $b$ ${\ estilo de visualización 4n-4}$

Construcción de un árbol de segmentos

A continuación se muestra el código C++ de una función recursiva para construir un árbol de segmentos para una suma de los elementos de una matriz . La complejidad de construir un árbol son las acciones. $\mahop {\rm {construir}}$ $a$ ${\ estilo de visualización O (2 ^ {h}) = O (n)}$

construir vacío () { construir(1, 0, (1 << h) - 1); } compilación vacía (int v, int L, int R) { si (L == R){ b[v] = a[L]; } más { int C = (L + R) / 2; construir (v * 2, L, C); construir (v * 2 + 1, C + 1, R); b[v] = b[v * 2] + b[v * 2 + 1]; } }

Árbol de segmentos con una sola modificación

Cambiando el elemento

Cambiemos el valor de . Luego necesitamos actualizar los valores en las celdas , , ,..., . Por lo tanto, tomará acciones para cambiar el elemento. $ai]$ $b[2^{h}+i]$ $b[2^{h-1}+i/2]$ $b[2^{h-2}+i/4]$ ${\ estilo de visualización b [1]}$ $O(h)=O(\log(n))$

A continuación se muestra el código C++ para un procedimiento recursivo para actualizar el árbol de segmentos para la suma cuando cambia el elemento -th en la matriz de origen . $\mahop {\rm {actualizar}}$ $i$ $a$

actualización nula (int i, int newValue) { actualizar(1, 0, (1 << h) - 1, i, nuevoValor); } actualización nula (int v, int L, int R, int i, int newValue) { si (L == R){ b[v] = nuevoValor; a[i] = nuevoValor; } más { int C = (L + R) / 2; si (yo <= C){ actualizar(v * 2, L, C, i, nuevoValor); } más { actualizar (v * 2 + 1, C + 1, R, i, newValue); } b[v] = b[v * 2] + b[v * 2 + 1]; } }

Cálculo de una función para un segmento

Para calcular una función a partir de elementos , se utiliza la siguiente función recursiva a partir de argumentos , que calcula el valor de la función para el segmento . Aquí , es un vértice de árbol tal que la celda contiene el valor de la función para el segmento . $F$ $a[l],a[l+1],\cdots,a[r]$ ${\ matemáticas {{\ rm {contar}}})$ $v, izq, d, l, r$ $F$ ${\ estilo de visualización [L; R] \ cap [l; r]}$ $v$ $b[v]$ $F$ ${\ estilo de visualización [L; R]}$

Si los segmentos y no se intersecan, entonces la respuesta es igual al elemento neutro de la función (0 para la suma, 1 para el producto, para el máximo, para el mínimo). ${\ estilo de visualización [L; R]}$ $[l;r]$ $F$ ${\ estilo de visualización - \ infinito}$ $+\infty$

Si , entonces la respuesta es . ${\ estilo de visualización [L; R] \ subconjunto [l; r]}$ $b[v]$

De lo contrario, dividimos el segmento por la mitad configurando . Reduzcamos el problema a calcular una función para los segmentos y . Entonces la respuesta es . ${\ estilo de visualización [L; R]}$ $C=\lpiso {\dfrac {L+R}{2}}\rpiso$ $F$ ${\ estilo de visualización [L; C] \ cap [l; r]}$ $[C+1;R]\cap[l;r]$ $f({\rm {contar}}(2v,L,C,l,r),{\rm {contar}}(2v+1,C+1,R,l,r))$

Así, el cálculo de una función sobre un segmento se reduce al cálculo de una función a partir de los elementos del array correspondientes a unos segmentos . $[l;r]$ $b$ ${\ estilo de visualización [2^{k}u;2^{k}(u+1)-1]}$

Demostremos que cuando se calcula la función, se obtendrán los resultados. En cada profundidad, devolveremos un valor de no más de dos vértices de árbol. Por el contrario, suponemos que hay al menos tres de ellos. Pero luego, dos llamadas de dos vértices vecinos podrían reemplazarse por una llamada de su padre común. Por lo tanto, en cada profundidad, devolveremos no más de dos valores. Debido a la construcción, la altura del árbol no supera los . Por lo tanto, no se realizarán más devoluciones. ${\ estilo de visualización 2 \ registro (n)}$ ${\ estilo de visualización \ registro (n)}$ ${\ estilo de visualización 2 \ registro (n)}$

Un razonamiento similar muestra que en una consulta en el árbol no omitiremos más que vértices. ${\ estilo de visualización 4 \ registro (n)}$

A continuación se muestra el código C++ para calcular la suma en un segmento . $[l;r]$

int obtenerSuma(int l, int r) { return obtenerSuma(1, 0, (1 << h) - 1, l, r); } int obtenerSuma(int v, int L, int R, int l, int r) { si (L > r || R < l){ devolver 0; } si (l <= L && R <= r){ devuelve b[v]; } int C = (L + R) / 2; devuelve obtenerSuma(v * 2, L, C, l, r) + obtenerSuma(v * 2 + 1, C + 1, R, l, r); }

Árbol de segmentos con modificación de intervalos

Supongamos que queremos cambiar el valor no de una celda de la matriz , sino de todo el intervalo (por ejemplo, aumentar los valores de todas las celdas del intervalo en un número dado ). Entonces almacenar solo la matriz no es suficiente. Sin embargo, los árboles de segmentos capaces de calcular la suma y el máximo se pueden implementar almacenando dos matrices de la misma longitud e implementando recursivamente la operación de cambio. $a$ $a[l],\cdots,a[r]$ $X$ $b$

Árbol de segmentos para suma (RSQ)

Almacenaremos arreglos con el mismo direccionamiento que el arreglo (ver arriba). $suma$ ${\ estilo de visualización agregar}$ $b$

El procedimiento recursivo consistirá en aumentar el valor de todos los elementos del segmento en el número . puede ser tanto positivo como negativo. Aquí , hay un vértice de árbol tal que la celda contiene la suma de todos los elementos en el intervalo . ${\ estilo de visualización {\ rm {modificar}} (v, L, R, l, r, X)}$ ${\ estilo de visualización [L; R] \ cap [l; r]}$ $X$ $X$ $v$ $suma[v]$ ${\ estilo de visualización [L; R]}$

A continuación se muestra el código del procedimiento en C++. ${\rm {modificar))$

anular modificar (int l, int r, int X) { modificar(1, 0, (1 << h) - 1, l, r, X); } anular modificar (int v, int L, int R, int l, int r, int X) { si (L > r || R < l){ devolver; } si (l <= L && R <= r){ suma[v] += X * (R - L + 1); suma[v] += X; } más { int C = (L + R) / 2; modificar (v * 2, L, C, l, r, X); modificar(v * 2 + 1, C + 1, R, l, r, X); suma[v] = suma[v * 2] + suma[v * 2 + 1] + suma[v] * (R - L + 1); } }

La función recursiva para calcular la suma de un segmento se modifica de la siguiente manera. Ella tiene un argumento más que caracteriza cuánto necesitas aumentar todos los números en el segmento al calcular la suma. ${\ estilo de visualización {\ rm {getSum}}}$ ${\ estilo de visualización [L; R] \ cap [l; r]}$ ${\ estilo de visualización aditivo}$ ${\ estilo de visualización [L; R]}$

int obtenerSuma(int l, int r) { return obtenerSuma(1, 0, (1 << h) - 1, l, r, 0); } int getSum(int v, int L, int R, int l, int r, int aditivo) { si (L > r || R < l){ devolver 0; } si (l <= L && R <= r){ return sum[v] + aditivo * (R - L + 1); } int C = (L + R) / 2; devuelve getSum(v * 2, L, C, l, r, aditivo + sumar[v]) + getSum(v * 2 + 1, C + 1, R, l, r, aditivo + sumar[v]); }

La complejidad de las operaciones es . ${\rm {modificar))$ ${\rm {contar}}$ $O(\registro(n))$

Árbol de segmento máximo (RMQ)

De manera similar al caso anterior, almacenaremos matrices y . El procedimiento tendrá el mismo significado y los mismos argumentos. $máximo$ ${\ estilo de visualización agregar}$ ${\rm {modificar))$

anular modificar (int l, int r, int X) { modificar(1, 0, (1 << h) - 1, l, r, X); } anular modificar (int v, int L, int R, int l, int r, int X) { si (L > r || R < l){ devolver; } si (l <= L && R <= r){ máx[v] += X; suma[v] += X; } más { int C = (L + R) / 2; modificar (v * 2, L, C, l, r, X); modificar(v * 2 + 1, C + 1, R, l, r, X); max[v] = std::max(max[v * 2], max[v * 2 + 1]) + add[v]; } }

La función recursiva para calcular el máximo en un segmento se implementa de manera similar a la función de árbol de segmentos para la suma. ${\ estilo de visualización {\ rm {getMax}}}$ ${\ estilo de visualización [L; R] \ cap [l; r]}$ ${\ estilo de visualización {\ rm {getSum}}}$

int getMax(int l, int r) { return getMax(1, 0, (1 << h) - 1, l, r, 0); } int getMax(int v, int L, int R, int l, int r, int aditivo) { si (L > r || R < l){ devolver -INF; // Menos infinito, es decir un número que ciertamente es menor que cualquier número en nuestro segmento. Por ejemplo, si todos los números son no negativos, puede poner INF = 0. } si (l <= L && R <= r){ devuelve max[v] + aditivo; } int C = (L + R) / 2; int max1 = getMax(v * 2, L, C, l, r, aditivo + sumar[v]); int max2 = getMax(v * 2 + 1, C + 1, R, l, r, aditivo + sumar[v]); devuelve std::max(max1, max2); }

La complejidad de las operaciones es . ${\rm {modificar))$ ${\ estilo de visualización {\ rm {getMax}}}$ $O(\registro(n))$

Resolviendo RMQ con Tabla Dispersa

Además, el problema de RMQ se puede resolver utilizando la tabla Sparse. Esta estructura de datos le permite encontrar el máximo/mínimo en el segmento en O(1) con preprocesamiento en tiempo O(n log n).

Preprocesamiento:

Indicar : máximo/mínimo en el segmento de a . Una matriz se puede llenar dinámicamente así: ${\mahop {{\rm {f))))[i,k]$ $i$ $i+2^{k}-1$ ${\mahop {{\rm {f))))[i,k]$

1) ; ${\mahop {{\rm {f))))[i,0]=a[i]$

2) o respectivamente. ${\mathop {{\rm {f))))[i,k]=\max({\mathop {{\rm {f))))[i,k-1],{\mathop {{\rm {f}}}}[i+2^{{k-1}},k-1])$ ${\mathop {{\rm {f))))[i,k]=\min({\mathop {{\rm {f))))[i,k-1],{\mathop {{\rm {f}}}}[i+2^{{k-1}},k-1])$

Cálculo:

La respuesta en el intervalo es (respectivamente ), donde lg es la potencia máxima de dos que no excede . $[l, r]$ $\max({\mathop {{\rm {f))))[l,lg],{\mathop {{\rm {f))))[r-2^{{lg}}+1,lg] )$ $\min({\mathop {{\rm {f))))[l,lg],{\mathop {{\rm {f))))[r-2^{{lg}}+1,lg] )$ $rl+1$

Ejemplo:

Consideramos el rango de 1 a 5. La potencia máxima de dos que cabe en él es dos, pero no cubre todo el rango, sino solo una parte de 1 a 4. El máximo en este segmento se puede obtener comparando los valores de f[1,2] y f[2,2] (máximos en los segmentos del 1 al 4 y del 2 al 5).

Solución O(1) con preprocesamiento y memoria O(N)

Para tal solución, basta con reducir el problema RMQ al problema LCA construyendo un árbol cartesiano a partir de elementos de la forma , es decir, - clave, - prioridad. Las prioridades deben ordenarse de abajo hacia arriba, es decir, el elemento con el menor . Obviamente, tal árbol es fácil de construir , ya que todas las claves que tenemos están ordenadas (estos son índices consecutivos de elementos de matriz). $(yo, un [yo])$ $i$ $ai]$ $ai]$ $EN)$

Después de eso, la respuesta a cualquier solicitud será el LCA de dos vértices y . El índice LCA estará en , ya que el árbol cartesiano por clave es un árbol binario. Debido al hecho de que el árbol cartesiano es un montón de prioridad , el mismo nodo tendrá la prioridad más baja (valor del elemento) de todos los que están en $(l,a[l])$ $(r,a[r])$ $[l;r]$ $[l;r]$

Se conocen varias soluciones posibles para el problema LCA con preprocesamiento y memoria . Tal solución es asintóticamente óptima. $O(1)$ $EN)$

Enlaces

Véase también

árbol de fenwick
Lista de estructuras de datos (árboles)

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión