20 · Fenwick y segment tree

Estructuras y algoritmos avanzados · Ruta de Aprendizaje

Antes de empezar. Sumas de rango: 17 - Sumas de prefijos; recursión: 09 - Recursión. Los operadores de bits se explican aquí.

🎯 Objetivos

Al terminar este módulo sabes:

  • Resolver el problema que los prefijos no pueden: consultas de rango con actualizaciones.
  • Usar un Fenwick (BIT) para sumas dinámicas en O(log n).
  • Escribir un segment tree de mínimo y saber por qué el Fenwick no sirve ahí.
  • Leer y escribir los operadores de bits que aparecen de aquí en adelante.

📖 La lección

La clase parte con sumas que cambian, construye un Fenwick y después pasa a mínimos con segment tree. La derivación binaria de lowbit queda como ampliación al final; puedes estudiar ambas estructuras antes de leerla.

El hueco que dejaron los prefijos

Los prefijos responden rangos en O(1)… mientras el arreglo no cambie (una actualización obliga a reconstruir O(n)). Cuando el enunciado mezcla “actualiza la posición i” con “suma del rango [l, r]”, conviene comparar cuántos cambios y consultas habrá. Con muchos de ambos, hacerlos en O(log n) puede ahorrar trabajo frente a reconstruir los prefijos. Ese es el contrato del Fenwick tree (BIT):

Imagina valores {5,2,7,3,1,4,6,8}, numerados del 1 al 8. Recalcular un prefijo tras cada cambio toca muchas posiciones. En cambio, podemos guardar bloques reutilizables:

iTramo resumido en bit[i]Suma inicial
1[1,1]5
2[1,2]7
3[3,3]7
4[1,4]17
5[5,5]1
6[5,6]5
7[7,7]6
8[1,8]36

Para sumar las primeras cinco casillas, combina los bloques [5,5] y [1,4]: 1+17=18. Para aumentar la quinta casilla en 3, cambia solo los bloques que la contienen: bit[5], bit[6] y bit[8], que pasan a 4, 8 y 39.

La longitud de cada bloque es la mayor potencia de dos que divide su índice: 6 tiene longitud 2, 4 tiene longitud 4. Esa longitud se calcula con i & (-i), llamado lowbit. Para usar los recorridos basta esta regla; más abajo se explica su representación binaria.

int n;
vector<long long> bit; // Fenwick 1-indexado
 
void sumar(int i, long long delta) {
    for (; i <= n; i += i & (-i)) bit[i] += delta;
}
 
long long prefijo(int i) { // suma de a[1..i]
    long long s = 0;
    for (; i > 0; i -= i & (-i)) s += bit[i];
    return s;
}
// rango [l, r]: prefijo(r) - prefijo(l-1)

Para usar las funciones, reserva la memoria e incorpora los valores. Para ejecutar con pocos datos, usaremos ahora cuatro valores. Este bloque va dentro de main, después de las definiciones anteriores:

// usa: n, bit, sumar, prefijo
vector<long long> a = {5, 2, 7, 3};
n = a.size();
bit.assign(n + 1, 0);
for (int i = 1; i <= n; i++) sumar(i, a[i - 1]);
cout << prefijo(3) - prefijo(1) << "\n"; // posiciones 2..3: 2+7 = 9
sumar(2, 4); // aumenta 4: el segundo valor pasa de 2 a 6
cout << prefijo(3) - prefijo(1) << "\n"; // 6+7 = 13

sumar recibe un aumento, no el nuevo valor. Sus índices válidos son 1..n; llamar sumar(0, ...) no avanzaría y produciría un ciclo infinito. prefijo(0) sí es válido y vale cero. Las sumas deben caber en long long.

Ese i & (-i) define qué bloque de sumas parciales guarda cada posición: bit[i] guarda la suma de un bloque que termina en i y mide i & (-i).

a11a22a33a44a55a66a77a88a[i]bit[1]bit[2]bit[3]bit[4]bit[5]bit[6]bit[7]bit[8]prefijo(7) = bit[7] + bit[6] + bit[4]7 = 111 → quita el bit más bajo → 6 = 110 → 4 = 100 → 0: tres bloques, sin traslape, que juntos cubren a[1..7]el largo del bloque de i es i & (-i); por eso los bloques no se pisan y hay a lo más log n por consulta

Si el diagrama no cabe, deslízalo horizontalmente.

Con eso, prefijo(7) es una caminata: 7 → 6 → 4 → 0, quitando cada vez el bit más bajo, y los tres bloques que visita cubren exactamente a[1..7] sin pisarse. sumar(i, delta) visita los bloques que contienen i agregando lowbit. No invierte el camino de una consulta: desde 5, consultar sigue 5→4→0; actualizar sigue 5→6→8. Por eso ambas cuestan O(log n). La tabla con el reparto exacto de los bloques está en Fenwick (BIT). Ojo: es 1-indexado por diseño.

Asignar un valor: convertirlo en aumento

Si el enunciado dice «deja la posición i en nuevo», hay que recordar su valor anterior. En este ejemplo independiente, a también se numera desde 1:

// usa: n, bit, sumar, prefijo
vector<long long> a = {0, 5, 2, 7, 3}; // a[0] no se usa
n = 4;
bit.assign(n + 1, 0);
for (int i = 1; i <= n; i++) sumar(i, a[i]);
int i = 2;
long long nuevo = 6;
sumar(i, nuevo - a[i]); // delta = 6 - 2 = 4
a[i] = nuevo;           // recordarlo para la próxima asignación
cout << prefijo(3) - prefijo(1) << "\n"; // 13

Asignar otra vez 6 produce delta=0. Sumar 6 directamente habría convertido el 2 en 8, que responde otra operación.

La artillería mayor: segment tree

El Fenwick que construimos responde sumas de rango restando dos prefijos. Ese mismo método no permite obtener un mínimo: el mínimo no se puede restar. Si sabes que el mínimo de [1..7] es 3 y el de [1..3] es 3, no tienes idea del mínimo de [4..7]. Ahí se acaba el truco de los prefijos, y empieza el segment tree.

La idea es un árbol donde cada nodo guarda la respuesta de su trozo: la raíz cubre todo, sus dos hijos cada mitad, y así hasta las hojas, que son un elemento. Un rango cualquiera se arma con O(log n) nodos ya calculados.

Construir un árbol pequeño

Usemos a = {5,2,7,3}, con posiciones 0..3. Cada nodo resume un tramo:

Nodo del árbol ndTramo del arreglo [l,r]Mínimo
1 (raíz)[0,3]2
2[0,1]2
3[2,3]3
4, 5, 6, 7 (hojas)[0,0], [1,1], [2,2], [3,3]5, 2, 7, 3

El nodo 5 no representa a[5]: es la hoja de a[1]. nd identifica una casilla del árbol t; l y r delimitan el tramo de a que esa casilla resume. Los hijos de nd se numeran 2·nd y 2·nd+1. Es una forma de guardar el dibujo, no una operación sobre los valores de entrada.

Las tres operaciones, paso a paso

Construir (build). Si l=r, copia el único valor de ese tramo. Si no, construye las dos mitades y guarda el mínimo de sus respuestas. En el ejemplo, las hojas 5 y 2 producen el resumen 2 del nodo 2; las hojas 7 y 3 producen el 3 del nodo 3; ambos resúmenes producen el 2 de la raíz.

Consultar (query). Queremos el mínimo en [1,2]. La raíz cubre [0,3], por lo que no podemos tomar su 2 directamente: podría venir de fuera del rango. Bajamos a ambas mitades. La hoja [0,0] queda fuera; [1,1] aporta 2; [2,2] aporta 7; [3,3] queda fuera. Combinamos min(2,7)=2. Si un nodo queda entero dentro de la consulta, usamos su resumen sin bajar. Si queda entero fuera, devuelve LLONG_MAX: un neutro que no cambia el mínimo del otro lado. No le sumamos nada a ese valor.

Asignar (update). Cambiar a[1] a 6 solo afecta los tramos que contienen esa posición. La hoja del nodo 5 pasa a 6; el nodo 2 pasa a min(5,6)=5; la raíz pasa a min(5,3)=3. Las otras hojas no se recorren. Después, consultar [1,2] devuelve min(6,7)=6.

En las tres funciones, nd,l,r describen el nodo que estamos visitando. En query, ql,qr son la consulta original y no cambian al bajar. En update, i,v son la posición que se asigna y su nuevo valor. La entrada es no vacía; las posiciones y consultas deben estar dentro de 0..n−1.

El bloque completo reúne esas tres operaciones:

int n;
vector<long long> t;                     // t tiene tamaño 4*n
 
void build(const vector<long long>& a, int nd, int l, int r) {
    if (l == r) { t[nd] = a[l]; return; }             // hoja: un solo elemento
    int m = (l + r) / 2;
    build(a, 2*nd, l, m);  build(a, 2*nd+1, m+1, r);
    t[nd] = min(t[2*nd], t[2*nd+1]);                  // el padre resume a sus hijos
}
void update(int nd, int l, int r, int i, long long v) {   // a[i] = v
    if (l == r) { t[nd] = v; return; }
    int m = (l + r) / 2;
    if (i <= m) update(2*nd, l, m, i, v);
    else        update(2*nd+1, m+1, r, i, v);
    t[nd] = min(t[2*nd], t[2*nd+1]);
}
long long query(int nd, int l, int r, int ql, int qr) {   // mínimo en [ql, qr]
    if (qr < l || r < ql) return LLONG_MAX;           // afuera: el neutro
    if (ql <= l && r <= qr) return t[nd];             // adentro: ya está resumido
    int m = (l + r) / 2;
    return min(query(2*nd, l, m, ql, qr), query(2*nd+1, m+1, r, ql, qr));
}
// la raíz es el nodo 1 y cubre [0, n-1]: query(1, 0, n-1, l, r)

Este es un ejemplo de uso independiente del Fenwick. Ahora los índices del arreglo empiezan en 0; los nodos internos del árbol empiezan en 1. Las funciones anteriores van antes de main y estas llamadas dentro:

// usa: n, t, build, update, query
vector<long long> a = {5, 2, 7, 3};
n = a.size();
t.assign(4 * n, LLONG_MAX);
build(a, 1, 0, n - 1);
cout << query(1, 0, n - 1, 1, 2) << "\n"; // min(2,7) = 2
update(1, 0, n - 1, 1, 6);               // asigna a[1] = 6 en el árbol
cout << query(1, 0, n - 1, 1, 2) << "\n"; // min(6,7) = 6

La figura sigue la asignación sobre los mismos cuatro valores: solo cambia un camino desde la hoja hasta la raíz.

a = [5, 2, 7, 3] · asignar a[1] = 6mínimo: 2 → 3nd=1 · rango [0,3]mínimo: 2 → 5nd=2 · rango [0,1]mínimo: 3nd=3 · rango [2,3]valor: 2 → 6nd=5 · hoja a[1]Cambiar la hoja y recalcular sus ancestros; los demás no cambian.

Si el diagrama no cabe, deslízalo horizontalmente.

nd=5 identifica la hoja que representa a[1]: índice de nodo e índice del arreglo son cosas distintas. Al cambiar 2 por 6, el mínimo de [0,1] pasa a 5 y el de [0,3] pasa a 3.

El árbol requiere n >= 1 y consultas 0 <= ql <= qr < n. update modifica el árbol; el vector original a no se actualiza automáticamente. nd identifica un nodo del árbol, mientras l y r describen el tramo del arreglo que cubre. No son tres posiciones del mismo arreglo.

Tres detalles que valen los tres que son:

  • 4*n y no 2*n: el árbol no es perfecto cuando n no es potencia de 2, y esa es la cota que siempre alcanza.
  • El neutro: LLONG_MAX para el mínimo, 0 para la suma. Es el valor que no cambia la respuesta cuando el trozo no aporta nada.
  • Cambiar de operación exige cambiar todas las combinaciones: reemplaza los min de construcción, actualización y consulta por max, + o __gcd y el neutro que corresponda. El resto es idéntico — por eso el segment tree es LA estructura de la IOI moderna.

Una consulta con bloques más grandes

En este segundo dibujo hay ocho valores. La consulta puede tomar nodos que resumen varios elementos, en vez de llegar a todas las hojas:

1[0,7]1[0,3]2[0,1]521[2,3]713[4,7]3[4,5]934[6,7]84a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]mínimo en [2, 6] = min(1, 3, 8) = 1Tomamos tres bloques en vez de cinco hojas; en general, O(log n) bloques.

Si el diagrama no cabe, deslízalo horizontalmente.

Fíjate en cómo la consulta “elige” nodos: si el trozo de un nodo cae entero dentro del rango, se toma su valor y no se baja más; si queda afuera, se ignora; y solo cuando el rango lo corta a la mitad hay que bajar a los dos hijos. En cada nivel del árbol eso pasa a lo más dos veces, y de ahí el O(log n).

Costo: O(n) construir, O(log n) por consulta o actualización. Con esto ya puedes hacer el problema 2 de la práctica.

Lo que no entra en este módulo es el lazy propagation, que permite actualizar un rango completo de una vez: es el siguiente escalón y vive en Segment tree con lazy propagation (y más adelante, Segment tree persistente). La ficha con las variantes y el código de referencia es Segment tree.

El mapa de decisión de consultas de rango

DatosConsultaHerramienta
fijossumaprefijos O(1)
cambian (1 posición)sumaFenwick O(log n)
cambian (1 posición)mín/máx/otroSegment tree O(log n)
cambian (rangos enteros)operaciones compatibles con la actualizaciónsegment tree con lazy

La versión completa de esta decisión — con todas las estructuras, de la STL y propias, y el costo de cada operación — está en el Catálogo de estructuras.

Ampliación: por qué funciona lowbit

Este módulo y el 22 usan aritmética binaria. Aquí se explican los símbolos necesarios.

Todo entero se guarda en binario: 13 es 1101, o sea 8+4+1. Los operadores trabajan bit a bit, en paralelo sobre todas las posiciones:

OperadorQué haceEjemplo
a & b1 donde ambos tienen 112 & 10 = 1100 & 1010 = 1000 = 8
a | b1 donde alguno tiene 112 | 10 = 1110 = 14
x << kcorre los bits k lugares a la izquierda (multiplica por 2ᵏ)1 << 3 = 1000 = 8
x >> kcorre k lugares a la derecha (divide por 2ᵏ)13 >> 2 = 11 = 3

En estos ejemplos x es no negativo y 0 <= k < 31 para enteros de 32 bits; los desplazamientos y sus resultados deben caber en el tipo usado.

De ahí salen los dos modismos que verás siempre:

// supone: int x, k;
int potencia = 1 << k;        // 2^k, sin pow() ni decimales
bool encendido = (x >> k) & 1; // ¿el bit k de x está en 1?

⚠️ & tiene menos prioridad que == en C++, así que if (x & 1 == 0) no hace lo que parece. Pon paréntesis siempre: if ((x & 1) == 0).

Y el que necesita el Fenwick: x & (-x) deja encendido solo el bit más bajo de x. Funciona porque -x es, en la representación de la máquina, ~x + 1: invertir todos los bits y sumar 1 deja los de la derecha iguales hasta el primer 1, y todo lo de la izquierda invertido — así que el & solo sobrevive en ese bit. Para 6 = 110 da 2 = 10; para 12 = 1100 da 4.

x = 600000110-x = -611111010x & (-x)00000010= 2a la derecha del bit más bajo, −x copia a x; a la izquierda lo invierte: el & sobrevive solo ahí

Si el diagrama no cabe, deslízalo horizontalmente.

🏋️ Práctica

Práctica directa: Asignar y consultar

En {5,2,7,3}, posiciones desde 1, suma [2,3], asigna 6 a la posición 2 y suma [2,3] otra vez. Salida: 9 13.

Variación: Asignar dos veces

Partes de {2,4,1}, con posiciones desde 1. Asigna 7 a la posición 2, consulta la suma total y vuelve a asignar 7 a esa misma posición. ¿Cuáles son ambas sumas?

Aplicar en problemas

Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.

#ProblemaDificultadQué practica
1Dynamic Range Sum Queries (CSES 1648)★★★ (—)Fenwick: convertir asignación en delta y recordar el valor
2Dynamic Range Minimum Queries (CSES 1649)★★★ (—)aquí el Fenwick no basta: segment tree
3⭐ Range Update Queries (CSES 1651)★★★★ (—)actualizar rangos con el truco de diferencias

Desafíos OCI (en español)

Estos tres no salen con lo de este módulo: cada uno pide una estructura auxiliar distinta que el vault documenta pero la ruta no enseña. Están aquí porque son el siguiente escalón natural y porque reconocer qué falta ya es media solución — ábrelos con la ficha al lado, sin apuro.

ProblemaFaseQué practica
Tranvía en ChuchuncoRegional 2024set + upper_bound: consultas de predecesor en vivo
⭐⭐ AplausómetroNacional 2024pila monótona propagando rondas
⭐⭐ Roberto el constructorNacional 2020ventanas deslizantes 2D con deques — ficha: Deque monótona (ventana deslizante)

Para pensar: qué información pierde un mínimo

Compara los arreglos {1, 5, 7} y {1, 2, 9}, con índices desde 1. En ambos, el mínimo del prefijo [1..1] es 1 y el de [1..3] también es 1. ¿Puedes deducir de esos dos valores el mínimo de [2..3]?


← 19 - Union-Find (DSU) · Ruta de Aprendizaje · 21 - Árboles I →