Introducción ======= Recientemente estuve aprendiendo sobre los árboles binarios indexados en línea, pero descubrí que la mayoría de las explicaciones disponibles en la web no son muy amigables para principiantes, especialmente en cuanto a la comprensión del principio fundamental. Por eso decidí escribir este artículo para consolidar mi propio entendimiento.
1. ¿Qué es un árbol binario indexado? ========= Concepto: ----- Básicamente, esta es una estructura de datos. Como su nombre lo indica, utiliza una estructura de árbol para realizar operaciones eficientes en arreglos, generalmente se usa para calcular sumas de prefijos y sumas de intervalos, y puede mantener dinámicamente el arreglo con complejidad temporal de \\(O(logN)\\).
Ventajas: ----- Comparado con las tablas ST, el árbol binario indexado tiene la funcionalidad de modificaciones en línea; comparado con los árboles segmentados, el código es más simple. Por supuesto, el árbol binario indexado tiene más limitaciones, pero no profundizaré demasiado aquí.
Esencia: ----- Utiliza las propiedades binarias.
2. Explicación detallada del principio ========== Veamos primero una imagen: (puedes continuar leyendo sin entenderla completamente) Imagen tomada de bilibili: [manim | Algoritmo | Estructura de Datos] Comprensión completa y aplicación profunda del árbol binario indexado | Soporte para múltiples operaciones de intervalo dinámicas
1.Lowbit -------- (1) Definición \\(lowbit(x)\\) representa el valor posicional del primer bit \\(1\\) contando desde la derecha en la representación binaria de \\(x\\) Ejemplo: \\(lowbit(5\_{10})=lowbit(101\_2)=1\_2=1\_{10}\\) \\(lowbit(12\_{10})=lowbit(1100\_2)=100\_2=4\_{10}\\)
En decimal, \\(lowbit(x)\\) representa el factor máximo de \\(x\\) que es una potencia de 2. Claro, este significado decimal no es muy importante. Para entender el árbol binario indexado, solo necesitamos enfocarnos en lowbit() en la representación binaria, no necesitamos preocuparnos por el decimal ni por lo que hay a la izquierda del primer \\(1\\) contando desde la derecha.
(2) Fórmula de cálculo Lowbit La fórmula es la siguiente:
El propósito de este almacenamiento es facilitar que la computadora utilice directamente el bit de signo para realizar sumas simples en números máquinas, completando así operaciones de resta. Por ejemplo, para calcular \\(5-12\\), sumando los números máquinas obtenemos \\(11111111\\) \\(11111111\\) \\(11111111\\) \\(11111001\\), que es el número máquina de \\(-7\\).
② Operación LowbitTomando \\(12\\) como ejemplo: Las codificaciones de los últimos ocho bits de \\(12\\) y \\(-12\\) son respectivamente $$00001100$$ $$11110100$$ Entonces realizando la operación \\(\&\\) obtenemos \\(000000100\\), que es \\(Lowbit(12)\\).
Explicación del principio: Supongamos que la codificación de un número \\(x\\) es así: \\(\\dots100\\dots0\\), agregar el signo negativo \\(-x\\) significa tomar el complemento a uno y \\(+1\\), el complemento a uno se convierte en \\(\\dots011\\dots1\\), \\(+1\\) se convierte en \\(\\dots100\\dots0\\). Podemos observar que \\(lowbit(x)\\) requerido es el mismo en \\(x\\) y \\(-x\\). Los bits superiores debido al complemento a uno tienen valores diferentes, entonces \\(x\&(-x)\\) puede obtener la parte \\(lowbit(x)\\) posterior. En otras palabras, cualquier \\(lowbit()\\), después de tomar complemento a uno y \\(+1\\), siempre será él mismo. Utilizando esta propiedad binaria, podemos calcular convenientemente \\(lowbit()\\).
2. Árbol binario indexado ------ (1) Definición (Esta es solo la definición dada por el autor para facilitar la comprensión; las definiciones encontradas en línea suelen ser descriptivas sin significado claro)
① Primero tenemos un arreglo \\(data\[x\]\\) para almacenar la secuencia original ② El árbol binario indexado es un arreglo \\(binaryTree\[x\]\\) de tipo int ③ Definimos \\(binaryTree\[x\]\\) como la suma de una secuencia de números de longitud \\(lowbit(x)\\) que termina en \\(data\[x\]\\), es decir \\(binaryTree\[x\]=\\displaystyle\\sum\_{i=x-lowbit(x)+1}^{x}{data\[i\]}\\)
(2) Propiedades Consideramos el arreglo \\(data\[x\]\\) como nodos hoja de este árbol, entonces este árbol tiene las siguientes propiedades:
Propiedad① \\(binaryTree\[x\]\\) tiene \\((log\_2lowbit(x))+1\\) nodos hijos, uno de los cuales es el nodo hoja \\(data\[x\]\\) Propiedad② Los nodos hijos de \\(binaryTree\[x\]\\) son \\(binaryTree\[x-2^i\] (i=0,1,2\\dots,(\\log\_2lowbit(x))-1)\\) y \\(data\[x\]\\) Es decir \\(binaryTree\[x\]=\\displaystyle\\sum\_{i=0}^{(\\log\_2lowbit(x))-1}{binaryTree\[x-2^i\]}+data\[x\]\\) Propiedad③ El nodo padre de \\(binaryTree\[x\]\\) es \\(binaryTree\[x+lowbit(x)\]\\) Combina la siguiente imagen para entender las tres propiedades: Imagen tomada de bilibili: [manim | Algoritmo | Estructura de Datos] Comprensión completa y aplicación profunda del árbol binario indexado | Soporte para múltiples operaciones de intervalo dinámicas
(3) Principio Lo más importante es la definición de \\(binaryTree\[x\]\\) como la suma de una secuencia de números de longitud \\(lowbit(x)\\) que termina en \\(data\[x\]\\), es decir \\(binaryTree\[x\]=\\displaystyle\\sum\_{i=x-lowbit(x)+1}^{x}{data\[i\]}\\), y la relación recursiva del árbol \\(binaryTree\[x\]=\\displaystyle\\sum\_{i=0}^{(\\log\_2lowbit(x))-1}{binaryTree\[x-2^i\]}+data\[x\]\\)
Ahora tomemos \\(binaryTree\[8\]\\) como ejemplo:
① Comprensión del patrón de longitud \\(lowbit(8)=1000\_2\\), es decir \\(binaryTree\[8\]\\) representa la suma de una secuencia de números de longitud \\(1000\_2\\). Podemos observar que en binario, \\(1000=0111+0001=(0100+0010+0001)+0001\\) Donde \\(0111=0100+0010+0001\\) representa \\(binaryTree\[4\]+binaryTree\[6\]+binaryTree\[7\]\\), con longitudes de \\(4\\), \\(2\\), \\(1\\) respectivamente; \\(0001\\) representa \\(data\[8\]\\), con longitud \\(1\\) La suma de sus longitudes \\(4+2+1+1=8=lowbit(8)\\)(reitero, solo necesitamos enfocarnos en lowbit() de un número)
El sistema binario permite ver claramente este patrón, y usando el sistema decimal familiar sería: \\(2^n=\\displaystyle\\sum\_{i=0}^{n-1}{2^i}+1\\) (se obtiene fácilmente con la fórmula de suma de series geométricas). Hasta ahora ya comprendemos el patrón de longitud.
② Comprensión del patrón de nodos hijos ¿Cómo obtenemos los índices de estos nodos hijos? La fórmula es: \\(child(x)=x-lowbit(2^i)=x-2^i(i=0,1,2\\dots,(log\_2lowbit(x))-1)\\) Requerimos que la suma de las longitudes \\(lowbit(i)\\) de todos los nodos hijos \\(binaryTree\[i\]\\) de \\(binaryTree\[x\]\\) más \\(1\\) sea igual a \\(lowbit(x)\\). Para cualquier \\(x\\), tenemos \\(lowbit(x-2^i)=lowbit(2^i)=2^i(i=0,1,2\\dots,(log\_2lowbit(x))-1)\\) (estos nodos hijos calculados así cumplen los requisitos). La demostración es bastante simple: considerando \\(x=\\dots100\\dots0,lowbit(x)=100\\dots0\\), entonces \\(x-lowbit(2^i)=(x-1)-lowbit(2^i)+1=\\dots011\\dots1-2^i+1=\\dots011\\dots1011\\dots1+1=\\dots011\\dots1100\\dots0\\), entonces la expresión anterior puede obtenerse una comprensión intuitiva.
Ya dedujimos los nodos hijos desde el nodo padre, entonces claramente, el nodo padre único de \\(binaryTree\[x\]\\) es \\(binaryTree\[x+lowbit(x)\]\\).
Hasta aquí, hemos comprendido completamente la definición de nodos y la relación recursiva entre nodos, entonces el árbol basado en arreglos está construido. Esto es el árbol binario indexado.
3. Aplicaciones del árbol binario indexado ======== (Nota: el árbol binario indexado necesita solo el doble espacio del arreglo original, fácilmente demostrable por definición.)
1. Modificación puntual, consulta de intervalo ----------- (1) Problema: [Plantilla] Árbol binario indexado 1
Descripción del problema Como se menciona, dado una secuencia, debes realizar dos tipos de operaciones:
- Agregar \\(x\\) a un número específico
- Calcular la suma de cada número en un intervalo específico
Formato de entrada La primera línea contiene dos enteros positivos \\(n,m\\), representando respectivamente la cantidad de números en la secuencia y el número total de operaciones. La segunda línea contiene \\(n\\) enteros separados por espacios, donde el \\(i\\)-ésimo número representa el valor inicial del \\(i\\)-ésimo elemento de la secuencia. Las siguientes \\(m\\) líneas contienen \\(3\\) enteros cada una, representando una operación, específicamente:
1 x kSignificado: agregar \\(k\\) al \\(x\\)-ésimo número2 x ySignificado: salida de la suma de cada número en el intervalo \\(\[x,y\]\\)
Formato de salida La salida contiene varias líneas de enteros, que son los resultados de todas las operaciones \\(2\\).
(2) Construcción del árbol: Aunque mencionamos anteriormente que necesitamos usar el arreglo \\(data\[x\]\\) para almacenar la secuencia original, en realidad no invocaremos \\(data\[x\]\\) realmente, por lo tanto, cuando ingresamos solo necesitamos almacenar el \\(i\\)-ésimo número en \\(binaryTree\[i\]\\) y construir desde abajo hacia arriba. Código:
int obtenerBitMenor(int x)
{
return x & (-x);
}
void construirArbol()
{
for(int i = 1; i <= tamano; i++)
{
int bitMenor = obtenerBitMenor(i);
for(int j = 1; j < bitMenor; j <<= 1)
binaryTree[i] += binaryTree[i - j];
}
}
(3) Modificación puntual: Solo modifica desde abajo hacia arriba. Código:
void actualizar(int posicion, int valor)
{
for(int i = posicion; i <= tamano; i += obtenerBitMenor(i))
binaryTree[i] += valor;
}
(4) Consulta de intervalo: Usa la diferencia de sumas de prefijo para obtener la suma de intervalo, solo sigue la definición y calcula \\(suma\\). Código:
long long consultarRango(int inicio, int fin)
{
long long suma1 = 0, suma2 = 0;
for(int i = fin; i >= 1; i -= obtenerBitMenor(i))
suma1 += binaryTree[i];
for(int i = inicio - 1; i >= 1; i -= obtenerBitMenor(i))
suma2 += binaryTree[i];
return suma1 - suma2;
}
(5) Código completo:
#include<bits/stdc++.h>
using namespace std;
const int MAXIMO = 5 * 1e5 + 5;
int datos[MAXIMO], binaryTree[MAXIMO];
int tamano, operaciones, contador;
int resultados[MAXIMO];
int obtenerBitMenor(int x)
{
return x & (-x);
}
void construirArbol()
{
for(int i = 1; i <= tamano; i++)
{
int bitMenor = obtenerBitMenor(i);
for(int j = 1; j < bitMenor; j <<= 1)
binaryTree[i] += binaryTree[i - j];
}
}
void actualizar(int posicion, int valor)
{
for(int i = posicion; i <= tamano; i += obtenerBitMenor(i))
binaryTree[i] += valor;
}
long long consultarRango(int inicio, int fin)
{
long long suma1 = 0, suma2 = 0;
for(int i = fin; i >= 1; i -= obtenerBitMenor(i))
suma1 += binaryTree[i];
for(int i = inicio - 1; i >= 1; i -= obtenerBitMenor(i))
suma2 += binaryTree[i];
return suma1 - suma2;
}
int main()
{
cin >> tamano >> operaciones;
for(int i = 1; i <= tamano; i++)
cin >> binaryTree[i];
construirArbol();
int tipo, x, y;
for(int i = 1; i <= operaciones; i++)
{
cin >> tipo >> x >> y;
if(tipo == 1)
actualizar(x, y);
else
resultados[++contador] = consultarRango(x, y);
}
for(int i = 1; i <= contador; i++)
cout << resultados[i] << endl;
return 0;
}
2. Modificación de intervalo, consulta puntual ----------- (1) Problema: [Plantilla] Árbol binario indexado 2
Descripción del problema Como se menciona, dado una secuencia, debes realizar dos tipos de operaciones:
- Agregar \\(x\\) a cada número en un intervalo;
- Calcular el valor de un número específico.
Formato de entrada La primera línea contiene dos enteros \\(N\\) y \\(M\\), representando respectivamente la cantidad de números en la secuencia y el número total de operaciones. La segunda línea contiene \\(N\\) enteros separados por espacios, donde el \\(i\\)-ésimo número representa el valor inicial del \\(i\\)-ésimo elemento de la secuencia. Las siguientes \\(M\\) líneas contienen \\(2\\) o \\(4\\) enteros cada una, representando una operación, específicamente:
Operación \\(1\\): Formato: 1 x y k Significado: agregar \\(k\\) a cada número en el intervalo \\(\[x,y\]\\); Operación \\(2\\): Formato: 2 x Significado: salida del valor del \\(x\\)-ésimo número.
Formato de salida La salida contiene varias líneas de enteros, que son los resultados de todas las operaciones \\(2\\).
(2) Arreglo de diferencias y sus propiedades La diferencia entre este problema y el anterior es que la modificación y la consulta están en rangos diferentes. La modificación de intervalo se puede entender como modificar cada punto individual en el intervalo, la consulta puntual se puede entender como consultar un intervalo de longitud \\(1\\), entonces también se puede resolver con la plantilla del problema anterior. Pero esto sería exageradamente complicado y claramente el algoritmo se demoraría demasiado. Por lo tanto, en este problema necesitamos usar un arreglo de diferencias y mantenerlo con árbol binario indexado.
¿Qué es un arreglo de diferencias? Su núcleo está en realizar diferencias: Dada una secuencia \\(data\[x\](data\[0\]=0)\\), definimos \\(diff\[x\]=data\[x\]-data\[x-1\](x\\ge1)\\), \\(diff\[x\]\\) es el arreglo de diferencias, con las siguientes propiedades:
Propiedad① \\(data\[x\]=\\displaystyle\\sum\_{i=1}^{x}{diff\[i\]}\\) (acumulación simple, demostración omitida) Propiedad② Cuando se realiza una modificación aditiva en un intervalo, solo cambian el comienzo y el final del arreglo de diferencias correspondiente.
Por ejemplo: agregar \\(k\\) a cada número \\(data\[l\\dots r\]\\) en \\(\[l,r\]\\), entonces la operación en el arreglo de diferencias correspondiente es: \\(diff\[l\]+k,diff\[r+1\]-k\\)
Entonces, a continuación podemos utilizar la propiedad① para consultas puntuales, utilizar la propiedad② para modificaciones de intervalo. Es decir, usar el arreglo de diferencias para convertir la modificación de intervalo en modificación puntual, y convertir la consulta puntual en consulta de intervalo (suma).
(3) Simplificación de entrada Aunque necesitamos usar un arreglo de diferencias, no necesitamos calcular la diferencia entre cada número y su número anterior. Solo necesitamos registrar cada cambio en el arreglo de diferencias causado por operaciones de intervalo. Su principio fundamental es: la adición satisface la ley conmutativa.
**Demostración:**Si no simplificamos, las operaciones serían: (por ahora no consideramos optimización con árbol binario indexado)
① Ingresar \\(data\[x\]\\), y obtener \\(diff\[x\]\\), \\(diff\[x\]=data\[x\]-data\[x-1\]\\) ② Realizar operación aditiva en intervalo \\(\[l,r\]\\) \\(data\[l\\dots r\]+=k\\), y modificar: \\(diff\[l\]=diff\[l\]+k，diff\[r+1\]=diff\[r+1\]-k\\) ③ Consultar \\(data\[x\]\\), \\(data\[x\]=\\displaystyle\\sum\_{i=1}^{x}{diff\[i\]}\\)
Observamos que \\(data\[x\]=\\displaystyle\\sum\_{i=1}^{x}{diff\[i\]}=\\displaystyle\\sum\_{i=1}^{x}{(data\[x\]-data\[x-1\]+k\_i)}=data\[x\]+\\displaystyle\\sum\_{i=1}^{x}{k\_i}\\), donde \\(k\_i\\) indica las operaciones realizadas en \\(diff\[i\]\\). Por lo tanto, solo necesitamos registrar \\(k\_i\\), lo que simplifica el código. Luego mantenemos con \\(binaryTree\[x\]\\).
(4) Código completo
#include<bits/stdc++.h>
using namespace std;
const int MAXIMO = 5 * 1e5 + 5;
int secuencia[MAXIMO], binaryTree[MAXIMO];
int resultados[MAXIMO], contador;
int tamano, operaciones;
int obtenerBitMenor(int x)
{
return x & (-x);
}
void aplicarModificacion(int inicio, int fin, int valor)
{
for(int i = inicio; i <= tamano; i += obtenerBitMenor(i))
binaryTree[i] += valor;
for(int i = fin + 1; i <= tamano; i += obtenerBitMenor(i))
binaryTree[i] -= valor;
}
int consultarPunto(int posicion)
{
int acumulado = 0;
for(int i = posicion; i >= 1; i = i - obtenerBitMenor(i))
acumulado += binaryTree[i];
return secuencia[posicion] + acumulado;
}
int main()
{
cin >> tamano >> operaciones;
for(int i = 1; i <= tamano; i++)
cin >> secuencia[i];
int tipo, x, y, k;
for(int i = 1; i <= operaciones; i++)
{
cin >> tipo;
if(tipo == 1)
{
cin >> x >> y >> k;
aplicarModificacion(x, y, k);
}
else
{
cin >> x;
resultados[++contador] = consultarPunto(x);
}
}
for(int i = 1; i <= contador; i++)
cout << resultados[i] << endl;
return 0;
}