Drzewo Fenwicka wspiera sumy prefiksowe i aktualizacje punktowe w O(log n) przy pamięci O(n). Użyj go, gdy masz dużo update’ów i zapytań typu „suma [0..i]” (np. problemy z częstotliwościami/licznikami).
class Fenwick {
private bit: number[];
constructor(n: number) {
this.bit = Array(n + 1).fill(0);
}
add(i: number, delta: number) {
for (let x = i + 1; x < this.bit.length; x += x & -x) this.bit[x] += delta;
}
sum(i: number) {
let res = 0;
for (let x = i + 1; x > 0; x -= x & -x) res += this.bit[x];
return res;
}
}