← Data structures from scratch · Lesson 30/32
Range sums: prefixes and Fenwick
Prefix sums: pay once, ask a thousand times
If you're asked many times "how much was sold from day 2 to day 5?", adding up the stretch every time costs O(n) per question. Better to build the prefix sums array once: pre[i] is the sum of the first i items, with pre[0] = 0.
The sum from a to b (inclusive) is then pre[b + 1] - pre[a]: everything up to b, minus what came before a. One subtraction, O(1), no matter how long the stretch is.
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
prehas one more item thanventasand only grows (when there are no negatives).suma(2, 5)ispre[6] - pre[2]= 23 − 4 = 19, the same as 4 + 1 + 5 + 9, the highlighted cells.- The total, 31, is the last item of
pre.
The whole lesson on one page
Prefix sums: pay once, ask a thousand times
If you're asked many times "how much was sold from day 2 to day 5?", adding up the stretch every time costs O(n) per question. Better to build the prefix sums array once: pre[i] is the sum of the first i items, with pre[0] = 0.
The sum from a to b (inclusive) is then pre[b + 1] - pre[a]: everything up to b, minus what came before a. One subtraction, O(1), no matter how long the stretch is.
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));
prehas one more item thanventasand only grows (when there are no negatives).suma(2, 5)ispre[6] - pre[2]= 23 − 4 = 19, the same as 4 + 1 + 5 + 9, the highlighted cells.- The total, 31, is the last item of
pre.
The same idea with products
The "product of array except self" challenge asks, for each position, for the product of all the others, without dividing and in O(n). It's a cousin of prefix sums: in a left-to-right pass you store the product of everything before; in a right-to-left pass you multiply by everything after.
This works even when there's a zero, which is exactly where dividing would fail.
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]));
- For
[1, 2, 3, 4]: 24 = 2·3·4, 12 = 1·3·4, 8 = 1·2·4 and 6 = 1·2·3. - With the zero, only the zero's own position gets something other than 0: 2·5 = 10.
When the data changes: the Fenwick tree
Prefix sums have a problem: if a value changes, everything after it must be recomputed, O(n). The Fenwick tree (or binary indexed tree) spreads the difference: each slot arbol[i] stores the sum of a stretch that ends at i and is i & -i long.
i & -i is the lowest set bit of i: for 6 (110 in binary) it's 2, for 8 (1000) it's 8, for 12 (1100) it's 4. To query you go down subtracting that bit; to update you go up adding it. Each path has at most log₂ n steps: both operations are O(log n).
Indices start at 1, because 0 & -0 is 0 and the loop would never move.
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)counts from 1: that's 4 + 1 + 5 + 9 = 19.- After adding 10 to position 4, the same range gives 29 without rebuilding anything:
sumaronly touched a few slots. - The last lines show the lowest bit: 2, 8 and 4.