Home/Trees/Fenwick tree
Search algorithmsCTRL K

Fenwick tree

· prefix sums by clearing the lowest bit
/trees/fenwick-tree
TOUCHED
0
nodes in this operation
OPERATION
build
running now
ANSWER
—
of the current query
SIZE
8
values in the array
HEIGHT
4
levels, root included
currentupdate chainsummed in the queryupdated
n = 8 · seed 7 · 31 steps
step 0 / 30
Values8
fenwick_tree.ts
1
class Fenwick {
2
  tree: number[]; constructor(size: number) { this.tree = new Array(size + 1).fill(0); }
3
  add(index: number, delta: number) {
4
    for (let i = index + 1; i < this.tree.length; i += i & -i) {
5
      this.tree[i] += delta;
6
    }
7
  }
8
  prefix(count: number) {
9
    let sum = 0;
10
    for (let i = count; i > 0; i -= i & -i) {
11
      sum += this.tree[i];
12
    }
13
    return sum;
14
  }
15
  rangeSum(from: number, to: number) { return this.prefix(to + 1) - this.prefix(from); }
16
  static build(values: number[]) {
17
    const fenwick = new Fenwick(values.length); values.forEach((value, index) => fenwick.add(index, value));
18
    return fenwick;
19
  }
20
}
CURRENT STEP
line 2

A Fenwick tree over 8 values. Node i stores the sum of the range (i − lowbit(i), i], where lowbit is the lowest set bit of i.

// how it works

Understanding Fenwick tree

Fenwick · an array that hides a tree in its indices
01

The idea

A Fenwick tree, or binary indexed tree, is a plain array of n + 1 numbers where slot i holds the sum of a range that ends at i and whose length is the lowest set bit of i: slot 6 (110₂) covers two values, slot 8 (1000₂) covers eight. Those ranges nest into a tree, and the tree is never stored: the parent of i on a prefix query is i minus its lowest bit, and on an update i plus it.

A prefix sum walks down from i clearing the lowest bit each time, so it adds at most log n slots. A point update walks up adding the lowest bit, touching the log n slots whose range covers the index. Twenty lines and no pointers, which is why it is the usual answer when the operation can be undone, as sums can.

02

The four stages

1
lowbiti & −i: the lowest set bit of i
2
addclimb i += lowbit(i), adding the delta
3
prefixdescend i −= lowbit(i), summing the slots
4
rangesum(a..b) = prefix(b + 1) − prefix(a)
03

Complexity

best
O(1)prefix of a power of two: one slot
average
O(log n)half the bits set on average
worst
O(log n)all bits set: log n slots
space
O(n)n + 1 integers, nothing else
04

Versus its siblings

OPERATIONS PER QUERY + UPDATE · 1 000 000 VALUES
segment tree
20
fenwick
20
sqrt decomposition
2,000
prefix sums (query)
1
plain array (update)
1
prefix sums answer in 1 but rebuild in n on every update; a plain array is the opposite
05

Pseudocode

ADD(index, delta): i ← index + 1; while i ≤ n: tree[i] += delta; i ← i + lowbit(i)
PREFIX(count): sum ← 0; i ← count; while i > 0: sum += tree[i]; i ← i − lowbit(i); return sum
RANGE(a, b) = PREFIX(b + 1) − PREFIX(a)
lowbit(i) = i & −i, the value of the lowest set bit
06

When to use

Prefix sums and counts that change: inversion counting, order statistics, frequency tables, cumulative scores.
Anywhere a segment tree would do but memory and code size matter and the operation is invertible.
07

Pitfalls

Indices are 1-based inside the tree; forgetting the +1 breaks lowbit at index 0.
Minimum and maximum cannot be undone, so range min needs a segment tree, not this.
Building by n adds is O(n log n); the linear build pushes each slot into its parent once.
08

History

Boris Ryabko proposed the structure in 1989 and Peter Fenwick described it independently in 1994 for cumulative frequency tables in arithmetic coding, where every symbol updates a count and every decode needs a prefix sum. It is now a fixture of competitive programming under the name binary indexed tree.

Back to Trees