TreesTrees

Fenwick Tree (Binary Indexed Tree)

A compact array-based tree that supports prefix-sum queries and point updates in O(log n) using the binary representation of indices.

Learn Fenwick Tree →
a
·
0
0
1
0
2
0
3
0
4
0
5
0
6
0
7
0
8
a (1-based)
·
0
3
1
2
2
-1
3
6
4
5
5
4
6
-3
7
3
8
1/32Build a Fenwick tree over 8 values (1-based). tree[i] will cover the `i & -i` elements ending at i — the lowest set bit of i decides the range length.
Current index iVisited on this walkUpdatedSummed into the answer
PseudocodeLearn Fenwick Tree →
1build: tree[i] += a[i]; j = i + (i & -i); if j <= n: tree[j] += tree[i]
2update(i, delta): while i <= n: tree[i] += delta; i += i & -i
3prefix(i): s = 0; while i > 0: s += tree[i]; i -= i & -i; return s
4range(l, r) = prefix(r) - prefix(l-1)
Variables
n8
Complexity
access O(log n)
search O(log n)
insert —
delete —
Speed