Expert · Module 26 · Lesson 4 of 4
Fenwick trees
The lowest set bit decides how many elements each cell owns, which buys prefix sums and point updates in O(log n) with one array of n plus 1 cells and a loop short enough to hold in your head.
By the end you can
- Explain which elements bit[i] covers and why i and -i finds the next cell in both walks
- Run add and sum on an eight-element tree, and build one from a raw array in O(n)
- Compare a Fenwick tree with a segment tree for sums, and reuse the walk to find an order statistic
Builds on Index arithmetic, Prefix sums.
01 · A question first
Prefix sums give O(1) range sums but die on the first update. A segment tree fixes that at 2n to 4n cells of pointer-free but still branching code. There is a third answer: let each cell own a block of elements whose length is the lowest set bit of its index, and you get both operations in O(log n), in one flat array, with a two-line loop.
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- From prefix sums to an array of blocks
- What each cell is responsible for
- Updating and querying by walking
- Building the table in O(n)
- Why it beats a segment tree for sums
- The same walk counts things
- Where it is used
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
03 · Practice
Something wrong with this lesson? Report a problem