Fenwick tree

The idea

A Fenwick tree, also called a binary indexed tree, solves the same problem as a segment tree for sums: change single items and ask for range sums, both in O(log n). It is shorter to write and uses an array of just n + 1 numbers.

Each cell tree[i] (counting from 1) stores the sum of a block of items that ends at item i. The block's length is the lowest set bit of i in binary, written i & -i. For example tree[6] covers 2 items (6 is 110), tree[8] covers 8 items (8 is 1000), and tree[7] covers 1 item.

To get the sum of the first i items, add tree[i], then jump to the item just before that block (i -= i & -i), and repeat. To add to an item, update every block that contains it by jumping the other way (i += i & -i). Both walks take about log n jumps.

An everyday example

From the slow way to fenwick tree

1. The problem is the same as for a segment tree: change single items and ask for range sums, many times, mixed together. A prefix-sum array answers in one step but needs up to n steps per change. A segment tree does both in O(log n), but it needs 4n slots and a few recursive methods. Can a plain array of n numbers do the same job?
2. Look at how a prefix is made of blocks. Any whole number is a sum of powers of two: 7 = 4 + 2 + 1. So the first 7 items split into a block of 4 (items 1 to 4), a block of 2 (items 5 to 6), and a block of 1 (item 7). If each of those block sums were stored, a prefix sum would be just 3 additions, one per 1 bit in the binary form of 7.
3. Which block should position i store? Let tree[i] hold the block that ends at item i and is as long as the lowest set bit of i, written i & -i. Every position stores exactly one block, so the array has n + 1 cells, and the blocks a prefix needs are found by taking tree[i] and then jumping to i - (i & -i), which drops the lowest 1 bit.
4. When one item changes, only the blocks that contain it need fixing. Starting at its position and jumping i += i & -i visits exactly those blocks, each longer than the last, so there are at most about log₂ n of them. One array, two short loops, and the lowest-set-bit trick: that is a Fenwick tree.

How it works

1. Create tree with n + 1 zeros. Index 0 is unused, because the jumps rely on 1-based positions.
2. add(index, delta): start at i = index + 1 and add delta to tree[i].
3. Move to the next block that also contains this item: i += i & -i. Stop when i passes the end.
4. prefixSum(index): start at i = index + 1 with total = 0. Add tree[i].
5. Move to the block just before: i -= i & -i. Stop when i reaches 0, and return total.
6. rangeSum(left, right) is prefixSum(right) minus prefixSum(left - 1).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

The code

Point at a note to light up the lines it explains.

How fast it is

Each jump changes the lowest set bit of i, so a walk has at most about log₂ n jumps. The tree is one array of n + 1 numbers.

• Best caseO(1)

  prefixSum(0) reads only tree[1], then i becomes 0. An add to a position whose next jump is past the end also takes one step.

• Average caseO(log n)

  A prefixSum takes one step per 1 bit in index + 1, about half of the log₂ n bits for a random index.

• Worst caseO(log n)

  Positions with many 1 bits for prefixSum, such as 511 (111111111), and add at position 1, which climbs 1, 2, 4, 8, and so on. For 1,000 items, a prefix sum takes at most 9 jumps and an add at most 10.

Common mistakes

• Using 0-based positions inside the loops. 0 & -0 is 0, so i never moves and the loop runs forever. Shift to 1-based with index + 1.
• Setting a value with add(index, value) instead of add(index, value - current). A Fenwick tree adds changes; keep the current values in a separate array if you need to set.
• Using it for min or max with updates that can make values bigger and smaller. Sums can be undone by subtracting, but a minimum can't; use a segment tree there.
• Forgetting the left > 0 check, which calls prefixSum(-1).

When to use it

Look for these clues in a problem:

• You need prefix sums or range sums while single items keep changing.
• You need to count, for each item, how many earlier items are smaller (inversions, ranks), often after compressing values to small indexes.
• You need to add to a range and read single items (store differences in the tree).
• Memory or code size matters, and the operation is a sum (or anything you can undo, like XOR).

Check yourself

Answer each one in your head first, then open it.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Go further

You don't need these to start practicing. Open one when you want more.

Related algorithms

• Segment treeA tree over an array where each node stores the sum (or min, or max) of a range, so range questions and single-item updates both take O(log n).
• Prefix sumsStore running totals once, so the sum of any range of an array takes one subtraction.
• Difference arrayApply many "add this amount to a range" updates in constant time each, then rebuild the final values in one pass.
• Coordinate compressionReplace big or spread-out values with their rank among the distinct values, so they can be used as small array indexes.
• Bitwise operatorsRead, set, clear, and flip single bits of a number with &, |, ^, ~, and shifts, keeping in mind that JavaScript does this on 32-bit integers.