El Árbol Binario Indexado (BIT), también conocido como Árbol de Fenwick, es una estructura de datos eficiente para manejar sumas de prefijos y actualizaciones puntuales. En comparación con un Árbol de Segmentos (Segment Tree), el BIT consume menos memoria y presenta una implementación más concisa, aunque tradicionalmente está limitado a operaciones de punto. En este artículo, exploraremos cómo extender sus capacidades para soportar modificaciones de rango y consultas de rango simultáneamente mediante el uso de arreglos de diferencia.

Fundamentos: La función lowbit

La estructura de un Árbol de Fenwick se basa en la manipulación de bits. La función lowbit es el núcleo de esta estructura, ya que permite navegar entre nodos ascendientes y descendientes para actualizar o consultar valores.

La operación lowbit(x) extrae el valor de la potencia de 2 más pequeña que compone al número x (el bit menos significativo). Matemáticamente, se define como:

int calcular_lowbit(int x) {
    return x & -x;
}

Esta función nos permite definir la relación entre niveles: para subir en el árbol (actualizar), sumamos el lowbit; para bajar (consultar prefijos), restamos el lowbit.

Extension a Modificaciones de Rango

Para modificar un rango $[l, r]$ con un valor $v$ en un BIT estándar, utilizamos el concepto de Arreglo de Diferencia. Definimos un arreglo $D$ tal que $A[i] = D[1] + D[2] + ... + D[i]$. Bajo esta premisa:

• Sumar $v$ al rango $[l, r]$ equivale a realizar $D[l] += v$ y $D[r+1] -= v$.
• La consulta del valor original $A[i]$ se convierte en una suma de prefijo de $D$ hasta $i$.

Consultas de Rango mediante Dos Árboles

Si desemaos obtener la suma de un rango $\sum_{i=1}^{x} A[i]$, debemos derivar la fórmula utilizando el arreglo de diferencia $D$:

$$\sum_{i=1}^{x} A[i] = \sum_{i=1}^{x} \sum_{j=1}^{i} D[j]$$

Al expandir la sumatoria, observamos que $D[1]$ aparece $x$ veces, $D[2]$ aparece $x-1$ veces, y así sucesivamente. La fórmula se puede reescribir como:

$$\sum_{i=1}^{x} A[i] = \sum_{i=1}^{x} (x - i + 1) \cdot D[i] = (x + 1) \sum_{i=1}^{x} D[i] - \sum_{i=1}^{x} (i \cdot D[i])$$

Para computar esto de forma eficiente en $O(\log n)$, necesitamos mantener dos Árboles de Fenwick:

1. BIT1: Almacana los valores de $D[i]$.
2. BIT2: Almacena los valores de $i \cdot D[i]$.

Implementación en C++

A continuación, se presenta una implementación robusta para procesar múltiples consutlas y actualizaciones de rango.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 100005;
ll arbol_dif[MAXN];     // Representa D[i]
ll arbol_idx_dif[MAXN]; // Representa D[i] * i
int total_elementos;

int obtener_lowbit(int x) {
    return x & -x;
}

void actualizar(ll* arbol, int idx, ll valor) {
    for (; idx <= total_elementos; idx += obtener_lowbit(idx)) {
        arbol[idx] += valor;
    }
}

ll consultar_prefijo(ll* arbol, int idx) {
    ll suma = 0;
    for (; idx > 0; idx -= obtener_lowbit(idx)) {
        suma += arbol[idx];
    }
    return suma;
}

void modificar_rango(int l, int r, ll valor) {
    // Actualización para BIT1
    actualizar(arbol_dif, l, valor);
    actualizar(arbol_dif, r + 1, -valor);
    
    // Actualización para BIT2: i * D[i]
    actualizar(arbol_idx_dif, l, valor * l);
    actualizar(arbol_idx_dif, r + 1, -valor * (r + 1));
}

ll obtener_suma_rango(int x) {
    // Aplicando la fórmula: (x+1) * Sum(D[i]) - Sum(i * D[i])
    return (x + 1) * consultar_prefijo(arbol_dif, x) - consultar_prefijo(arbol_idx_dif, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int consultas;
    cin >> total_elementos >> consultas;

    ll valor_previo = 0;
    for (int i = 1; i <= total_elementos; ++i) {
        ll valor_actual;
        cin >> valor_actual;
        modificar_rango(i, i, valor_actual); // Inicialización como rangos de tamaño 1
    }

    while (consultas--) {
        char tipo;
        cin >> tipo;
        if (tipo == 'U') { // Update: Rango [l, r] + v
            int l, r;
            ll v;
            cin >> l >> r >> v;
            modificar_rango(l, r, v);
        } else if (tipo == 'Q') { // Query: Suma en [l, r]
            int l, r;
            cin >> l >> r;
            cout << obtener_suma_rango(r) - obtener_suma_rango(l - 1) << "\n";
        }
    }

    return 0;
}

Análisis de Complejidad

Con esta estructura, tanto la modificación de un rango como la consulta de la suma en un intervalo se realizan en un tiempo de $O(\log n)$. El espacio de memoria es $O(n)$, duplicando el almacenamiento respecto a un BIT simple pero manteniéndose significativamente por debajo de los requerimientos de un Árbol de Segmentos estándar, que suele requerir $4n$.