dsa.guide
Tracks
61 topics · 8 tracks

Fenwick tree

A Fenwick tree, or binary indexed tree, is one array of partial sums. Cell i holds the sum of a block ending at i, and the block's length is i's lowest 1 bit. Adding that bit moves to the next cell to update; clearing it moves to the next block of a prefix sum.

O(log n)one arraycounts from 1
[5, 8, 6, 3, 2, 7, 2, 6]sum up to 6
58632726

tree[i], labelled by i in binary

0
1
0
10
0
11
0
100
0
101
0
110
0
111
0
1000

Add the 8 values into a Fenwick tree, then sum positions 0 to 6. Cell i holds the sum of the last lowbit(i) positions up to i, where lowbit is i's lowest 1 bit.

value being addedcovered by this tree cellbeyond the prefix 
1function add(tree, i, delta) {2  for (i++; i < tree.length; i += i & -i) tree[i] += delta;3}45function prefixSum(tree, i) {6  let sum = 0;7  for (i++; i > 0; i -= i & -i) sum += tree[i];8  return sum;9}

Keys: Space play or pause, ← → step. The URL always points at the frame you are on.

What it costs

CaseTimeWhen
best1a prefix whose length is a power of two: one cell
averagelog nper prefix sum or per update
worstlog none cell per 1 bit of the index
spacenone cell per value, no pointers

Where it breaks

  • Off-by-one indexes. i & -i is 0 when i is 0, so the loop would never move. That is why the tree counts from 1 and both functions start with i++. Mixing 0-based and 1-based indexes is the usual Fenwick bug.
  • Powers of two are cheap. Pick Sum up to 7: 8 positions is 1000 in binary, one 1 bit, so the answer is a single cell. Sum up to 6 is 7 positions, 111 in binary, so it takes three.
  • Less flexible than a segment tree. It does prefix sums, and so any range sum by subtracting two of them, in less code and memory. For range minimum or maximum, use a segment tree.