Fenwick-træ (binært indekseret træ)

Træ

En pladseffektiv datastruktur til kumulative frekvenstabeller og præfikssumforespørgsler i O(log n) tid.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(log n)`
Search	`O(log n) for præfikssum`
Insertion	`O(log n) for opdatering`
Deletion	`O(log n) for opdatering`

Beskrivelse

Fenwick-træet, også kaldet binært indekseret træ (BIT), er en genial datastruktur opfundet af Peter Fenwick i 1994. Den løser samme problem som segmenttræer - effektive intervalforespørgsler og punktopdateringer - men med halvt så meget plads (O(n) mod O(4n)) og simplere implementering. Tricket ligger i hvordan data organiseres: hver position i i Fenwick-træet gemmer summen af elementer fra et interval bestemt af i's binære repræsentation. Specifikt gemmer position i summen af de sidste (i & -i) elementer. For at finde præfikssum fra 0 til i, summerer vi værdier ved positioner fundet ved gentagne gange at fjerne den sidste satte bit. For at opdatere element i, propagerer vi ændringen til alle positioner der indeholder i i deres interval ved at tilføje den sidste satte bit. Dette bitmanipulationstrick gør operationer ekstremt effektive. Fenwick-træer bruges primært til sumforespørgsler, men kan også håndtere andre inverterbare operationer. De er mindre alsidige end segmenttræer (kan ikke lave intervalopdateringer lige så let), men perfekte når du kun har brug for præfikssummer eller punktopdateringer.

Kode Eksempel

// JavaScript Fenwick Tree (Binary Indexed Tree) Implementation
class FenwickTree {
  constructor(size) {
    this.size = size;
    this.tree = new Array(size + 1).fill(0);
  }

  // Initialiser fra array
  static fromArray(arr) {
    const ft = new FenwickTree(arr.length);
    for (let i = 0; i < arr.length; i++) {
      ft.update(i, arr[i]);
    }
    return ft;
  }

  // Tilføj delta til element på indeks (0-indekseret)
  update(index, delta) {
    index++; // Konverter til 1-indekseret
    while (index <= this.size) {
      this.tree[index] += delta;
      index += index & (-index); // Tilføj sidste satte bit
    }
  }

  // Få præfikssum fra 0 til indeks (0-indekseret)
  prefixSum(index) {
    index++; // Konverter til 1-indekseret
    let sum = 0;
    while (index > 0) {
      sum += this.tree[index];
      index -= index & (-index); // Fjern sidste satte bit
    }
    return sum;
  }

  // Få sum af interval [left, right] (0-indekseret, inklusiv)
  rangeSum(left, right) {
    if (left > 0) {
      return this.prefixSum(right) - this.prefixSum(left - 1);
    }
    return this.prefixSum(right);
  }
}

// Brug
const arr = [3, 2, -1, 6, 5, 4, -3, 3, 7, 2];
const ft = FenwickTree.fromArray(arr);

console.log('Præfikssum [0, 5]:', ft.prefixSum(5)); // 3+2-1+6+5+4 = 19
console.log('Intervalsum [2, 7]:', ft.rangeSum(2, 7)); // -1+6+5+4-3+3 = 14

ft.update(3, 4); // Tilføj 4 til arr[3]
console.log('Efter opdatering, intervalsum [2, 7]:', ft.rangeSum(2, 7)); // 18

Anvendelsesområder

•Kumulative frekvenstabeller
•Dynamiske præfikssummer
•Inversionstal i arrays
•2D matrix intervalsumforespørgsler
•Koordinatkomprimeringsproblemer

Fordele

✓Pladseffektiv O(n) (halvdelen af segmenttræ)
✓Simplere implementering end segmenttræ
✓Konstant faktor hurtigere end segmenttræ
✓Elegant bitmanipulationstricks
✓Kan udvides til 2D og højere dimensioner

Ulemper

✗Kun for inverterbare operationer (sum, XOR, ikke min/max)
✗Intervalopdateringer kræver difference array-trick
✗Mindre intuitiv end segmenttræ
✗1-indeksering kan være forvirrende
✗Svær at fejlfinde ved fejl

Eksempler fra den virkelige verden

•Online bedømmelsessystemer - indleveringsstatistik
•E-handel lagersporing (lagerniveauer)
•Finansielle systemer - kumulative transaktioner
•Spil - dynamiske rangliste-placeringer
•Sociale medier - kumulative likes/visninger over tid

Relaterede strukturer

Segment TreeArrayBinary TreePrefix Sum Array