← Estructuras de datos desde cero · Lección 30/32
Sumas por rango: prefijos y Fenwick
Sumas prefijas: pagar una vez, preguntar mil
Si te preguntan muchas veces «¿cuánto se vendió del día 2 al 5?», sumar el tramo cada vez cuesta O(n) por pregunta. Mejor preparar una vez el arreglo de sumas prefijas: pre[i] es la suma de los primeros i elementos, con pre[0] = 0.
La suma de a a b (incluidos) es entonces pre[b + 1] - pre[a]: todo hasta b, menos lo que había antes de a. Una resta, O(1), sin importar qué tan largo sea el tramo.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
pretiene un elemento más queventasy crece siempre (si no hay negativos).suma(2, 5)espre[6] - pre[2]= 23 − 4 = 19, lo mismo que 4 + 1 + 5 + 9, las casillas resaltadas.- El total, 31, es el último de
pre.
Toda la lección en una página
Sumas prefijas: pagar una vez, preguntar mil
Si te preguntan muchas veces «¿cuánto se vendió del día 2 al 5?», sumar el tramo cada vez cuesta O(n) por pregunta. Mejor preparar una vez el arreglo de sumas prefijas: pre[i] es la suma de los primeros i elementos, con pre[0] = 0.
La suma de a a b (incluidos) es entonces pre[b + 1] - pre[a]: todo hasta b, menos lo que había antes de a. Una resta, O(1), sin importar qué tan largo sea el tramo.
const ventas = [3, 1, 4, 1, 5, 9, 2, 6];
const pre = [0];
for (const v of ventas) pre.push(pre[pre.length - 1] + v);
console.log(pre);
const suma = (a, b) => pre[b + 1] - pre[a];
console.log(suma(2, 5));
console.log(suma(0, 7));
pretiene un elemento más queventasy crece siempre (si no hay negativos).suma(2, 5)espre[6] - pre[2]= 23 − 4 = 19, lo mismo que 4 + 1 + 5 + 9, las casillas resaltadas.- El total, 31, es el último de
pre.
La misma idea con productos
El reto «producto del arreglo excepto uno mismo» pide, para cada posición, el producto de todos los demás, sin dividir y en O(n). Es un pariente de las sumas prefijas: en una pasada de izquierda a derecha guardas el producto de todo lo que hay antes; en otra de derecha a izquierda multiplicas por todo lo que hay después.
Así funciona aunque haya un cero, que es justo donde dividir fallaría.
function productoExceptoYo(nums) {
const n = nums.length;
const res = new Array(n).fill(1);
let izq = 1;
for (let i = 0; i < n; i++) {
res[i] = izq;
izq *= nums[i];
}
let der = 1;
for (let i = n - 1; i >= 0; i--) {
res[i] *= der;
der *= nums[i];
}
return res;
}
console.log(productoExceptoYo([1, 2, 3, 4]));
console.log(productoExceptoYo([2, 0, 5]));
- Para
[1, 2, 3, 4]: 24 = 2·3·4, 12 = 1·3·4, 8 = 1·2·4 y 6 = 1·2·3. - Con el cero, sólo la posición del cero da algo distinto de 0: 2·5 = 10.
Cuando los datos cambian: el árbol de Fenwick
Las sumas prefijas tienen un problema: si cambia un valor, hay que recalcular todo lo que viene después, O(n). El árbol de Fenwick (o árbol binario indexado) reparte la diferencia: cada casilla arbol[i] guarda la suma de un tramo que termina en i y mide i & -i.
i & -i es el bit más bajo encendido de i: para 6 (110 en binario) es 2, para 8 (1000) es 8, para 12 (1100) es 4. Para consultar se baja restando ese bit; para actualizar se sube sumándolo. Cada camino tiene a lo más log₂ n pasos: las dos operaciones son O(log n).
Los índices van desde 1, porque 0 & -0 es 0 y el ciclo nunca avanzaría.
class Fenwick {
constructor(n) {
this.arbol = new Array(n + 1).fill(0);
}
sumar(i, delta) {
for (; i < this.arbol.length; i += i & -i) this.arbol[i] += delta;
}
prefijo(i) {
let s = 0;
for (; i > 0; i -= i & -i) s += this.arbol[i];
return s;
}
rango(a, b) {
return this.prefijo(b) - this.prefijo(a - 1);
}
}
const ventas = [3, 1, 4, 1, 5, 9, 2, 6];
const f = new Fenwick(ventas.length);
ventas.forEach((v, k) => f.sumar(k + 1, v));
console.log(f.rango(3, 6));
f.sumar(4, 10);
console.log(f.rango(3, 6));
for (const i of [6, 8, 12]) console.log(i, "& -" + i, "=", i & -i);
rango(3, 6)cuenta desde 1: son 4 + 1 + 5 + 9 = 19.- Al sumarle 10 a la posición 4, el mismo rango da 29 sin reconstruir nada:
sumartocó sólo unas pocas casillas. - Los últimos renglones enseñan el bit más bajo: 2, 8 y 4.