Fenwick Tree (Binary Indexed Tree)

Træ

En space-efficient datastruktur til cumulative frequency tables og prefix sum queries i O(log n) tid.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(log n)`
Search	`O(log n) for prefix sum`
Insertion	`O(log n) for update`
Deletion	`O(log n) for update`

Beskrivelse

Fenwick Tree, også kaldet Binary Indexed Tree (BIT), er en genial datastruktur opfundet af Peter Fenwick i 1994. Den løser samme problem som Segment Tree - effektive range queries og point updates - men med halvt så meget plads (O(n) vs O(4n)) og simplere implementation. Tricket ligger i hvordan data organiseres: hver position i i Fenwick Tree 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 prefix sum fra 0 til i, summer vi værdier ved positioner fundet ved gentagne gange at fjerne den sidste set bit. For at opdatere element i, propagerer vi ændringen til alle positioner der indeholder i i deres interval ved at tilføje den sidste set bit. Dette bit manipulation trick gør operations ekstremt effektive. Fenwick Trees bruges primært til sum queries, men kan også håndtere andre invertible operations. De er mindre alsidige end Segment Trees (kan ikke range update lige så let), men perfekte når du kun har brug for prefix sums eller point updates.

Kode Eksempel

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

  // Initialize from 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;
  }

  // Add delta to element at index (0-indexed)
  update(index, delta) {
    index++; // Convert to 1-indexed
    while (index <= this.size) {
      this.tree[index] += delta;
      index += index & (-index); // Add last set bit
    }
  }

  // Get prefix sum from 0 to index (0-indexed)
  prefixSum(index) {
    index++; // Convert to 1-indexed
    let sum = 0;
    while (index > 0) {
      sum += this.tree[index];
      index -= index & (-index); // Remove last set bit
    }
    return sum;
  }

  // Get sum of range [left, right] (0-indexed, inclusive)
  rangeSum(left, right) {
    if (left > 0) {
      return this.prefixSum(right) - this.prefixSum(left - 1);
    }
    return this.prefixSum(right);
  }

  // Set value at index (not add)
  set(index, value) {
    const currentValue = this.rangeSum(index, index);
    const delta = value - currentValue;
    this.update(index, delta);
  }

  // Get value at index
  get(index) {
    return this.rangeSum(index, index);
  }
}

// 2D Fenwick Tree for matrix range sums
class FenwickTree2D {
  constructor(rows, cols) {
    this.rows = rows;
    this.cols = cols;
    this.tree = Array(rows + 1).fill(0)
      .map(() => Array(cols + 1).fill(0));
  }

  update(row, col, delta) {
    row++; col++;
    for (let i = row; i <= this.rows; i += i & (-i)) {
      for (let j = col; j <= this.cols; j += j & (-j)) {
        this.tree[i][j] += delta;
      }
    }
  }

  prefixSum(row, col) {
    row++; col++;
    let sum = 0;
    for (let i = row; i > 0; i -= i & (-i)) {
      for (let j = col; j > 0; j -= j & (-j)) {
        sum += this.tree[i][j];
      }
    }
    return sum;
  }

  rangeSum(r1, c1, r2, c2) {
    return this.prefixSum(r2, c2) 
      - this.prefixSum(r1 - 1, c2)
      - this.prefixSum(r2, c1 - 1)
      + this.prefixSum(r1 - 1, c1 - 1);
  }
}

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

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

ft.update(3, 4); // Add 4 to arr[3]
console.log('After update, range sum [2, 7]:', ft.rangeSum(2, 7)); // 18

ft.set(2, 5); // Set arr[2] to 5 (was -1)
console.log('After set, range sum [2, 7]:', ft.rangeSum(2, 7)); // 24

// 2D example
const ft2d = new FenwickTree2D(5, 5);
ft2d.update(2, 2, 10);
ft2d.update(3, 3, 20);
console.log('2D Range sum:', ft2d.rangeSum(1, 1, 3, 3)); // 30

Anvendelsesområder

•Cumulative frequency tables
•Dynamic prefix sums
•Inversion count i arrays
•2D matrix range sum queries
•Coordinate compression problems

Fordele

✓Space efficient O(n) (halvdelen af Segment Tree)
✓Simplere implementation end Segment Tree
✓Konstant factor hurtigere end Segment Tree
✓Elegant bit manipulation tricks
✓Kan udvides til 2D og højere dimensioner

Ulemper

✗Kun for invertible operations (sum, XOR, ikke min/max)
✗Range updates kræver difference array trick
✗Mindre intuitiv end Segment Tree
✗1-indexing kan være confusing
✗Svær at debugge ved fejl

Eksempler fra den virkelige verden

•Online judge systems - submission statistics
•E-commerce inventory tracking (stock levels)
•Financial systems - cumulative transactions
•Gaming - dynamic leaderboard rankings
•Social media - cumulative likes/views over time

Relaterede strukturer

Segment TreeArrayBinary TreePrefix Sum Array