Árbol de Segmentos

Un Árbol de Segmentos (Segment Tree) es una estructura de datos que guarda información sobre intervalos de un arreglo en forma de árbol. Esto permite responder consultas de rango sobre un arreglo de forma eficiente, y al mismo tiempo es lo bastante flexible como para permitir modificar el arreglo con rapidez. Esto incluye encontrar la suma de elementos consecutivos del arreglo $a[l \dots r]$ , o encontrar el elemento mínimo en un rango de ese tipo, en tiempo $O(\log n)$ . Entre respuestas a esas consultas, el Árbol de Segmentos permite modificar el arreglo reemplazando un elemento, o incluso cambiando los elementos de todo un subsegmento (p. ej. asignar a todos los elementos $a[l \dots r]$ un valor cualquiera, o sumar un valor a todos los elementos del subsegmento).

En general, un Árbol de Segmentos es una estructura de datos muy flexible, y se puede resolver una enorme cantidad de problemas con él. Además, también es posible aplicar operaciones más complejas y responder consultas más complejas (véase Versiones avanzadas de Árboles de Segmentos). En particular, el Árbol de Segmentos se puede generalizar con facilidad a dimensiones mayores. Por ejemplo, con un Árbol de Segmentos bidimensional se pueden responder consultas de suma o de mínimo sobre algún subrectángulo de una matriz dada en solo tiempo $O(\log^2 n)$ .

Una propiedad importante de los Árboles de Segmentos es que requieren solo una cantidad lineal de memoria. El Árbol de Segmentos estándar requiere $4n$ vértices para trabajar sobre un arreglo de tamaño $n$ .

Forma más simple de un Árbol de Segmentos

Para empezar de forma sencilla, consideramos la forma más simple de un Árbol de Segmentos. Queremos responder consultas de suma de forma eficiente. La definición formal de la tarea es: Dado un arreglo $a[0 \dots n-1]$ , el Árbol de Segmentos debe poder encontrar la suma de los elementos entre los índices $l$ y $r$ (es decir, calcular la suma $\sum_{i=l}^r a[i]$ ), y también manejar cambios de valores de los elementos del arreglo (es decir, realizar asignaciones de la forma $a[i] = x$ ). El Árbol de Segmentos debe poder procesar ambas consultas en tiempo $O(\log n)$ .

Esto es una mejora respecto de los enfoques más simples. Una implementación naive con arreglo —usar simplemente un arreglo— puede actualizar elementos en $O(1)$ , pero requiere $O(n)$ para calcular cada consulta de suma. Y las sumas de prefijos precomputadas pueden calcular consultas de suma en $O(1)$ , pero actualizar un elemento del arreglo requiere $O(n)$ cambios en las sumas de prefijos.

Estructura del Árbol de Segmentos

Podemos tomar un enfoque de divide y vencerás cuando se trata de segmentos de un arreglo. Calculamos y guardamos la suma de los elementos de todo el arreglo, es decir, la suma del segmento $a[0 \dots n-1]$ . Luego partimos el arreglo en dos mitades $a[0 \dots (n-1)/2]$ y $a[(n+1)/2 \dots n-1]$ y calculamos la suma de cada mitad y las guardamos. Cada una de estas dos mitades se parte a su vez por la mitad, y así sucesivamente hasta que todos los segmentos alcanzan tamaño $1$ .

Podemos ver estos segmentos como formando un árbol binario: la raíz de este árbol es el segmento $a[0 \dots n-1]$ , y cada vértice (excepto los vértices hoja) tiene exactamente dos vértices hijos. Por eso la estructura de datos se llama “Árbol de Segmentos”, aunque en la mayoría de las implementaciones el árbol no se construye de forma explícita (véase Implementación).

Aquí hay una representación visual de un Árbol de Segmentos de este tipo sobre el arreglo $a = [1, 3, -2, 8, -7]$ :

"Árbol de Segmentos de suma"

A partir de esta breve descripción de la estructura de datos, ya podemos concluir que un Árbol de Segmentos solo requiere una cantidad lineal de vértices. El primer nivel del árbol contiene un solo nodo (la raíz), el segundo nivel contendrá dos vértices, en el tercero contendrá cuatro vértices, hasta que el número de vértices alcanza $n$ . Así, el número de vértices en el peor caso se puede estimar por la suma $1 + 2 + 4 + \dots + 2^{\lceil\log_2 n\rceil} \lt 2^{\lceil\log_2 n\rceil + 1} \lt 4n$ .

Vale la pena notar que cuando $n$ no es una potencia de dos, no todos los niveles del Árbol de Segmentos estarán completamente llenos. Podemos ver ese comportamiento en la imagen. Por ahora podemos olvidarnos de este hecho, pero se volverá importante más adelante durante la implementación.

La altura del Árbol de Segmentos es $O(\log n)$ , porque al bajar de la raíz a las hojas el tamaño de los segmentos disminuye aproximadamente a la mitad.

Construcción

Antes de construir el Árbol de Segmentos, hay que decidir:

el valor que se guarda en cada nodo del Árbol de Segmentos. Por ejemplo, en un Árbol de Segmentos de suma, un nodo guardaría la suma de los elementos en su rango $[l, r]$ .
la operación de merge que fusiona dos hermanos en un Árbol de Segmentos. Por ejemplo, en un Árbol de Segmentos de suma, los dos nodos correspondientes a los rangos $a[l_1 \dots r_1]$ y $a[l_2 \dots r_2]$ se fusionarían en un nodo correspondiente al rango $a[l_1 \dots r_2]$ sumando los valores de los dos nodos.

Nótese que un vértice es un “vértice hoja” si su segmento correspondiente cubre solo un valor del arreglo original. Está presente en el nivel más bajo de un Árbol de Segmentos. Su valor sería igual al elemento (correspondiente) $a[i]$ .

Ahora, para la construcción del Árbol de Segmentos, empezamos en el nivel de abajo (los vértices hoja) y les asignamos sus valores respectivos. Sobre la base de estos valores, podemos calcular los valores del nivel anterior, usando la función merge. Y sobre la base de esos, podemos calcular los valores del anterior, y repetir el procedimiento hasta llegar al vértice raíz.

Es conveniente describir esta operación de forma recursiva en la otra dirección, es decir, desde el vértice raíz hacia los vértices hoja. El procedimiento de construcción, si se llama sobre un vértice que no es hoja, hace lo siguiente:

construir recursivamente los valores de los dos vértices hijos
fusionar los valores calculados de esos hijos.

Empezamos la construcción en el vértice raíz y, por tanto, podemos calcular todo el Árbol de Segmentos.

La complejidad temporal de esta construcción es $O(n)$ , suponiendo que la operación de merge toma tiempo constante (la operación de merge se llama $n$ veces, que es igual al número de nodos internos del Árbol de Segmentos).

Consultas de suma

Por ahora vamos a responder consultas de suma. Como entrada recibimos dos enteros $l$ y $r$ , y tenemos que calcular la suma del segmento $a[l \dots r]$ en tiempo $O(\log n)$ .

Para ello, recorreremos el Árbol de Segmentos y usaremos las sumas precomputadas de los segmentos. Supongamos que estamos actualmente en el vértice que cubre el segmento $a[tl \dots tr]$ . Hay tres casos posibles.

El caso más fácil es cuando el segmento $a[l \dots r]$ es igual al segmento correspondiente del vértice actual (es decir, $a[l \dots r] = a[tl \dots tr]$ ); entonces hemos terminado y podemos devolver la suma precomputada que está guardada en el vértice.

Como alternativa, el segmento de la consulta puede caer por completo en el dominio del hijo izquierdo o del hijo derecho. Recordemos que el hijo izquierdo cubre el segmento $a[tl \dots tm]$ y el vértice derecho cubre el segmento $a[tm + 1 \dots tr]$ con $tm = (tl + tr) / 2$ . En este caso podemos simplemente ir al vértice hijo cuyo segmento correspondiente cubre el segmento de la consulta, y ejecutar el algoritmo descrito aquí con ese vértice.

Y luego está el último caso: el segmento de la consulta intersecta con ambos hijos. En este caso no tenemos otra opción que hacer dos llamadas recursivas, una para cada hijo. Primero vamos al hijo izquierdo, calculamos una respuesta parcial para este vértice (es decir, la suma de los valores de la intersección entre el segmento de la consulta y el segmento del hijo izquierdo), luego vamos al hijo derecho, calculamos la respuesta parcial usando ese vértice, y después combinamos las respuestas sumándolas. En otras palabras, como el hijo izquierdo representa el segmento $a[tl \dots tm]$ y el hijo derecho el segmento $a[tm+1 \dots tr]$ , calculamos la consulta de suma $a[l \dots tm]$ usando el hijo izquierdo, y la consulta de suma $a[tm+1 \dots r]$ usando el hijo derecho.

Así, procesar una consulta de suma es una función que se llama a sí misma de forma recursiva una vez con el hijo izquierdo o con el derecho (sin cambiar los extremos de la consulta), o dos veces, una para el izquierdo y una para el derecho (partiendo la consulta en dos subconsultas). Y la recursión termina cuando los extremos del segmento de consulta actual coinciden con los extremos del segmento del vértice actual. En ese caso la respuesta será el valor precomputado de la suma de este segmento, que está guardado en el árbol.

En otras palabras, el cálculo de la consulta es un recorrido del árbol, que se extiende por todas las ramas necesarias del árbol, y usa los valores de suma precomputados de los segmentos en el árbol.

Obviamente empezaremos el recorrido desde el vértice raíz del Árbol de Segmentos.

El procedimiento se ilustra en la siguiente imagen. Otra vez se usa el arreglo $a = [1, 3, -2, 8, -7]$ , y aquí queremos calcular la suma $\sum_{i=2}^4 a[i]$ . Se visitarán los vértices coloreados, y usaremos los valores precomputados de los vértices verdes. Esto nos da el resultado $-2 + 1 = -1$ .

"Consulta en un Árbol de Segmentos de suma"

¿Por qué la complejidad de este algoritmo es $O(\log n)$ ? Para mostrar esta complejidad miramos cada nivel del árbol. Resulta que en cada nivel visitamos no más de cuatro vértices. Y como la altura del árbol es $O(\log n)$ , obtenemos el tiempo de ejecución deseado.

Podemos mostrar que esta proposición (a lo sumo cuatro vértices en cada nivel) es cierta por inducción. En el primer nivel solo visitamos un vértice, el vértice raíz, así que aquí visitamos menos de cuatro vértices. Ahora miremos un nivel arbitrario. Por hipótesis de inducción, visitamos a lo sumo cuatro vértices. Si solo visitamos a lo sumo dos vértices, el siguiente nivel tiene a lo sumo cuatro vértices. Eso es trivial, porque cada vértice solo puede provocar a lo sumo dos llamadas recursivas. Así que supongamos que visitamos tres o cuatro vértices en el nivel actual. De esos vértices, analizaremos con más cuidado los vértices del medio. Como la consulta de suma pide la suma de un subarreglo continuo, sabemos que los segmentos correspondientes a los vértices visitados del medio estarán completamente cubiertos por el segmento de la consulta de suma. Por lo tanto estos vértices no harán ninguna llamada recursiva. Así que solo el vértice más a la izquierda y el más a la derecha tendrán el potencial de hacer llamadas recursivas. Y esos solo crearán a lo sumo cuatro llamadas recursivas, así que también el siguiente nivel satisfará la afirmación. Podemos decir que una rama se aproxima al extremo izquierdo de la consulta, y la segunda rama se aproxima al derecho.

Por lo tanto visitamos a lo sumo $4 \log n$ vértices en total, y eso equivale a un tiempo de ejecución de $O(\log n)$ .

En conclusión, la consulta funciona partiendo el segmento de entrada en varios subsegmentos para los cuales todas las sumas ya están precomputadas y guardadas en el árbol. Y si dejamos de partir cuando el segmento de la consulta coincide con el segmento del vértice, entonces solo necesitamos $O(\log n)$ de esos segmentos, lo que da la efectividad del Árbol de Segmentos.

Consultas de actualización

Ahora queremos modificar un elemento específico del arreglo; digamos que queremos hacer la asignación $a[i] = x$ . Y tenemos que reconstruir el Árbol de Segmentos de modo que corresponda al arreglo nuevo, modificado.

Esta consulta es más fácil que la consulta de suma. Cada nivel de un Árbol de Segmentos forma una partición del arreglo. Por lo tanto un elemento $a[i]$ solo contribuye a un segmento de cada nivel. Así que solo hay que actualizar $O(\log n)$ vértices.

Es fácil ver que la petición de actualización se puede implementar usando una función recursiva. La función recibe el vértice actual del árbol, y se llama a sí misma de forma recursiva con uno de los dos vértices hijos (el que contiene $a[i]$ en su segmento), y después de eso recomputa su valor de suma, de forma similar a como se hace en el método de construcción (es decir, como la suma de sus dos hijos).

Otra vez aquí hay una visualización usando el mismo arreglo. Aquí realizamos la actualización $a[2] = 3$ . Los vértices verdes son los que visitamos y actualizamos.

"Actualización en un Árbol de Segmentos de suma"

Implementación ### { #implementation}

La consideración principal es cómo guardar el Árbol de Segmentos. Por supuesto podemos definir un struct $\text{Vertex}$ y crear objetos que guarden los extremos del segmento, su suma y además punteros a sus vértices hijos. Sin embargo, esto requiere guardar mucha información redundante en forma de punteros. Usaremos un truco simple para hacerlo mucho más eficiente usando una estructura de datos implícita: guardar solo las sumas en un arreglo. (Se usa un método similar para heaps binarios). La suma del vértice raíz en el índice 1, las sumas de sus dos vértices hijos en los índices 2 y 3, las sumas de los hijos de esos dos vértices en los índices 4 a 7, y así sucesivamente. Con indexación desde uno, de forma conveniente el hijo izquierdo de un vértice en el índice $i$ se guarda en el índice $2i$ , y el derecho en el índice $2i + 1$ . De forma equivalente, el padre de un vértice en el índice $i$ se guarda en $i/2$ (división entera).

Esto simplifica mucho la implementación. No necesitamos guardar la estructura del árbol en memoria. Está definida de forma implícita. Solo necesitamos un arreglo que contiene las sumas de todos los segmentos.

Como se notó antes, hay que guardar a lo sumo $4n$ vértices. Podría ser menos, pero por conveniencia siempre asignamos un arreglo de tamaño $4n$ . Habrá algunos elementos en el arreglo de sumas que no corresponderán a ningún vértice del árbol real, pero esto no complica la implementación.

Así, guardamos el Árbol de Segmentos simplemente como un arreglo $t[]$ con un tamaño de cuatro veces el tamaño de entrada $n$ :


int n, t[4*MAXN];

El procedimiento para construir el Árbol de Segmentos a partir de un arreglo dado $a[]$ se ve así: es una función recursiva con los parámetros $a[]$ (el arreglo de entrada), $v$ (el índice del vértice actual), y los extremos $tl$ y $tr$ del segmento actual. En el programa principal esta función se llamará con los parámetros del vértice raíz: $v = 1$ , $tl = 0$ , y $tr = n - 1$ .


void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

Además, la función para responder consultas de suma también es una función recursiva, que recibe como parámetros información sobre el vértice/segmento actual (es decir, el índice $v$ y los extremos $tl$ y $tr$ ) y también la información sobre los extremos de la consulta, $l$ y $r$ . Para simplificar el código, esta función siempre hace dos llamadas recursivas, incluso si solo una es necesaria; en ese caso la llamada recursiva superflua tendrá $l > r$ , y esto se puede atrapar fácilmente con una comprobación adicional al principio de la función.


int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
           + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

Finalmente la consulta de actualización. La función también recibirá información sobre el vértice/segmento actual, y además el parámetro de la consulta de actualización (es decir, la posición del elemento y su valor nuevo).


void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = t[v*2] + t[v*2+1];
    }
}

Implementación eficiente en memoria

La mayoría de la gente usa la implementación de la sección anterior. Si se mira el arreglo t se ve que sigue la numeración de los nodos del árbol en el orden de un recorrido BFS (recorrido por niveles). Usando este recorrido, los hijos del vértice $v$ son $2v$ y $2v + 1$ respectivamente. Sin embargo, si $n$ no es una potencia de dos, este método saltará algunos índices y dejará sin usar algunas partes del arreglo t. El consumo de memoria está acotado por $4n$ , aunque un Árbol de Segmentos de un arreglo de $n$ elementos requiere solo $2n - 1$ vértices.

Sin embargo se puede reducir. Renumeramos los vértices del árbol en el orden de un recorrido de tour de Euler (recorrido preorden), y escribimos todos estos vértices uno al lado del otro.

Miremos un vértice en el índice $v$ , y sea responsable del segmento $[l, r]$ , y sea $mid = \dfrac{l + r}{2}$ . Es obvio que el hijo izquierdo tendrá el índice $v + 1$ . El hijo izquierdo es responsable del segmento $[l, mid]$ , es decir, en total habrá $2 * (mid - l + 1) - 1$ vértices en el subárbol del hijo izquierdo. Así podemos calcular el índice del hijo derecho de $v$ . El índice será $v + 2 * (mid - l + 1)$ . Con esta numeración logramos una reducción de la memoria necesaria a $2n$ .

Versiones avanzadas de Árboles de Segmentos

Un Árbol de Segmentos es una estructura de datos muy flexible, y permite variaciones y extensiones en muchas direcciones distintas. Intentemos categorizarlas abajo.

Consultas más complejas

Puede ser bastante fácil cambiar el Árbol de Segmentos en una dirección tal que calcule consultas distintas (p. ej. calcular el mínimo / máximo en lugar de la suma), pero también puede ser muy no trivial.

Encontrar el máximo

Cambiemos ligeramente la condición del problema descrito arriba: en lugar de consultar la suma, ahora haremos consultas de máximo.

El árbol tendrá exactamente la misma estructura que el árbol descrito arriba. Solo hay que cambiar la forma en que se calcula $t[v]$ en las funciones $\text{build}$ y $\text{update}$ . $t[v]$ ahora guardará el máximo del segmento correspondiente. Y también hay que cambiar el cálculo del valor de retorno de la función $\text{sum}$ (reemplazando la suma por el máximo).

Por supuesto este problema se puede cambiar fácilmente a calcular el mínimo en lugar del máximo.

En lugar de mostrar una implementación de este problema, la implementación se dará para una versión más compleja de este problema en la siguiente sección.

Encontrar el máximo y el número de veces que aparece

Esta tarea es muy similar a la anterior. Además de encontrar el máximo, también tenemos que encontrar el número de ocurrencias del máximo.

Para resolver este problema, guardamos un par de números en cada vértice del árbol: Además del máximo también guardamos el número de ocurrencias de él en el segmento correspondiente. Determinar el par correcto a guardar en $t[v]$ se puede seguir haciendo en tiempo constante usando la información de los pares guardados en los vértices hijos. Combinar dos de esos pares debería hacerse en una función separada, ya que esta será una operación que haremos al construir el árbol, al responder consultas de máximo y al realizar modificaciones.


pair<int, int> t[4*MAXN];

pair<int, int> combine(pair<int, int> a, pair<int, int> b) {
    if (a.first > b.first) 
        return a;
    if (b.first > a.first)
        return b;
    return make_pair(a.first, a.second + b.second);
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = make_pair(a[tl], 1);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

pair<int, int> get_max(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return make_pair(-INF, 0);
    if (l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(get_max(v*2, tl, tm, l, min(r, tm)), 
                   get_max(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = make_pair(new_val, 1);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

Calcular el máximo común divisor / mínimo común múltiplo

En este problema queremos calcular el GCD / LCM de todos los números de rangos dados del arreglo.

Esta variación interesante del Árbol de Segmentos se puede resolver exactamente de la misma forma que los Árboles de Segmentos que derivamos para consultas de suma / mínimo / máximo: basta con guardar el GCD / LCM del vértice correspondiente en cada vértice del árbol. Combinar dos vértices se puede hacer calculando el GCD / LCM de ambos vértices.

Contar el número de ceros, buscar el $k$ -ésimo cero { #counting-zero-search-kth data-toc-label=“Contar el número de ceros, buscar el k-ésimo cero”}

En este problema queremos encontrar el número de ceros en un rango dado, y además encontrar el índice del $k$ -ésimo cero usando una segunda función.

Otra vez hay que cambiar un poco los valores guardados del árbol: Esta vez guardaremos el número de ceros en cada segmento en $t[]$ . Queda bastante claro cómo implementar las funciones $\text{build}$ , $\text{update}$ y $\text{count_zero}$ ; podemos simplemente usar las ideas del problema de consulta de suma. Así resolvimos la primera parte del problema.

Ahora aprendemos cómo resolver el problema de encontrar el $k$ -ésimo cero en el arreglo $a[]$ . Para esta tarea, descenderemos el Árbol de Segmentos, empezando en el vértice raíz, y moviéndonos cada vez al hijo izquierdo o al derecho, según qué segmento contenga el $k$ -ésimo cero. Para decidir a qué hijo hay que ir, basta con mirar el número de ceros que aparecen en el segmento correspondiente al vértice izquierdo. Si este conteo precomputado es mayor o igual que $k$ , es necesario descender al hijo izquierdo, y en caso contrario descender al hijo derecho. Nótese que, si elegimos el hijo derecho, hay que restar de $k$ el número de ceros del hijo izquierdo.

En la implementación podemos manejar el caso especial de que $a[]$ contenga menos de $k$ ceros devolviendo -1.


int find_kth(int v, int tl, int tr, int k) {
    if (k > t[v])
        return -1;
    if (tl == tr)
        return tl;
    int tm = (tl + tr) / 2;
    if (t[v*2] >= k)
        return find_kth(v*2, tl, tm, k);
    else 
        return find_kth(v*2+1, tm+1, tr, k - t[v*2]);
}

Buscar un prefijo del arreglo con una cantidad dada

La tarea es la siguiente: para un valor dado $x$ hay que encontrar rápido el menor índice $i$ tal que la suma de los primeros $i$ elementos del arreglo $a[]$ es mayor o igual que $x$ (suponiendo que el arreglo $a[]$ solo contiene valores no negativos).

Esta tarea se puede resolver usando búsqueda binaria, calculando la suma de los prefijos con el Árbol de Segmentos. Sin embargo esto llevará a una solución $O(\log^2 n)$ .

En su lugar podemos usar la misma idea que en la sección anterior, y encontrar la posición descendiendo el árbol: moviéndonos cada vez a la izquierda o a la derecha, según la suma del hijo izquierdo. Así encontramos la respuesta en tiempo $O(\log n)$ .

Buscar el primer elemento mayor que una cantidad dada

La tarea es la siguiente: para un valor dado $x$ y un rango $a[l \dots r]$ encontrar el menor $i$ en el rango $a[l \dots r]$ tal que $a[i]$ es mayor que $x$ .

Esta tarea se puede resolver usando búsqueda binaria sobre consultas de máximo de prefijos con el Árbol de Segmentos. Sin embargo, esto llevará a una solución $O(\log^2 n)$ .

En su lugar, podemos usar la misma idea que en las secciones anteriores, y encontrar la posición descendiendo el árbol: moviéndonos cada vez a la izquierda o a la derecha, según el valor máximo del hijo izquierdo. Así encontramos la respuesta en tiempo $O(\log n)$ .


int get_first(int v, int tl, int tr, int l, int r, int x) {
    if(tl > r || tr < l) return -1;
    if(t[v] <= x) return -1;
    
    if (tl== tr) return tl;
    
    int tm = tl + (tr-tl)/2;
    int left = get_first(2*v, tl, tm, l, r, x);
    if(left != -1) return left;
    return get_first(2*v+1, tm+1, tr, l ,r, x);
}

Encontrar subsegmentos con la suma máxima

Aquí otra vez recibimos un rango $a[l \dots r]$ para cada consulta; esta vez tenemos que encontrar un subsegmento $a[l^\prime \dots r^\prime]$ tal que $l \le l^\prime$ y $r^\prime \le r$ y la suma de los elementos de este segmento es máxima. Como antes también queremos poder modificar elementos individuales del arreglo. Los elementos del arreglo pueden ser negativos, y el subsegmento óptimo puede ser vacío (p. ej. si todos los elementos son negativos).

Este problema es un uso no trivial de un Árbol de Segmentos. Esta vez guardaremos cuatro valores para cada vértice: la suma del segmento, la suma de prefijo máxima, la suma de sufijo máxima, y la suma del subsegmento maximal en él. En otras palabras, para cada segmento del Árbol de Segmentos la respuesta ya está precomputada, así como las respuestas para segmentos que tocan los extremos izquierdo y derecho del segmento.

¿Cómo construir un árbol con esos datos? Otra vez lo calculamos de forma recursiva: primero calculamos los cuatro valores para el hijo izquierdo y el derecho, y luego los combinamos para obtener los cuatro valores del vértice actual. Nótese que la respuesta para el vértice actual es alguna de:

la respuesta del hijo izquierdo, lo que significa que el subsegmento óptimo está colocado por completo en el segmento del hijo izquierdo
la respuesta del hijo derecho, lo que significa que el subsegmento óptimo está colocado por completo en el segmento del hijo derecho
la suma de la suma de sufijo máxima del hijo izquierdo y la suma de prefijo máxima del hijo derecho, lo que significa que el subsegmento óptimo intersecta con ambos hijos.

Por tanto la respuesta del vértice actual es el máximo de estos tres valores. Calcular la suma de prefijo / sufijo máxima es aún más fácil. Aquí está la implementación de la función $\text{combine}$ , que recibe solo datos del hijo izquierdo y del derecho, y devuelve los datos del vértice actual.


struct data {
    int sum, pref, suff, ans;
};

data combine(data l, data r) {
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
    return res;
}

Usando la función $\text{combine}$ es fácil construir el Árbol de Segmentos. Podemos implementarlo exactamente de la misma forma que en las implementaciones anteriores. Para inicializar los vértices hoja, además creamos la función auxiliar $\text{make_data}$ , que devolverá un objeto $\text{data}$ que contiene la información de un solo valor.


data make_data(int val) {
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = max(0, val);
    return res;
}

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = make_data(a[tl]);
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}
 
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = make_data(new_val);
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = combine(t[v*2], t[v*2+1]);
    }
}

Solo queda cómo calcular la respuesta a una consulta. Para responderla, bajamos por el árbol como antes, partiendo la consulta en varios subsegmentos que coinciden con los segmentos del Árbol de Segmentos, y combinamos las respuestas en ellos en una sola respuesta para la consulta. Entonces debería quedar claro que el trabajo es exactamente el mismo que en el Árbol de Segmentos simple, pero en lugar de sumar / minimizar / maximizar los valores, usamos la función $\text{combine}$ .


data query(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return make_data(0);
    if (l == tl && r == tr) 
        return t[v];
    int tm = (tl + tr) / 2;
    return combine(query(v*2, tl, tm, l, min(r, tm)), 
                   query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

Guardar los subarreglos enteros en cada vértice

Esta es una subsección aparte que se distingue de las demás, porque en cada vértice del Árbol de Segmentos no guardamos información sobre el segmento correspondiente en forma comprimida (suma, mínimo, máximo, …), sino que guardamos todos los elementos del segmento. Así la raíz del Árbol de Segmentos guardará todos los elementos del arreglo, el vértice hijo izquierdo guardará la primera mitad del arreglo, el vértice derecho la segunda mitad, y así sucesivamente.

En su aplicación más simple de esta técnica guardamos los elementos en orden ordenado. En versiones más complejas los elementos no se guardan en listas, sino en estructuras de datos más avanzadas (conjuntos, mapas, …). Pero todos estos métodos tienen el factor común de que cada vértice requiere memoria lineal (es decir, proporcional a la longitud del segmento correspondiente).

La primera pregunta natural, al considerar estos Árboles de Segmentos, es sobre el consumo de memoria. Intuitivamente esto podría parecer memoria $O(n^2)$ , pero resulta que el árbol completo solo necesitará memoria $O(n \log n)$ . ¿Por qué es así? Sencillamente, porque cada elemento del arreglo cae en $O(\log n)$ segmentos (recordemos que la altura del árbol es $O(\log n)$ ).

Así, a pesar de la aparente extravagancia de un Árbol de Segmentos de este tipo, consume solo un poco más de memoria que el Árbol de Segmentos usual.

Más abajo se describen varias aplicaciones típicas de esta estructura de datos. Vale la pena notar la similitud de estos Árboles de Segmentos con estructuras de datos 2D (de hecho esta es una estructura de datos 2D, pero con capacidades bastante limitadas).

Encontrar el menor número mayor o igual que un número especificado. Sin consultas de modificación.

Queremos responder consultas de la siguiente forma: para tres números dados $(l, r, x)$ hay que encontrar el número mínimo en el segmento $a[l \dots r]$ que es mayor o igual que $x$ .

Construimos un Árbol de Segmentos. En cada vértice guardamos una lista ordenada de todos los números que ocurren en el segmento correspondiente, como se describió arriba. ¿Cómo construir un Árbol de Segmentos de este tipo de la forma más efectiva posible? Como siempre abordamos este problema de forma recursiva: supongamos que las listas de los hijos izquierdo y derecho ya están construidas, y queremos construir la lista para el vértice actual. Desde este punto de vista la operación ahora es trivial y se puede completar en tiempo lineal: Solo hay que combinar las dos listas ordenadas en una, lo cual se puede hacer recorriéndolas con dos punteros. La STL de C++ ya tiene una implementación de este algoritmo.

Por esta estructura del Árbol de Segmentos y las similitudes con el algoritmo mergesort, la estructura de datos también se llama a menudo “Merge Sort Tree”.


vector<int> t[4*MAXN];

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = vector<int>(1, a[tl]);
    } else { 
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
              back_inserter(t[v]));
    }
}

Ya sabemos que el Árbol de Segmentos construido de esta forma requerirá memoria $O(n \log n)$ . Y gracias a esta implementación su construcción también toma tiempo $O(n \log n)$ , después de todo cada lista se construye en tiempo lineal respecto de su tamaño.

Ahora consideremos la respuesta a la consulta. Bajaremos por el árbol, como en el Árbol de Segmentos regular, partiendo nuestro segmento $a[l \dots r]$ en varios subsegmentos (en a lo sumo $O(\log n)$ pedazos). Es claro que la respuesta de toda la consulta es el mínimo de cada una de las subconsultas. Así que ahora solo hay que entender cómo responder a una consulta sobre un subsegmento de ese tipo que corresponde con algún vértice del árbol.

Estamos en algún vértice del Árbol de Segmentos y queremos calcular la respuesta a la consulta, es decir, encontrar el número mínimo mayor o igual que un número dado $x$ . Como el vértice contiene la lista de elementos en orden ordenado, podemos simplemente hacer una búsqueda binaria sobre esta lista y devolver el primer número mayor o igual que $x$ .

Así, la respuesta a la consulta en un segmento del árbol toma tiempo $O(\log n)$ , y toda la consulta se procesa en $O(\log^2 n)$ .


int query(int v, int tl, int tr, int l, int r, int x) {
    if (l > r)
        return INF;
    if (l == tl && r == tr) {
        vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
        if (pos != t[v].end())
            return *pos;
        return INF;
    }
    int tm = (tl + tr) / 2;
    return min(query(v*2, tl, tm, l, min(r, tm), x), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r, x));
}

La constante $\text{INF}$ es igual a algún número grande que es mayor que todos los números del arreglo. Su uso significa que no hay ningún número mayor o igual que $x$ en el segmento. Tiene el significado de “no hay respuesta en el intervalo dado”.

Encontrar el menor número mayor o igual que un número especificado. Con consultas de modificación.

Esta tarea es similar a la anterior. El último enfoque tiene una desventaja: no era posible modificar el arreglo entre respuestas a consultas. Ahora queremos hacer exactamente esto: una consulta de modificación hará la asignación $a[i] = y$ .

La solución es similar a la solución del problema anterior, pero en lugar de listas en cada vértice del Árbol de Segmentos, guardaremos una lista balanceada que permite buscar números, borrar números e insertar números nuevos de forma rápida. Como el arreglo puede contener un número repetido, la elección óptima es la estructura de datos $\text{multiset}$ .

La construcción de un Árbol de Segmentos de este tipo se hace prácticamente de la misma forma que en el problema anterior, solo que ahora hay que combinar $\text{multiset}$ s y no listas ordenadas. Esto lleva a un tiempo de construcción de $O(n \log^2 n)$ (en general fusionar dos árboles rojo-negro se puede hacer en tiempo lineal, pero la STL de C++ no garantiza esta complejidad temporal).

La función $\text{query}$ también es casi equivalente, solo que ahora hay que llamar a la función $\text{lower_bound}$ del $\text{multiset}$ ( $\text{std::lower_bound}$ solo funciona en tiempo $O(\log n)$ si se usa con iteradores de acceso aleatorio).

Finalmente la petición de modificación. Para procesarla, hay que bajar por el árbol y modificar todos los $\text{multiset}$ de los segmentos correspondientes que contienen el elemento afectado. Simplemente borramos el valor viejo de este elemento (pero solo una ocurrencia), e insertamos el valor nuevo.


void update(int v, int tl, int tr, int pos, int new_val) {
    t[v].erase(t[v].find(a[pos]));
    t[v].insert(new_val);
    if (tl != tr) {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
    } else {
        a[pos] = new_val;
    }
}

El procesamiento de esta consulta de modificación también toma tiempo $O(\log^2 n)$ .

Encontrar el menor número mayor o igual que un número especificado. Aceleración con “cascada fraccionaria” (fractional cascading).

Tenemos el mismo enunciado del problema: queremos encontrar el número mínimo mayor o igual que $x$ en un segmento, pero esta vez en tiempo $O(\log n)$ . Mejoraremos la complejidad temporal usando la técnica de cascada fraccionaria (fractional cascading).

La cascada fraccionaria es una técnica simple que permite mejorar el tiempo de ejecución de múltiples búsquedas binarias, que se realizan al mismo tiempo. Nuestro enfoque anterior a la consulta de búsqueda era que partíamos la tarea en varias subtareas, cada una de las cuales se resuelve con una búsqueda binaria. La cascada fraccionaria permite reemplazar todas estas búsquedas binarias por una sola.

El ejemplo más simple y más obvio de cascada fraccionaria es el siguiente problema: hay $k$ listas ordenadas de números, y hay que encontrar en cada lista el primer número mayor o igual que el número dado.

En lugar de hacer una búsqueda binaria para cada lista, podríamos fusionar todas las listas en una gran lista ordenada. Además, para cada elemento $y$ guardamos una lista de resultados de buscar $y$ en cada una de las $k$ listas. Por lo tanto, si queremos encontrar el menor número mayor o igual que $x$ , solo hay que hacer una sola búsqueda binaria, y a partir de la lista de índices podemos determinar el menor número en cada lista. Sin embargo este enfoque requiere $O(n \cdot k)$ ( $n$ es la longitud de las listas combinadas), lo cual puede ser bastante ineficiente.

La cascada fraccionaria reduce esta complejidad de memoria a memoria $O(n)$ , creando a partir de las $k$ listas de entrada $k$ listas nuevas, en las que cada lista contiene la lista correspondiente y además también cada segundo elemento de la siguiente lista nueva. Usando esta estructura solo es necesario guardar dos índices, el índice del elemento en la lista original, y el índice del elemento en la siguiente lista nueva. Así este enfoque solo usa memoria $O(n)$ , y aún puede responder las consultas usando una sola búsqueda binaria.

Pero para nuestra aplicación no necesitamos toda la potencia de la cascada fraccionaria. En nuestro Árbol de Segmentos un vértice contendrá la lista ordenada de todos los elementos que ocurren en el subárbol izquierdo o en el derecho (como en el Merge Sort Tree). Además de esta lista ordenada, guardamos dos posiciones para cada elemento. Para un elemento $y$ guardamos el menor índice $i$ tal que el $i$ -ésimo elemento en la lista ordenada del hijo izquierdo es mayor o igual que $y$ . Y guardamos el menor índice $j$ tal que el $j$ -ésimo elemento en la lista ordenada del hijo derecho es mayor o igual que $y$ . Estos valores se pueden calcular en paralelo al paso de fusión cuando construimos el árbol.

¿Cómo acelera esto las consultas?

Recordemos que, en la solución normal, hacíamos una búsqueda binaria en cada nodo. Pero con esta modificación, podemos evitar todas excepto una.

Para responder una consulta, simplemente hacemos una búsqueda binaria en el nodo raíz. Esto nos da el menor elemento $y \ge x$ en el arreglo completo, pero también nos da dos posiciones. El índice del menor elemento mayor o igual que $x$ en el subárbol izquierdo, y el índice del menor elemento $y$ en el subárbol derecho. Nótese que $\ge y$ es lo mismo que $\ge x$ , ya que nuestro arreglo no contiene ningún elemento entre $x$ e $y$ . En la solución normal del Merge Sort Tree calcularíamos estos índices vía búsqueda binaria, pero con la ayuda de los valores precomputados podemos simplemente consultarlos en $O(1)$ . Y podemos repetir eso hasta haber visitado todos los nodos que cubren nuestro intervalo de consulta.

Para resumir, como es usual tocamos $O(\log n)$ nodos durante una consulta. En el nodo raíz hacemos una búsqueda binaria, y en todos los demás nodos solo hacemos trabajo constante. Esto significa que la complejidad para responder una consulta es $O(\log n)$ .

Pero nótese que esto usa tres veces más memoria que un Merge Sort Tree normal, que ya usa mucha memoria ( $O(n \log n)$ ).

Es directo aplicar esta técnica a un problema que no requiere consultas de modificación. Las dos posiciones son simplemente enteros y se pueden calcular fácilmente contando al fusionar las dos secuencias ordenadas.

Todavía es posible también permitir consultas de modificación, pero eso complica todo el código. En lugar de enteros, hay que guardar el arreglo ordenado como multiset, y en lugar de índices hay que guardar iteradores. Y hay que trabajar con mucho cuidado, para incrementar o decrementar los iteradores correctos durante una consulta de modificación.

Otras variaciones posibles

Esta técnica implica toda una clase nueva de aplicaciones posibles. En lugar de guardar un $\text{vector}$ o un $\text{multiset}$ en cada vértice, se pueden usar otras estructuras de datos: otros Árboles de Segmentos (algo discutido en Generalización a dimensiones superiores), Árboles de Fenwick, árboles cartesianos, etc.

Actualizaciones de rango (propagación perezosa)

Todos los problemas de las secciones de arriba discutieron consultas de modificación que solo afectaban un solo elemento del arreglo cada una. Sin embargo el Árbol de Segmentos permite aplicar consultas de modificación a todo un segmento de elementos contiguos, y realizar la consulta en el mismo tiempo $O(\log n)$ .

Suma sobre segmentos

Empezamos considerando problemas de la forma más simple: la consulta de modificación debe sumar un número $x$ a todos los números del segmento $a[l \dots r]$ . La segunda consulta, que se supone que debemos responder, pide simplemente el valor de $a[i]$ .

Para hacer eficiente la consulta de suma, guardamos en cada vértice del Árbol de Segmentos cuánto debemos sumar a todos los números del segmento correspondiente. Por ejemplo, si llega la consulta “sumar 3 a todo el arreglo $a[0 \dots n-1]$ ”, entonces colocamos el número 3 en la raíz del árbol. En general tenemos que colocar este número en múltiples segmentos, que forman una partición del segmento de la consulta. Así no tenemos que cambiar todos los $O(n)$ valores, sino solo $O(\log n)$ de ellos.

Si ahora llega una consulta que pide el valor actual de una entrada particular del arreglo, basta con bajar por el árbol y sumar todos los valores encontrados por el camino.


void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = 0;
    }
}
 
void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r)
        return;
    if (l == tl && r == tr) {
        t[v] += add;
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), add);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, add);
    }
}
 
int get(int v, int tl, int tr, int pos) {
    if (tl == tr)
        return t[v];
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return t[v] + get(v*2, tl, tm, pos);
    else
        return t[v] + get(v*2+1, tm+1, tr, pos);
}

Asignación sobre segmentos

Supongamos ahora que la consulta de modificación pide asignar a cada elemento de un cierto segmento $a[l \dots r]$ algún valor $p$ . Como segunda consulta otra vez consideraremos leer el valor del arreglo $a[i]$ .

Para realizar esta consulta de modificación sobre todo un segmento, hay que guardar en cada vértice del Árbol de Segmentos si el segmento correspondiente está cubierto por completo con el mismo valor o no. Esto nos permite hacer una actualización “perezosa”: en lugar de cambiar todos los segmentos del árbol que cubren el segmento de la consulta, solo cambiamos algunos, y dejamos otros sin cambiar. Un vértice marcado significará que cada elemento del segmento correspondiente está asignado a ese valor, y de hecho también el subárbol completo debería contener solo este valor. En cierto sentido somos perezosos y retrasamos escribir el valor nuevo en todos esos vértices. Podemos hacer esta tarea tediosa más tarde, si es necesario.

Así, después de ejecutar la consulta de modificación, algunas partes del árbol se vuelven irrelevantes: algunas modificaciones quedan sin cumplir en él.

Por ejemplo, si se ejecuta una consulta de modificación “asignar un número a todo el arreglo $a[0 \dots n-1]$ ”, en el Árbol de Segmentos solo se hace un solo cambio: el número se coloca en la raíz del árbol y este vértice se marca. Los segmentos restantes quedan sin cambiar, aunque de hecho el número debería colocarse en todo el árbol.

Supongamos ahora que la segunda consulta de modificación dice que la primera mitad del arreglo $a[0 \dots n/2]$ debería asignarse con algún otro número. Para procesar esta consulta debemos asignar a cada elemento de todo el hijo izquierdo del vértice raíz ese número. Pero antes de hacer esto, primero debemos ordenar el vértice raíz. La sutileza aquí es que la mitad derecha del arreglo todavía debería estar asignada al valor de la primera consulta, y en este momento no hay información guardada para la mitad derecha.

La forma de resolver esto es empujar la información de la raíz a sus hijos, es decir, si la raíz del árbol estaba asignada con algún número, entonces asignamos a los vértices hijos izquierdo y derecho este número y quitamos la marca de la raíz. Después de eso, podemos asignar al hijo izquierdo el valor nuevo, sin perder ninguna información necesaria.

Resumiendo obtenemos: para cualquier consulta (de modificación o de lectura) durante el descenso a lo largo del árbol siempre debemos empujar información del vértice actual a ambos de sus hijos. Podemos entender esto de esta forma: cuando descendemos el árbol aplicamos modificaciones retrasadas, pero exactamente las necesarias (para no degradar la complejidad de $O(\log n)$ ).

Para la implementación necesitamos hacer una función $\text{push}$ , que recibirá el vértice actual, y empujará la información de su vértice a ambos de sus hijos. Llamaremos a esta función al principio de las funciones de consulta (pero no la llamaremos desde las hojas, porque no hay necesidad de empujar información de ellas más adelante).


void push(int v) {
    if (marked[v]) {
        t[v*2] = t[v*2+1] = t[v];
        marked[v*2] = marked[v*2+1] = true;
        marked[v] = false;
    }
}
 
void update(int v, int tl, int tr, int l, int r, int new_val) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] = new_val;
        marked[v] = true;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), new_val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
    }
}
 
int get(int v, int tl, int tr, int pos) {
    if (tl == tr) {
        return t[v];
    }
    push(v);
    int tm = (tl + tr) / 2;
    if (pos <= tm) 
        return get(v*2, tl, tm, pos);
    else
        return get(v*2+1, tm+1, tr, pos);
}

Nótese: la función $\text{get}$ también se puede implementar de otra forma: no hacer actualizaciones retrasadas, sino devolver inmediatamente el valor $t[v]$ si $marked[v]$ es true.

Suma sobre segmentos, consulta de máximo

Ahora la consulta de modificación es sumar un número a todos los elementos de un rango, y la consulta de lectura es encontrar el máximo en un rango.

Así, para cada vértice del Árbol de Segmentos tenemos que guardar el máximo del subsegmento correspondiente. La parte interesante es cómo recomputar estos valores durante una petición de modificación.

Para este propósito guardamos un valor adicional para cada vértice. En este valor guardamos los sumandos que no hemos propagado a los vértices hijos. Antes de recorrer hacia un vértice hijo, llamamos $\text{push}$ y propagamos el valor a ambos hijos. Tenemos que hacer esto tanto en la función $\text{update}$ como en la función $\text{query}$ .


void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        t[v] = max(t[v*2], t[v*2 + 1]);
    }
}
 
void push(int v) {
    t[v*2] += lazy[v];
    lazy[v*2] += lazy[v];
    t[v*2+1] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}
 
void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}
 
int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return -INF;
    if (l == tl && tr == r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

Generalización a dimensiones superiores

Un Árbol de Segmentos se puede generalizar de forma bastante natural a dimensiones superiores. Si en el caso unidimensional partimos los índices del arreglo en segmentos, entonces en el bidimensional hacemos un Árbol de Segmentos ordinario respecto de los primeros índices, y para cada segmento construimos un Árbol de Segmentos ordinario respecto de los segundos índices.

Árbol de Segmentos 2D simple

Se da una matriz $a[0 \dots n-1, 0 \dots m-1]$ , y tenemos que encontrar la suma (o el mínimo/máximo) sobre alguna submatriz $a[x_1 \dots x_2, y_1 \dots y_2]$ , además de realizar modificaciones de elementos individuales de la matriz (es decir, consultas de la forma $a[x][y] = p$ ).

Así construimos un Árbol de Segmentos 2D: primero el Árbol de Segmentos usando la primera coordenada ( $x$ ), luego la segunda ( $y$ ).

Para hacer el proceso de construcción más comprensible, se puede olvidar por un rato que la matriz es bidimensional, y dejar solo la primera coordenada. Construiremos un Árbol de Segmentos unidimensional ordinario usando solo la primera coordenada. Pero en lugar de guardar un número en un segmento, guardamos un Árbol de Segmentos entero: es decir, en este momento recordamos que también tenemos una segunda coordenada; pero como en este momento la primera coordenada ya está fijada a algún intervalo $[l \dots r]$ , de hecho trabajamos con una franja $a[l \dots r, 0 \dots m-1]$ y para ella construimos un Árbol de Segmentos.

Aquí está la implementación de la construcción de un Árbol de Segmentos 2D. De hecho representa dos bloques separados: la construcción de un Árbol de Segmentos a lo largo de la coordenada $x$ ( $\text{build}_x$ ), y la coordenada $y$ ( $\text{build}_y$ ). Para los nodos hoja en $\text{build}_y$ hay que separar dos casos: cuando el segmento actual de la primera coordenada $[tlx \dots trx]$ tiene longitud 1, y cuando tiene longitud mayor que uno. En el primer caso, simplemente tomamos el valor correspondiente de la matriz, y en el segundo caso podemos combinar los valores de dos Árboles de Segmentos del hijo izquierdo y del derecho en la coordenada $x$ .


void build_y(int vx, int lx, int rx, int vy, int ly, int ry) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = a[lx][ly];
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
    } else {
        int my = (ly + ry) / 2;
        build_y(vx, lx, rx, vy*2, ly, my);
        build_y(vx, lx, rx, vy*2+1, my+1, ry);
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
    }
}
 
void build_x(int vx, int lx, int rx) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        build_x(vx*2, lx, mx);
        build_x(vx*2+1, mx+1, rx);
    }
    build_y(vx, lx, rx, 1, 0, m-1);
}

Un Árbol de Segmentos de este tipo todavía usa una cantidad lineal de memoria, pero con una constante mayor: $16 n m$ . Es claro que el procedimiento descrito $\text{build}_x$ también funciona en tiempo lineal.

Ahora pasamos al procesamiento de consultas. Responderemos a la consulta bidimensional usando el mismo principio: primero partimos la consulta en la primera coordenada, y luego para cada vértice alcanzado, llamamos al Árbol de Segmentos correspondiente de la segunda coordenada.


int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry) 
        return 0;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         + sum_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry);
}
 
int sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return sum_y(vx, 1, 0, m-1, ly, ry);
    int tmx = (tlx + trx) / 2;
    return sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         + sum_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry);
}

Esta función funciona en tiempo $O(\log n \log m)$ , ya que primero desciende el árbol en la primera coordenada, y para cada vértice recorrido en el árbol hace una consulta en el Árbol de Segmentos correspondiente a lo largo de la segunda coordenada.

Finalmente consideramos la consulta de modificación. Queremos aprender cómo modificar el Árbol de Segmentos de acuerdo con el cambio en el valor de algún elemento $a[x][y] = p$ . Es claro que los cambios ocurrirán solo en aquellos vértices del primer Árbol de Segmentos que cubren la coordenada $x$ (y tales serán $O(\log n)$ ), y para los Árboles de Segmentos correspondientes a ellos los cambios solo ocurrirán en aquellos vértices que cubren la coordenada $y$ (y tales serán $O(\log m)$ ). Por lo tanto la implementación no será muy distinta del caso unidimensional, solo que ahora primero descendemos la primera coordenada, y luego la segunda.


void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
        t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
    }
}
 
void update_x(int vx, int lx, int rx, int x, int y, int new_val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx+1, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val);
}

Compresión del Árbol de Segmentos 2D

Sea el problema el siguiente: hay $n$ puntos en el plano dados por sus coordenadas $(x_i, y_i)$ y consultas de la forma “contar el número de puntos que yacen en el rectángulo $((x_1, y_1), (x_2, y_2))$ ”. Es claro que en el caso de un problema de este tipo se vuelve irrazonablemente derrochador construir un Árbol de Segmentos bidimensional con $O(n^2)$ elementos. La mayor parte de esta memoria se desperdiciará, ya que cada punto individual solo puede entrar en $O(\log n)$ segmentos del árbol a lo largo de la primera coordenada, y por tanto el tamaño total “útil” de todos los segmentos del árbol en la segunda coordenada es $O(n \log n)$ .

Así procedemos de la siguiente forma: en cada vértice del Árbol de Segmentos respecto de la primera coordenada guardamos un Árbol de Segmentos construido solo con aquellas segundas coordenadas que ocurren en el segmento actual de las primeras coordenadas. En otras palabras, al construir un Árbol de Segmentos dentro de algún vértice con índice $vx$ y los extremos $tlx$ y $trx$ , solo consideramos aquellos puntos que caen en este intervalo $x \in [tlx, trx]$ , y construimos un Árbol de Segmentos solo usándolos.

Así lograremos que cada Árbol de Segmentos en la segunda coordenada ocupe exactamente tanta memoria como debería. Como resultado, la cantidad total de memoria disminuirá a $O(n \log n)$ . Todavía podemos responder las consultas en tiempo $O(\log^2 n)$ ; solo hay que hacer una búsqueda binaria en la segunda coordenada, pero esto no empeorará la complejidad.

Pero las consultas de modificación serán imposibles con esta estructura: de hecho, si aparece un punto nuevo, hay que agregar un elemento nuevo en el medio de algún Árbol de Segmentos a lo largo de la segunda coordenada, lo cual no se puede hacer de forma efectiva.

Para concluir notamos que el Árbol de Segmentos bidimensional construido de la forma descrita se vuelve prácticamente equivalente a la modificación del Árbol de Segmentos unidimensional (véase Guardar los subarreglos enteros en cada vértice). En particular el Árbol de Segmentos bidimensional es solo un caso especial de guardar un subarreglo en cada vértice del árbol. Se sigue que, si hay que abandonar un Árbol de Segmentos bidimensional por la imposibilidad de ejecutar una consulta, tiene sentido intentar reemplazar el Árbol de Segmentos anidado por alguna estructura de datos más poderosa, por ejemplo un árbol cartesiano.

Preservar la historia de sus valores (Árbol de Segmentos Persistente)

Una estructura de datos persistente es una estructura de datos que recuerda su estado anterior para cada modificación. Esto permite acceder a cualquier versión de esta estructura de datos que nos interese y ejecutar una consulta sobre ella.

El Árbol de Segmentos es una estructura de datos que se puede convertir en una estructura de datos persistente de forma eficiente (tanto en tiempo como en consumo de memoria). Queremos evitar copiar el árbol completo antes de cada modificación, y no queremos perder el comportamiento de tiempo $O(\log n)$ para responder consultas de rango.

De hecho, cualquier petición de cambio en el Árbol de Segmentos lleva a un cambio en los datos de solo $O(\log n)$ vértices a lo largo del camino que empieza en la raíz. Así que si guardamos el Árbol de Segmentos usando punteros (es decir, un vértice guarda punteros a los vértices hijos izquierdo y derecho), entonces al realizar la consulta de modificación, simplemente hay que crear vértices nuevos en lugar de cambiar los vértices disponibles. Los vértices que no se ven afectados por la consulta de modificación todavía se pueden usar apuntando los punteros a los vértices viejos. Así, para una consulta de modificación se crearán $O(\log n)$ vértices nuevos, incluyendo un vértice raíz nuevo del Árbol de Segmentos, y toda la versión anterior del árbol enraizado en el vértice raíz viejo permanecerá sin cambios.

Demos un ejemplo de implementación para el Árbol de Segmentos más simple: cuando solo hay una consulta que pide sumas, y consultas de modificación de elementos individuales.


struct Vertex {
    Vertex *l, *r;
    int sum;
 
    Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }
};
 
Vertex* build(int a[], int tl, int tr) {
    if (tl == tr)
        return new Vertex(a[tl]);
    int tm = (tl + tr) / 2;
    return new Vertex(build(a, tl, tm), build(a, tm+1, tr));
}
 
int get_sum(Vertex* v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l == tl && tr == r)
        return v->sum;
    int tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, min(r, tm))
         + get_sum(v->r, tm+1, tr, max(l, tm+1), r);
}
 
Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) {
    if (tl == tr)
        return new Vertex(new_val);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos, new_val), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos, new_val));
}

Para cada modificación del Árbol de Segmentos recibiremos un vértice raíz nuevo. Para saltar rápido entre dos versiones distintas del Árbol de Segmentos, hay que guardar estas raíces en un arreglo. Para usar una versión específica del Árbol de Segmentos simplemente llamamos a la consulta usando el vértice raíz apropiado.

Con el enfoque descrito arriba casi cualquier Árbol de Segmentos se puede convertir en una estructura de datos persistente.

Encontrar el $k$ -ésimo número más pequeño en un rango {data-toc-label=“Encontrar el k-ésimo número más pequeño en un rango”}

Esta vez tenemos que responder consultas de la forma “¿Cuál es el $k$ -ésimo elemento más pequeño en el rango $a[l \dots r]$ ”. Esta consulta se puede responder usando una búsqueda binaria y un Merge Sort Tree, pero la complejidad temporal de una sola consulta sería $O(\log^3 n)$ . Cumpliremos la misma tarea usando un Árbol de Segmentos Persistente en $O(\log n)$ .

Primero discutiremos una solución para un problema más simple: Solo consideraremos arreglos en los que los elementos están acotados por $0 \le a[i] \lt n$ . Y solo queremos encontrar el $k$ -ésimo elemento más pequeño en algún prefijo del arreglo $a$ . Será muy fácil extender las ideas desarrolladas más adelante para arreglos no restringidos y consultas de rango no restringidas. Nótese que usaremos indexación desde uno para $a$ .

Usaremos un Árbol de Segmentos que cuenta todos los números que aparecen, es decir, en el Árbol de Segmentos guardaremos el histograma del arreglo. Así los vértices hoja guardarán cuántas veces aparecen los valores $0$ , $1$ , $\dots$ , $n-1$ en el arreglo, y los demás vértices guardarán cuántos números en algún rango están en el arreglo. En otras palabras creamos un Árbol de Segmentos regular con consultas de suma sobre el histograma del arreglo. Pero en lugar de crear los $n$ Árboles de Segmentos para cada prefijo posible, crearemos uno persistente, que contendrá la misma información. Empezaremos con un Árbol de Segmentos vacío (todos los conteos serán $0$ ) apuntado por $root_0$ , y agregaremos los elementos $a[1]$ , $a[2]$ , $\dots$ , $a[n]$ uno tras otro. Para cada modificación recibiremos un vértice raíz nuevo; llamemos $root_i$ a la raíz del Árbol de Segmentos después de insertar los primeros $i$ elementos del arreglo $a$ . El Árbol de Segmentos enraizado en $root_i$ contendrá el histograma del prefijo $a[1 \dots i]$ . Usando este Árbol de Segmentos podemos encontrar en tiempo $O(\log n)$ la posición del $k$ -ésimo elemento usando la misma técnica discutida en Contar el número de ceros, buscar el $k$ -ésimo cero.

Ahora a la versión no restringida del problema.

Primero para la restricción sobre las consultas: En lugar de solo realizar estas consultas sobre un prefijo de $a$ , queremos usar cualquier segmento arbitrario $a[l \dots r]$ . Aquí necesitamos un Árbol de Segmentos que represente el histograma de los elementos en el rango $a[l \dots r]$ . Es fácil ver que un Árbol de Segmentos de este tipo es solo la diferencia entre el Árbol de Segmentos enraizado en $root_{r}$ y el Árbol de Segmentos enraizado en $root_{l-1}$ , es decir, cada vértice en el Árbol de Segmentos $[l \dots r]$ se puede calcular con el vértice del árbol $root_{r}$ menos el vértice del árbol $root_{l-1}$ .

En la implementación de la función $\text{find_kth}$ esto se puede manejar pasando dos punteros a vértice y calculando el conteo/suma del segmento actual como diferencia de los dos conteos/sumas de los vértices.

Aquí están las funciones $\text{build}$ , $\text{update}$ y $\text{find_kth}$ modificadas


Vertex* build(int tl, int tr) {
    if (tl == tr)
        return new Vertex(0);
    int tm = (tl + tr) / 2;
    return new Vertex(build(tl, tm), build(tm+1, tr));
}

Vertex* update(Vertex* v, int tl, int tr, int pos) {
    if (tl == tr)
        return new Vertex(v->sum+1);
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        return new Vertex(update(v->l, tl, tm, pos), v->r);
    else
        return new Vertex(v->l, update(v->r, tm+1, tr, pos));
}

int find_kth(Vertex* vl, Vertex *vr, int tl, int tr, int k) {
    if (tl == tr)
    	return tl;
    int tm = (tl + tr) / 2, left_count = vr->l->sum - vl->l->sum;
    if (left_count >= k)
    	return find_kth(vl->l, vr->l, tl, tm, k);
    return find_kth(vl->r, vr->r, tm+1, tr, k-left_count);
}

Como ya se escribió arriba, hay que guardar la raíz del Árbol de Segmentos inicial, y también todas las raíces después de cada actualización. Aquí está el código para construir un Árbol de Segmentos Persistente sobre un vector a con elementos en el rango [0, MAX_VALUE].


int tl = 0, tr = MAX_VALUE + 1;
std::vector<Vertex*> roots;
roots.push_back(build(tl, tr));
for (int i = 0; i < a.size(); i++) {
    roots.push_back(update(roots.back(), tl, tr, a[i]));
}

// find the 5th smallest number from the subarray [a[2], a[3], ..., a[19]]
int result = find_kth(roots[2], roots[20], tl, tr, 5);

Ahora a las restricciones sobre los elementos del arreglo: De hecho podemos transformar cualquier arreglo a un arreglo de este tipo por compresión de índices. Al elemento más pequeño del arreglo se le asignará el valor 0, al segundo más pequeño el valor 1, y así sucesivamente. Es fácil generar tablas de lookup (p. ej. usando $\text{map}$ ), que convierten un valor a su índice y viceversa en tiempo $O(\log n)$ .

Árbol de Segmentos dinámico

(Se llama así porque su forma es dinámica y los nodos suelen asignarse de forma dinámica. También se conoce como Árbol de Segmentos implícito o Árbol de Segmentos disperso.)

Antes consideramos casos en los que tenemos la capacidad de construir el Árbol de Segmentos original. ¿Pero qué hacer si el tamaño original está lleno con algún elemento por defecto, pero su tamaño no permite construirlo por completo de antemano?

Podemos resolver este problema creando un Árbol de Segmentos de forma perezosa (incrementalmente). Inicialmente, crearemos solo la raíz, y crearemos los demás vértices solo cuando los necesitemos. En este caso, usaremos la implementación con punteros (antes de ir a los hijos del vértice, comprobar si están creados, y si no, crearlos). Cada consulta sigue teniendo solo la complejidad $O(\log n)$ , que es lo bastante pequeña para la mayoría de los casos de uso (p. ej. $\log_2 10^9 \approx 30$ ).

En esta implementación tenemos dos consultas: sumar un valor en una posición (inicialmente todos los valores son $0$ ), y calcular la suma de todos los valores en un rango. Vertex(0, n) será el vértice raíz del árbol implícito.


struct Vertex {
    int left, right;
    int sum = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;
 
    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
    }
 
    void extend() {
        if (!left_child && left + 1 < right) {
            int t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t, right);
        }
    }
 
    void add(int k, int x) {
        extend();
        sum += x;
        if (left_child) {
            if (k < left_child->right)
                left_child->add(k, x);
            else
                right_child->add(k, x);
        }
    }
 
    int get_sum(int lq, int rq) {
        if (lq <= left && right <= rq)
            return sum;
        if (max(left, lq) >= min(right, rq))
            return 0;
        extend();
        return left_child->get_sum(lq, rq) + right_child->get_sum(lq, rq);
    }
};

Obviamente esta idea se puede extender de muchas formas distintas. P. ej. agregando soporte para actualizaciones de rango vía propagación perezosa.

Problemas de práctica

SPOJ - KQUERY [Persistent segment tree / Merge sort tree]
Codeforces - Xenia and Bit Operations
UVA 11402 - Ahoy, Pirates!
SPOJ - GSS3
Codeforces - Sereja And Brackets
Codeforces - Distinct Characters Queries
Codeforces - Knight Tournament [For beginners]
Codeforces - Ant colony
Codeforces - Drazil and Park
Codeforces - Circular RMQ
Codeforces - Lucky Array
Codeforces - The Child and Sequence
Codeforces - DZY Loves Fibonacci Numbers [Lazy propagation]
Codeforces - Alphabet Permutations
Codeforces - Eyes Closed
Codeforces - Kefa and Watch
Codeforces - A Simple Task
Codeforces - SUM and REPLACE
Codeforces - XOR on Segment [Lazy propagation]
Codeforces - Please, another Queries on Array? [Lazy propagation]
COCI - Deda [Last element smaller or equal to x / Binary search]
Codeforces - The Untended Antiquity [2D]
CSES - Hotel Queries
CSES - Polynomial Queries
CSES - Range Updates and Sums