Fenwick tree

Overview

A Fenwick tree (binary indexed tree, BIT) supports point updates and prefix sums in O(log n) with a single array of size n + 1 and about ten lines of code. Each index i stores the sum of a block of elements whose length is the lowest set bit of i, computed as i & -i.

To get a prefix sum you jump down by removing the lowest set bit; to update you jump up by adding it. Range sums are prefix(r) - prefix(l - 1). It is the shortest way to solve dynamic prefix-sum and counting problems such as inversions and count of smaller numbers after self.

When to use it

• Prefix sums or range sums with point updates.
• Counting inversions or elements smaller / greater than x seen so far.
• Frequency tables with rank queries after coordinate compression.
• You want less code than a segment tree and the operation is invertible (sum, xor).

Problem patterns it solves

Where it is used in real software

Key terms

Lowest set bit

i & -i: the value of the rightmost 1 bit, e.g. 12 & -12 = 4.

1-indexed

Fenwick trees use indexes 1..n; index 0 is unused.

tree[i]

Sum of elements (i - lowbit(i), i].

Coordinate compression

Map large or negative values to ranks 1..m before using them as indexes.

How it works, step by step

1. 1
   Update(i, delta)

   While i <= n: tree[i] += delta; i += i & -i. Moves to every block that contains i.

2. 2
   Prefix(i)

   sum = 0; while i > 0: sum += tree[i]; i -= i & -i. Collects disjoint blocks.

3. 3
   Range(l, r)

   prefix(r) - prefix(l - 1).

4. 4
   Build

   Call update for every element (O(n log n)), or use the O(n) parent-propagation build.

prefix(13) and which blocks it adds

13 in binary is 1101

prefix(13) = tree[13] + tree[12] + tree[8]: three lookups, one per set bit of 13. Updates walk the opposite direction: 5 -> 6 -> 8 -> 16 by adding the lowest bit.

Implementation

1class FenwickTree {2  constructor(n) {3    this.n = n;4    this.tree = new Array(n + 1).fill(0); // 1-indexed5  }6  update(i, delta) {7    for (; i <= this.n; i += i & -i) this.tree[i] += delta;8  }9  prefix(i) {10    let sum = 0;11    for (; i > 0; i -= i & -i) sum += this.tree[i];12    return sum;13  }14  range(l, r) {15    return this.prefix(r) - this.prefix(l - 1);16  }17}18 19// 307 using 0-indexed API on top of the 1-indexed tree20class NumArray {21  constructor(nums) {22    this.nums = nums.slice();23    this.bit = new FenwickTree(nums.length);24    nums.forEach((x, i) => this.bit.update(i + 1, x));25  }26  update(index, val) {27    this.bit.update(index + 1, val - this.nums[index]);28    this.nums[index] = val;29  }30  sumRange(left, right) {31    return this.bit.range(left + 1, right + 1);32  }33}34 35// 315. Count of Smaller Numbers After Self36function countSmaller(nums) {37  const sorted = [...new Set(nums)].sort((a, b) => a - b);38  const rank = new Map(sorted.map((v, i) => [v, i + 1]));39  const bit = new FenwickTree(sorted.length);40  const result = new Array(nums.length);41  for (let i = nums.length - 1; i >= 0; i--) {42    const r = rank.get(nums[i]);43    result[i] = bit.prefix(r - 1); // how many smaller values are to the right44    bit.update(r, 1);45  }46  return result;47}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using index 0.

  Fix: i & -i is 0 for i = 0, causing an infinite loop. Shift all indexes by 1.

• Updating with the new value instead of the difference.

  Fix: Pass delta = newValue - oldValue.

• Large or negative values as indexes.

  Fix: Compress coordinates to ranks 1..m first.

Interview questions

Practice problems