Fenwick Trees

In short: a Fenwick tree keeps one flat list where cell i owns a range of i & -i minutes ending at i, found with the lowest-set-bit trick. A prefix query jumps down, clearing the lowest set bit each step; a point update jumps up, adding it — both in O(log n) hops. It needs an aggregate with an inverse (sum, count, XOR), because a range answer is still prefix minus prefix; min has no inverse, which is what the segment tree is for.

A Fenwick list of 8 cells; T[4] is labelled "owns 1-4", and prefix(7) reads T[7], T[6] and T[4]

Square-root blocks got Quarry to O(√n) for both edits and queries. On a month-long log that is a couple of hundred reads, which is fine for one dashboard and not fine for the live counter on Quarry's status page. There, every incoming request is an edit and every refresh is a query, thousands of each per second.

The block idea had one level of summaries. What if there were summaries of summaries, and summaries of those, each level twice as coarse as the one below? Then any prefix could be assembled from about log₂ n pieces. A Fenwick tree (also called a binary indexed tree) does exactly that, and it does it in a single flat list the same length as the log, with no pointers and no nodes. It needs one bit trick. Everything else follows from it.

The lowest set bit

For a positive integer i, i & -i keeps only its lowest 1 bit. Python's integers are two's-complement for bitwise operations, so -i is "flip every bit and add one", which leaves the lowest set bit as the only bit the two share.

python

What does this print?

print(12 & -12, 10 & -10, 7 & -7)

Each cell owns a range

Number the minutes from 1 (the tree needs it, as you'll see). Cell i of the Fenwick list stores the total of a range that ends at i and is i & -i minutes long:

T[i] = total of minutes (i − (i & −i), i]

Odd cells own one minute. Cell 2 owns minutes 1–2, cell 4 owns 1–4, cell 6 owns 5–6, cell 8 owns 1–8. The ranges nest like the markings on a ruler.

To total minutes 1..i, take T[i], which covers the top i & -i minutes, then jump down to i − (i & -i) and repeat. Each jump clears the lowest set bit, so there are at most as many jumps as i has 1-bits: O(log n).

To add to minute i, change every cell whose range contains it. They are found by jumping up: i += i & -i. Each jump carries the bit up, so there are O(log n) of them too.

The labels under each cell below show the range it owns. Watch a prefix query walk down, then an edit walk up:

watch it move · array

A prefix query clears the lowest set bit at each jump, and an update adds it. Each cell's label is the range of minutes it owns, and each is as long as that bit.

The log is 5, 2, 7, 1, 3, 4, 6, 2 in minutes 1..8. Cell 0 is never used, because 0 has no lowest set bit. 9 cells. 1 ruled out.

1 / 8

The one-indexing is not a style choice: at index 0, 0 & -0 is 0, the jump never moves, and the loop never ends. Quarry's API stays 0-indexed, and the tree adds 1 on the way in.

What does this print?

i = 13
path = []
while i > 0:
    path.append(i)
    i -= i & -i
print(path)

The code

Two loops of three lines each:

python

A range l..r is two prefixes subtracted, the same trick as lesson 1. So a Fenwick tree needs an aggregate you can subtract. Sums, counts and XOR work. Minimum doesn't, which is why lesson 4 exists.

Trace one prefix query and watch i lose a bit each time round:

step through it

1tree = [0, 5, 7, 7, 15, 3, 7, 6, 30]

2i = 6

3total = 0

4while i > 0:

5 total += tree[i]

6 i -= i & -i

7print(total)

Now your own copy. Change the log, the minute being edited, or the prefix being asked for, and run it:

your code, drawn · array

Your Fenwick tree. The query touches one cell per 1-bit of q.

Building in O(n)

Calling add once per minute builds the tree in O(n log n). There is a faster way: fill each cell with its own minute, then push every cell's total into the one cell directly above it, i + (i & -i), in increasing order. By the time a cell is pushed, everything below it has already arrived. Here's a teammate's attempt that forgot the push:

broken — fix it

Minutes 1..4 total 5 + 2 + 7 + 1 = 15, but this prints 1. Each cell holds only its own minute, not the range it owns.

❓ Cross-question — "It's called a tree. Where are the nodes?" The parent links are arithmetic. Cell i's parent for updates is i + (i & -i), and for queries it's i − (i & -i). The tree exists only in those two formulas, which is why a Fenwick tree is n + 1 integers and nothing else, and why it's usually the fastest structure here in practice: it's a flat list, and walking it reads memory the processor has probably already cached.

How many jumps does a query make on a big log? A prefix query makes at most one jump per bit of the index, and 2²⁰ = 1,048,576 is the first power of two past a million, so on a million-minute log every query takes at most 20 jumps. The block walk reads about 2,000 cells on the same log. A thousand times more data costs a Fenwick query only about 10 more jumps.

Idioms & real-world patterns

Range updates, point reads

Put a Fenwick tree over lesson 1's difference array. A range bump is two point adds, and a prefix sum of the differences is the current value of one minute. Both are O(log n). That's the boss exercise.

Counting with a Fenwick tree

Index the tree by value instead of by minute, and "how many values seen so far are smaller than x?" becomes a prefix query. Walk a list once, asking that question before adding each value, and you count the pairs that are out of order in O(n log n). That's the build exercise.

⚡ Advanced — searching down the tree

Because cell 2ᵏ owns exactly the first 2ᵏ values, you can descend by powers of two, from the largest downward, and find the smallest position whose prefix reaches a target without calling prefix at all. It's O(log n) and finds "the k-th smallest value still present". That's the capstone exercise.

Quick practice

What does this print?

i, n = 5, 9
path = []
while i < n:
    path.append(i)
    i += i & -i
print(path)

broken — fix itIndexError

prefix(5) should total tree[5] + tree[4] = 3 + 15 = 18, but i climbs 5 → 6 → 8 → 16 and runs off the list.

🎯 Your turn

Build Quarry's live counter: fenwick_log(values, ops). values is the starting log, 0-indexed. Each op is ["add", i, d] or ["sum", l, r] (both ends included). Keep a Fenwick tree, where minute i lives at index i + 1, and return the answers to the sum ops in order.

fenwick_log([5, 2, 7, 1, 3, 4, 6, 2], [["sum", 0, 6], ["add", 2, 3], ["sum", 2, 4]]) → [28, 14]

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of Quarry is built. ✅

Fenwick Trees

Fenwick Trees

The lowest set bit

Each cell owns a range

The code

Building in O(n)

Idioms & real-world patterns

Range updates, point reads

Counting with a Fenwick tree

⚡ Advanced — searching down the tree

Quick practice

🎯 Your turn

Practice — level up