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:
| i | Tramo 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 = 13sumar 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).
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"; // 13Asignar 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 nd | Tramo 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) = 6La figura sigue la asignación sobre los mismos cuatro valores: solo cambia un camino desde la hoja hasta la raíz.
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*ny no2*n: el árbol no es perfecto cuando n no es potencia de 2, y esa es la cota que siempre alcanza.- El neutro:
LLONG_MAXpara el mínimo,0para 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
minde construcción, actualización y consulta pormax,+o__gcdy 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:
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
| Datos | Consulta | Herramienta |
|---|---|---|
| fijos | suma | prefijos O(1) |
| cambian (1 posición) | suma | Fenwick O(log n) |
| cambian (1 posición) | mín/máx/otro | Segment tree O(log n) |
| cambian (rangos enteros) | operaciones compatibles con la actualización | segment 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:
| Operador | Qué hace | Ejemplo |
|---|---|---|
a & b | 1 donde ambos tienen 1 | 12 & 10 = 1100 & 1010 = 1000 = 8 |
a | b | 1 donde alguno tiene 1 | 12 | 10 = 1110 = 14 |
x << k | corre los bits k lugares a la izquierda (multiplica por 2ᵏ) | 1 << 3 = 1000 = 8 |
x >> k | corre 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.
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.
Idea para comprobar tu solución
Fenwick recibe delta=6−2=4. Si consultas mínimos en vez de sumas, las respuestas son 2 y 6 y puedes usar segment tree.
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?
Una pista, si la necesitas
Distingue asignar un valor de sumar un incremento.
Contrastar el razonamiento
Ambas sumas son 10. Si tu Fenwick ofrece add, la primera asignación necesita delta=7−4=3 y la segunda delta=7−7=0. Conserva el valor actual para calcular la diferencia.
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.
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Dynamic Range Sum Queries (CSES 1648) | ★★★ (—) | Fenwick: convertir asignación en delta y recordar el valor |
| 2 | Dynamic 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.
| Problema | Fase | Qué practica |
|---|---|---|
| Tranvía en Chuchunco | Regional 2024 | set + upper_bound: consultas de predecesor en vivo |
| ⭐⭐ Aplausómetro | Nacional 2024 | pila monótona propagando rondas |
| ⭐⭐ Roberto el constructor | Nacional 2020 | ventanas 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]?
Ver razonamiento
No: en el primero es 5 y en el segundo es 2, aunque los dos resúmenes son idénticos. Al resumir todo por el mínimo se perdió información que ninguna resta puede recuperar. Las sumas sí permiten cancelar el prefijo sobrante. Un segment tree resuelve la consulta de mínimo combinando bloques contenidos en
[2..3], sin incluir el 1 de la primera posición ni intentar eliminarlo después. Esa diferencia explica la elección de estructura.
← 19 - Union-Find (DSU) · Ruta de Aprendizaje · 21 - Árboles I →