Este artículo explora tres estructuras de datos fundamentales para resolver problemas eficientes de consulta y actualización en secuencias: el Árbol de Fenwick (o BIT), el Árbol de Segmentos y la Tabla de Dispersión (Sparse Table). Cada una ofrece ventajas particulares dependiendo del tipo de operación requerida.

Árbol de Fenwick (Binary Indexed Tree)

El Árbol de Fenwick permite realizar actualizaciones en un punto y consultas de suma prefija en complejidad logarítmica. Su implementación se basa en operaciones de bits.

La operación clave es lowbit, que calcula el bit menos significativo de un número.

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

Para añadir un valor delta a una posición específica, se actualizan todos los nodos ancestros.

void actualizar(int posicion, int delta) {
    for (int idx = posicion; idx <= tamanio; idx += obtener_lowbit(idx)) {
        arbol[idx] += delta;
    }
}

La consulta de la suma hasta una posición determinada acumula los valores de los nodos cubiertos.

int consultar(int posicion) {
    int suma_total = 0;
    for (int idx = posicion; idx > 0; idx -= obtener_lowbit(idx)) {
        suma_total += arbol[idx];
    }
    return suma_total;
}

Ejemplo aplicado: Conteo de estrellas
Dado un conjunto de estrellas en un plano 2D con coordenadas (x, y) ordenadas ascendentemente por y, se determina el nivel de cada estrella. Una estrella tiene nivel k si hay k estrellas con coordenada x' ≤ x e y' ≤ y (excluyéndose a sí misma).

#include <iostream>
#include <vector>
using namespace std;

const int MAX_COORD = 32001;
int bit[MAX_COORD + 2];
int niveles[MAX_COORD];
int n;

void agregar(int pos) {
    for (int i = pos; i <= MAX_COORD; i += i & -i)
        bit[i]++;
}

int sumar_hasta(int pos) {
    int s = 0;
    for (int i = pos; i > 0; i -= i & -i)
        s += bit[i];
    return s;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        x++; // Ajuste para usar índices desde 1
        int nivel = sumar_hasta(x);
        niveles[nivel]++;
        agregar(x);
    }
    for (int i = 0; i < n; i++)
        cout << niveles[i] << endl;
    return 0;
}

Árbol de Segmentos

Esta estructura es versátil para consultas de rango y actualizaciones. Se modela como un árbol binario donde cada nodo representa un intervalo.

Las operaciones principales son:

void fusionar(int nodo) {
    // Combina los resultados de los hijos izquierdo y derecho
    datos[nodo].suma = datos[2*nodo].suma + datos[2*nodo+1].suma;
}

La construcción se realiza de forma recursiva:

void construir(int nodo, int izq, int der) {
    if (izq == der) {
        datos[nodo] = {izq, der, valores[der]};
    } else {
        datos[nodo] = {izq, der};
        int medio = (izq + der) / 2;
        construir(2*nodo, izq, medio);
        construir(2*nodo+1, medio+1, der);
        fusionar(nodo);
    }
}

La consulta para un intervalo [L, R] se divide recursivamente:

int consultar(int nodo, int L, int R) {
    if (L <= datos[nodo].izq && datos[nodo].der <= R)
        return datos[nodo].suma;

    int mitad = datos[nodo].izq + datos[nodo].der) / 2;
    int resultado = 0;
    if (L <= mitad) resultado += consultar(2*nodo, L, R);
    if (R > mitad) resultado += consultar(2*nodo+1, L, R);
    return resultado;
}

Para modificar un valor en una posición:

void modificar(int nodo, int pos, int nuevo_valor) {
    if (datos[nodo].izq == datos[nodo].der) {
        datos[nodo].suma += nuevo_valor;
    } else {
        int mitad = (datos[nodo].izq + datos[nodo].der) / 2;
        if (pos <= mitad) modificar(2*nodo, pos, nuevo_valor);
        else modificar(2*nodo+1, pos, nuevo_valor);
        fusionar(nodo);
    }
}

Tabla de Dispersión (Sparse Table)

Ideal para consultas de función idempotente (como mínimo, máximo o GCD) en rangos estáticos. Preprocesa respuestas para intervalos de longitud potencia de dos.

La tabla st[i][j] almacena el resultado para el intervalo que comienza en i con longitud 2^j.

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 200010, LOGN = 18;
int elementos[MAXN];
int tabla[MAXN][LOGN];

int main() {
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> elementos[i];

    // Preprocesamiento
    for (int i = 1; i <= n; i++) tabla[i][0] = elementos[i];

    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            tabla[i][j] = max(tabla[i][j-1], tabla[i + (1 << (j-1))][j-1]);
        }
    }

    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        int longitud = r - l + 1;
        int k = log2(longitud);
        int respuesta = max(tabla[l][k], tabla[r - (1 << k) + 1][k]);
        cout << respuesta << endl;
    }
    return 0;
}