El Árbol Indexado Binario (BIT, por sus siglas en inglés Binary Indexed Tree), también conocido como Árbol de Fenwick, es una estructura de datos eficiente diseñada para manejar consultas de sumas de prefijos y actualizaciones puntuales en arreglos numéricos. Su principal ventaja radica en su eficiencia tanto espacial como temporal, operando en O(log n) para ambas acciones.

La operación lowbit

El núcleo del funcionamiento de un Fenwick Tree es la función lowbit. Esta operación a nivel de bits extrae el bit menos significativo (el primer "1" de derecha a izquierda) de un número entero no negativo.

Matemáticamente, se define como: lowbit(x) = x & (-x).

En términos de representación binaria, si tenemos el número 10 (1010₂), su lowbit será 2 (0010₂), aislando la potencia de dos más baja que compone al número.

// Estructura básica para consultas de prefijo y actualización puntual
const int MAX_TAM = 100005;
long long arbol[MAX_TAM];
int limite_n;

// Obtiene el bit menos significativo
int extraer_lowbit(int n) {
    return n & -n;
}

// Incrementa el valor en una posición específica
void actualizar_punto(int pos, int valor) {
    for (; pos <= limite_n; pos += extraer_lowbit(pos)) {
        arbol[pos] += valor;
    }
}

// Calcula la suma acumulada desde 1 hasta pos
long long consultar_prefijo(int pos) {
    long long suma = 0;
    while (pos > 0) {
        suma += arbol[pos];
        pos -= extraer_lowbit(pos);
    }
    return suma;
}

Extensión 1: Actualizaciones de Rango y Consultas Puntuales

Para soportar el incremento de un valor en un intervalo [L, R] y realizar consultas sobre un elemento individual, podemos utilizar un arreglo de diferencias (Difference Array). En este esquema, una actualización de rango se convierte en dos actualizaciones puntuales en el Fenwick Tree:

1. Sumar d en la posición L.
2. Restar d en la posición R + 1.

La consulta puntual en la posición i se obtiene calculando la suma de prefijo 1 a i sobre este árbol de diferencias, sumándole el valor original del arreglo en dicha posición.

void actualizar_rango_simple(int l, int r, int val) {
    actualizar_punto(l, val);
    actualizar_punto(r + 1, -val);
}

long long obtener_valor_puntual(int i, int arreglo_original[]) {
    return consultar_prefijo(i) + arreglo_original[i];
}

Extensión 2: Actualizaciones de Rango y Consultas de Rango

Este es el escenario más complejo. Para realizar consultas de suma en un rango [1, i] tras haber aplicado actualizaciones de rango, debemos derivar la fórmula de la suma acumulada basándonos en el arreglo de diferencias D:

Suma(1, i) = ∑_{j=1}^i ∑_{k=1}^j D[k]

Reordenando la sumatoria, obtenemos: Suma(1, i) = (i + 1) * ∑ D[j] - ∑ (j * D[j]).

Por lo tanto, necesitamos mantener dos árboles de Fenwick: uno para almacenar D[i] y otro para i * D[i].

#include <cstdio>

long long bit_diferencias[MAX_TAM];
long long bit_ponderado[MAX_TAM];
int N;

void update_bit(long long tree[], int idx, long long val) {
    for (; idx <= N; idx += idx & -idx) {
        tree[idx] += val;
    }
}

long long query_bit(long long tree[], int idx) {
    long long res = 0;
    for (; idx > 0; idx -= idx & -idx) {
        res += tree[idx];
    }
    return res;
}

// Actualiza el rango [l, r] con el valor v
void modificar_rango(int l, int r, long long v) {
    update_bit(bit_diferencias, l, v);
    update_bit(bit_diferencias, r + 1, -v);
    update_bit(bit_ponderado, l, l * v);
    update_bit(bit_ponderado, r + 1, -(r + 1) * v);
}

// Obtiene la suma acumulada hasta idx
long long suma_prefijo_rango(int idx) {
    return (idx + 1) * query_bit(bit_diferencias, idx) - query_bit(bit_ponderado, idx);
}

int main() {
    int Q;
    if (scanf("%d %d", &N, &Q) != 2) return 0;

    long long prefijo_original[MAX_TAM] = {0};
    for (int i = 1; i <= N; i++) {
        long long val;
        scanf("%lld", &val);
        prefijo_original[i] = prefijo_original[i - 1] + val;
    }

    while (Q--) {
        char op[2];
        int l, r;
        scanf("%s %d %d", op, &l, &r);
        if (op[0] == 'C') {
            long long v;
            scanf("%lld", &v);
            modificar_rango(l, r, v);
        } else {
            long long total = (prefijo_original[r] + suma_prefijo_rango(r)) - 
                             (prefijo_original[l - 1] + suma_prefijo_rango(l - 1));
            printf("%lld\n", total);
        }
    }
    return 0;
}

Esta implementación permite gestionar operaciones masivas sobre grandes volúmenes de datos con una complejidad espacial mínima, superando en ocasiones al Segment Tree en términos de constante de tiempo y facilidad de codificación.