Lesson 36.1 · Advanced Data Structures
Fenwick Trees (Binary Indexed Trees)
bit[i] stores the sum of a block ending at i whose length is the lowest set bit of i. A prefix sum adds O(log n) blocks; an update fixes O(log n) blocks.
16 min
Think of it like this
A library that keeps running totals at a few shelves: shelf 4 knows books 1–4, shelf 6 knows 5–6, shelf 7 knows just 7. To count books 1–7 you ask shelves 7, 6 and 4 instead of all seven.
1.Blocks from the lowest set bit
With 1-based indices, bit[i] covers (i − lowbit(i), i] where lowbit(i) = i & −i. So bit[4] covers 1..4, bit[6] covers 5..6, bit[7] covers 7, bit[8] covers 1..8.
prefix(i): add bit[i], then i −= lowbit(i), until i = 0. add(i, delta): bit[i] += delta, then i += lowbit(i), until past n. Both loops run at most log₂ n times.
A Fenwick tree handles anything you can add and subtract (sums, counts). For min or max over arbitrary ranges, use a segment tree.
bit[1..8] = [5, 6, 4, 12, 3, 9, 2, 24]Step 1/4bit[i] covers (i − lowbit(i), i]: bit[2] = a1 + a2 = 6, bit[4] = a1..a4 = 12, bit[6] = a5 + a6 = 9, bit[8] = all = 24.
Remember
- lowbit(i) = i & −i.
- Query: subtract lowbit. Update: add lowbit.
- Range sum = prefix(r) − prefix(l − 1).
Common mistakes
- Using index 0 (lowbit(0) = 0 loops forever): shift to 1-based.
- Setting a value instead of adding the difference.
Words used in this lesson
- Fenwick tree / BIT
- A compact array that supports prefix sums and point updates in O(log n).
- Point update
- Changing one element.