Algorithms · 11 min

Fenwick tree

Running totals that stay fast while the numbers keep changing, in one plain array the same size as the data. The binary of each position does the work.

A ramen shop in Osaka writes down how many bowls it sells each day. The owner keeps asking one question: “how many bowls from day 1 up to day 13?”

Corrections also keep arriving. A late receipt turns up, and day 5 needs 3 more bowls. Here is the puzzle: make both the question and the correction fast, using one plain array of numbers the same length as the list of days, and nothing else.

Two easy answers that each fail half the job

Keep the raw daily counts. A correction is one write. But “total up to day 13” means reading 13 numbers, and up to day 1,000,000 means reading a million.

Or keep running totals: slot r holds days 1 to r added up. Now the question is one read. But a correction to day 5 changes the total for day 5, 6, 7 and every day after it. With a million days, that is up to a million writes.

One layout makes reads slow, the other makes writes slow. A Fenwick tree (also called a binary indexed tree) sits in between: each slot holds a total for a block of days, and the blocks have different lengths.

Each slot holds a block, sized by its binary

Write a slot’s position in binary and look at its rightmost 1. Call that the lowest 1 bit (the demo calls it the lowest set bit). For 12 = 1100 the rightmost 1 is in the 4s place, so its lowest 1 bit is 4. For any odd number it is 1.

The rule is: slot i holds the total of the block of days that ends at day i and is as long as i’s lowest 1 bit. Slot 12 holds 4 days, 9 to 12. Slot 13 holds 1 day, just 13. Slot 8 = 1000 holds 8 days, 1 to 8.

Days are numbered from 1, not 0, because 0 has no 1 bits and would hold nothing. Here are all 16 slots for the shop’s first 16 days:

It is still one array of 16 numbers, the same size as the data. Only what each slot means has changed. In the demo each slot is drawn as a bar labelled t[i], as wide as its block; stacked by width, the bars look like a tree, which is where the name comes from.

Adding up days 1 to 13 by hand

Start at slot 13 and keep crossing off the lowest 1 bit until nothing is left:

1. 13 = 1101. Lowest 1 bit is 1, so slot 13 holds day 13: 8 bowls. Cross off that bit: 1100 = 12.
2. 12 = 1100. Lowest 1 bit is 4, so slot 12 holds days 9–12: 37 bowls. Cross it off: 1000 = 8.
3. 8 = 1000. Lowest 1 bit is 8, so slot 8 holds days 1–8: 88 bowls. Cross it off: 0, so stop.

Total: 8 + 37 + 88 = 133 bowls, from 3 reads instead of 13. The blocks fit end to end (13, then 9–12, then 1–8) because of how the blocks are sized. Slot 12 holds the 4 days ending at 12, which is 9–12. Crossing off its bit gives 12 − 4 = 8, the day just before that block. Every slot works the same way: subtracting the block’s length lands one day before it starts.

The number of reads is the number of 1s in the binary. 13 has three 1s, so three reads.

A correction climbs instead of falling

Adding 3 bowls to day 5 must fix every slot whose block includes day 5. To find them, do the opposite of the query: add the lowest 1 bit instead of crossing it off.

Four writes. Check the full table of 16 slots: these four are the only blocks that reach day 5. Slot 4 stops at day 4, slot 7 starts at day 7, slot 12 starts at day 9, and so on.

Each jump lands on a longer block that still reaches back to day 5; in the demo it is a bar higher up, spanning day 5. Try another day against the table: day 12 climbs 12 → 16, two writes.

This is also how the slots get filled at the start: begin with all zeros and call this correction once per day with that day’s bowls.

Any range from two totals

Days 4 to 13 is the total up to 13 minus the total up to 3: 133 − (20 + 19) = 94. A total from day 1 is called a prefix sum, so any range is two prefix sums subtracted.

Why it stays small at a million days

A query does one read per 1 in the binary. A correction moves the lowest 1 bit at least one place to the left on every jump. Either way, the work is capped by how many binary digits the day number has.

A million needs 20 binary digits (2 to the power 20 is 1,048,576). So any total or any correction over a million days takes at most 20 steps. A billion days: at most 30 (2 to the power 30 is about 1.07 billion).

Finding the lowest 1 bit in one line

In code, the lowest 1 bit of i is i & -i. & is “bitwise AND”: it keeps a 1 only where both numbers have a 1. For 12 that gives 4, for 13 it gives 1. You can use it as a recipe without knowing why it works.

With that, the whole structure is two short loops, where n is the number of days. Look for the only difference: the query subtracts the lowest bit and goes down, the correction adds it and goes up.

lowbit(i):
    return i & -i

total_up_to(day):              # days 1..day
    total = 0
    i = day
    while i > 0:
        total += tree[i]
        i -= lowbit(i)
    return total

add(day, bowls):
    i = day
    while i <= n:
        tree[i] += bowls
        i += lowbit(i)

When to reach for it

Ranges come from subtracting two totals. That subtraction is also the limit.

• It works for anything you can undo by subtracting: sums and counts. For a game leaderboard, give each score a slot holding how many players have that score; the total up to 899 is “how many players scored below 900”. When a player’s score changes, subtract 1 from the old score’s slot and add 1 to the new one.
• It cannot give the smallest or largest value in a range, because there is no way to subtract a minimum. A segment tree, which stores totals for halves and halves of halves (it has its own article), can, at 2 to 4 times the memory.
• If the numbers never change, plain running totals are simpler: one read per question.

Peter Fenwick published it in 1994 for data compression, where a table of letter counts needs running totals and changes after every letter read.