Struktury danychhard

Do czego służy drzewo Fenwicka (Binary Indexed Tree)?

Tagi

#fenwick#bit#prefix-sum#big-o

Odpowiedź

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;
  }
}

Odpowiedź zaawansowana

Głębiej

Rozwinięcie krótkiej odpowiedzi — co zwykle ma znaczenie w praktyce:

Kontekst (tagi): fenwick, bit, prefix-sum, big-o
Złożoność: porównaj typowe operacje (średnio vs najgorzej).
Inwarianty: co musi być zawsze prawdą, żeby struktura/algorytm działał poprawnie.
Kiedy wybór jest zły: objawy w produkcji (latencja, GC, cache misses).
Wytłumacz "dlaczego", nie tylko "co" (intuicja + konsekwencje).
Trade-offy: co zyskujesz i co tracisz (czas, pamięć, złożoność, ryzyko).
Edge-case’y: puste dane, duże dane, błędne dane, współbieżność.

Przykłady

Poniżej dodatkowy przykład (bazuje na tym, co już jest w odpowiedzi):

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;
  }
}