AlgoScope

Fenwick Tree

structureadvancedTime O(log n)Space O(n)

An array where each cell secretly holds the sum of a short range ending there. The length of that range is the lowest set bit of the index, and that one trick makes both prefix sums and updates cost O(log n).

00102030405060708

Build the tree for 3, 2, 5, 1, 4, 6, 2, 7. Cell i will hold the sum of the lowbit(i) values ending at i, so cell 8 covers 1 to 8, cell 6 covers 5 to 6, and cell 5 covers only 5. Cell 0 is unused.

How it runs, step by step

  1. Build the tree for 3, 2, 5, 1, 4, 6, 2, 7. Cell i will hold the sum of the lowbit(i) values ending at i, so cell 8 covers 1 to 8, cell 6 covers 5 to 6, and cell 5 covers only 5. Cell 0 is unused.

    Building a Fenwick tree over 8 values, indexed from 1.

  2. Cell 1 covers 1 to 1 and now holds 3. Its parent is 1 + lowbit(1) = 2, so 3 is folded in there too.

    Cell 1 holds 3. It also contributes to cell 2.

  3. Cell 2 covers 1 to 2 and now holds 5. Its parent is 2 + lowbit(2) = 4, so 5 is folded in there too.

    Cell 2 holds 5. It also contributes to cell 4.

  4. Cell 3 covers 3 to 3 and now holds 5. Its parent is 3 + lowbit(3) = 4, so 5 is folded in there too.

    Cell 3 holds 5. It also contributes to cell 4.

  5. Cell 4 covers 1 to 4 and now holds 11. Its parent is 4 + lowbit(4) = 8, so 11 is folded in there too.

    Cell 4 holds 11. It also contributes to cell 8.

  6. Cell 5 covers 5 to 5 and now holds 4. Its parent is 5 + lowbit(5) = 6, so 4 is folded in there too.

    Cell 5 holds 4. It also contributes to cell 6.

  7. Cell 6 covers 5 to 6 and now holds 10. Its parent is 6 + lowbit(6) = 8, so 10 is folded in there too.

    Cell 6 holds 10. It also contributes to cell 8.

  8. Cell 7 covers 7 to 7 and now holds 2. Its parent is 7 + lowbit(7) = 8, so 2 is folded in there too.

    Cell 7 holds 2. It also contributes to cell 8.

  9. Cell 8 covers 1 to 8 and now holds 30. No parent within 8.

    Cell 8 holds 30.

  10. Built in one pass. Every cell holds the sum of exactly the range its lowest set bit says it does.

    The Fenwick tree is built.

Write it yourself

Define prefixSum(values, count) and return the sum of the first count values. It runs in your browser against this lesson's own 2 examples.

// Any prefix is a handful of the tree's ranges, found by stripping the lowest set bit off the index one at a time.function prefixSum(values, count) {    return 0;}
Ln 1, Col 16 linesTab indents; Escape then Tab leaves the editor. Ctrl-Enter runs, Cmd-Enter on a Mac.

Remember

  • Cell i covers the lowbit(i) values ending at i. Cell 8 covers 1 to 8, cell 6 covers 5 to 6.
  • Query walks down by subtracting the lowest set bit. Update walks up by adding it.
  • Both walks touch at most one cell per bit of the index, so O(log n) each.

Topics covered

Related

Where this is used

CompressionAdaptive arithmetic coding

An arithmetic coder encodes a symbol from the total frequency of every symbol ranked below it, then bumps that symbol's count so the model keeps adapting to the file. A flat table of running totals makes the lookup one read and the bump O(n); raw per-symbol counts make the bump one write and the lookup O(n). Fenwick published this structure in 1994 for exactly that deadlock, and it puts both halves of the coder's inner loop at O(log n).

Programming librariesAtCoder Library

ACL, the reference library shipped for AtCoder contests, carries fenwick_tree alongside its segment tree even though the segment tree strictly covers more cases. It earns the slot because point-add with prefix-sum is the common case, and for that it is a single array of n values instead of the 2n or 4n a segment tree allocates, with loops short enough to stay in cache on a hot query.

Order statisticsKACTL

A Fenwick tree over counts answers more than prefix sums: it can find the first position where the running total reaches a target. KACTL, the KTH contest library many ICPC teams carry, ships this as lower_bound, walking powers of two down from 1 << 25 and subtracting each cell it steps past, so the search costs one O(log n) descent rather than a binary search that pays for a full prefix query at every step. Hold counts per value and it gives the k-th smallest; hold weights and it draws a weighted sample. It only works while the running totals never fall, which means every stored value has to be non-negative.

GraphicsIntegral images and summed-area tables

A summed-area table answers the sum over any rectangle in four lookups, which is how Viola-Jones face detection scores thousands of candidate windows per frame and how a box blur runs in constant time per pixel. The catch is that it is frozen: change one pixel and every entry below and to the right of it is wrong. A 2D Fenwick tree is the version for a grid that keeps changing, costing log w times log h per update and per rectangle query instead of a full rebuild.

Why it works this way

Why the array is 1-based

lowbit(0) is 0, so index 0 has no lowest set bit to walk by, and the two loops fail in opposite ways. The query loop is guarded by i > 0, so it never runs at all: it returns 0 and quietly reports an empty prefix. The update loop has no such guard, and i += lowbit(i) leaves i where it was, so it adds to tree[0] forever and hangs. That is why the tree array gets n + 1 slots with slot 0 left unused and your data position k stored at tree index k + 1. Forgetting that shift is the usual reason a Fenwick tree hangs on a write or silently drops the first value.

Why i and -i picks out the lowest set bit

In two's complement, -i is the bitwise inverse of i plus one. That carry runs through the trailing zeros and stops at the lowest set bit, so -i is i with every bit above the lowest set bit flipped and that bit and everything below it unchanged. ANDing the two therefore keeps only the positions where both hold a 1, and the lowest set bit is the only such position. Take 12 = 00001100 in eight bits: -12 is 11110100, and 00001100 and 11110100 gives 00000100, or 4.

Why the query walks down and the update walks up

Both loops come from the same fact read in opposite directions. A prefix has to be covered by disjoint cells: cell i handles its tail, and what remains is itself a prefix ending at i - lowbit(i), so subtracting enumerates that cover. An update instead has to repair every cell whose range contains position i, and those turn out to be i, then i + lowbit(i), and so on until you run past n. One walk lists the cells a prefix is built from, the other lists the cells one position belongs to.

Sums and xor work here, min and max do not

A range sum is prefix(r) minus prefix(l - 1), and that subtraction is what keeps the structure small: it needs an operation you can undo. Sum and xor can be undone, min and max cannot, because there is no way to pull one value back out of a stored minimum. A min-Fenwick is only correct while values never increase; once they can, you need a segment tree, which keeps each range outright and never has to cancel anything.

Read more

Next up