jsschools

Fenwick Tree (Binary Indexed Tree)

A compact array-based structure that computes prefix sums and supports point updates in O(log n) with O(n) space — simpler and faster in practice than a segment tree for sum queries.

Spec ↗

Syntax

class FenwickTree {
  constructor(n) { this.tree = new Array(n + 1).fill(0); }
  update(i, delta) { for (; i < this.tree.length; i += i & -i) this.tree[i] += delta; }
  query(i)  { let s = 0; for (; i > 0; i -= i & -i) s += this.tree[i]; return s; }
  range(l, r) { return this.query(r) - this.query(l - 1); }
}

Parameters

NameTypeRequiredDescription
n number Yes The size of the array (values are 1-indexed in a Fenwick tree).

Returns

FenwickTree — A new Fenwick Tree instance initialized to all zeros.

Examples

class FenwickTree {
  #t;
  constructor(n) { this.#t = new Array(n + 1).fill(0); }
  update(i, delta) { for (; i < this.#t.length; i += i & -i) this.#t[i] += delta; }
  query(i)         { let s = 0; for (; i > 0; i -= i & -i) s += this.#t[i]; return s; }
  range(l, r)      { return this.query(r) - this.query(l - 1); }
}

// Build from array
const arr = [1, 3, 5, 7, 9, 11];
const ft = new FenwickTree(arr.length);
arr.forEach((v, i) => ft.update(i + 1, v)); // 1-indexed

console.log(ft.query(4));     // prefix sum [1..4] = 1+3+5+7
console.log(ft.range(2, 5));  // range sum  [2..5] = 3+5+7+9
ft.update(3, 4);              // arr[3] += 4 (5 → 9)
console.log(ft.query(4));     // updated prefix sum
Output 
16
24
20

// Count inversions in an array using a Fenwick tree
function countInversions(arr) {
  const n = arr.length;
  const sorted = [...new Set(arr)].sort((a, b) => a - b);
  const rank = new Map(sorted.map((v, i) => [v, i + 1]));
  const ft = new FenwickTree(n);
  let inv = 0;
  for (const v of arr) {
    const r = rank.get(v);
    inv += ft.query(n) - ft.query(r); // elements seen > v
    ft.update(r, 1);
  }
  return inv;
}
console.log(countInversions([3, 1, 2, 4]));
Output 
2

Notes

| Operation | Time | Space | |-------------|---------|-------| | Build | O(n) | O(n) | | Point update | O(log n)| O(1) | | Prefix query | O(log n)| O(1) | | Range query | O(log n)| O(1) | The key trick: `i & -i` isolates the lowest set bit of i, giving the "responsibility range" of each index. Fenwick trees are 1-indexed by convention. Compared to a segment tree: simpler code, lower constant factor, but supports only associative-invertible operations (sum, XOR — not min/max).

See also