Fenwick tree (binary indexed tree)

53 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Six numbers: 1, 3, 5, 7, 9, 11. You need the sum of the first k of them, for various k, while the numbers keep changing. The sum of the first 5 is 1 + 3 + 5 + 7 + 9 = 25. With a table of running totals (1, 4, 9, 16, 25, 36) that is one lookup, but adding 2 to the fourth number forces you to rewrite the last three totals, and with a million numbers that is a million rewrites. Adding up from scratch each time is a million steps per question instead. We want both the question and the change to cost a few steps.

Build the structure, one piece at a time

Piece one: number the positions from 1, not 0, and write each position in binary. The lowest set bit of a position, written lowbit(i), is the value of its rightmost 1: lowbit(6) = 2 because 6 is 110, lowbit(4) = 4 because 4 is 100, lowbit(5) = 1.

Piece two: a second array, tree, where slot i stores the sum of a block ending at i whose length is lowbit(i). So slot 1 covers position 1 alone, slot 2 covers positions 1 to 2, slot 3 covers position 3 alone, slot 4 covers 1 to 4, slot 5 covers 5 alone, slot 6 covers 5 to 6:

Piece three: a prefix sum by walking down. To sum positions 1 to 5, start at i = 5, take tree[5] = 9, then remove the lowest bit: 5 − 1 = 4. Take tree[4] = 16, remove the lowest bit: 4 − 4 = 0, stop. Total 25, from two slots. The blocks visited, 5..5 and 1..4, tile the range 1..5 exactly.

Piece four: a change by walking up. Add 2 to position 4. Every slot whose block contains position 4 must grow by 2. Start at i = 4, add 2 so tree[4] = 18, then add the lowest bit: 4 + 4 = 8, which is past the end, stop. Had the array been longer, slot 8 (covering 1..8) would be next.

Why it is correct

The invariant is that tree[i] equals the sum of positions i − lowbit(i) + 1 through i. The downward walk from i takes the block ending at i, then jumps to i − lowbit(i), which is exactly the position just before that block, and takes the block ending there, and so on until 0. The blocks are adjacent and end at position i, so together they cover 1..i once each.

The upward walk must visit every slot whose block contains position p. A slot j > p contains p exactly when j − lowbit(j) < p, and the next such slot after p itself is p + lowbit(p): adding the lowest set bit clears it and carries, producing the smallest larger number whose block reaches back past p. Repeating the step visits all of them and nothing else.

Why it is fast

Each downward step removes one set bit from i, and i has at most log₂ n + 1 bits, so a prefix sum reads at most that many slots. Each upward step moves the lowest set bit at least one place to the left, so an update also takes at most log₂ n + 1 steps:

query and update ≤ ⌊log₂ n⌋ + 1 slot visits

For a million positions that is 21 steps for either operation, against a million for one of them in the by-hand approaches. The memory is one extra array of n numbers, and the code is two loops of three lines each. A segment tree does the same job with more memory and more code; the Fenwick tree is the compact choice when only prefix sums and point updates are needed. A range sum from l to r is prefix(r) − prefix(l − 1).

How to recognise it in an interview

Cues: "count how many earlier elements are smaller", "prefix sum with updates", "number of inversions", or any scan where you must ask how many already-seen values fall below a threshold. Say: "I will scan once and keep a Fenwick tree over values, so each count and each insert is O(log n)".

Count of Smaller Numbers After Self scans from the right: for each number, query the prefix sum of values below it, then add 1 at its value. Reverse Pairs scans the same way asking how many seen values exceed 2 × the current one. Range Sum Query Mutable is the plain point-update, range-sum use.

02The idea in one line

Prefix sums in O(log n) by walking the lowest set bit up and down.

Reach for it when: Count of smaller numbers after self, reverse pairs, create sorted array, range sum mutable.

Cost: O(log n) per op.

03The walk-through, step by step

The video works one example: Fenwick prefix sum on [1,3,5,7,9,11]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Each tree slot sums a block whose length is its lowest set bit
2. tree[1] = sum of array[0..0] = 1 (lowbit 1)
3. tree[2] = sum of array[0..1] = 4 (lowbit 2)
4. tree[3] = sum of array[2..2] = 5 (lowbit 1)
5. tree[4] = sum of array[0..3] = 16 (lowbit 4)
6. tree[5] = sum of array[4..4] = 9 (lowbit 1)
7. tree[6] = sum of array[4..5] = 20 (lowbit 2)
8. prefix(5): start at i = 5, walk down by clearing the lowest bit
9. add tree[5] = 9 → sum 9; i = 5 − 1 = 4
10. add tree[4] = 16 → sum 25; i = 4 − 4 = 0
11. prefix(5) = 25 from only 2 slots
12. update array[3] += 2: climb i = 4, then i += lowbit(i)
13. tree[4] += 2 → 18; next i = 4 + 4 = 8
14. Both walks touch one slot per bit: O(log n) query and update

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Advanced Structures: Segment tree (range query + point update), Ordered set / sorted container, Bucketing by value range, Matrix exponentiation for recurrences, Meet in the middle.