Skip to content
Tutorials Center
My learning

Topics

Lesson 115 of 225 ยท Tries and Range Queries

Fenwick Tree (Binary Indexed Tree)

Learn the Fenwick tree (binary indexed tree) in Python: lowbit, update and prefix query in O(log n), range sums, counting inversions and a 2D version.

You have met two answers to "sum of a range". Prefix sums answer in O(1) but break when values change. A segment tree handles changes in O(log n) but takes a page of code. The Fenwick tree, also called the binary indexed tree (BIT), gives you the same O(log n) updates and prefix queries in about ten lines, using a single flat array and a clever bit trick.

It is the favorite tool of competitive programmers for counting problems: how many numbers so far are smaller than x? How many inversions are in this array? In exchange for its brevity, a Fenwick tree is less flexible than a segment tree: it naturally handles operations that can be undone (like addition), mostly for prefix queries.

The key trick: lowbit

The lowbit of a positive integer is its lowest set bit, computed as i & -i:

TEXT
 i  binary   -i (two's complement)   i & -i
 6   0110         ...1010             0010 = 2
 8   1000         ...1000             1000 = 8
 7   0111         ...1001             0001 = 1
12   1100         ...0100             0100 = 4

A Fenwick tree uses 1-based indexes (index 0 would make i & -i equal 0 and loop forever). Cell tree[i] stores the sum of the lowbit(i) elements that end at i:

TEXT
tree[i] = a[i - lowbit(i) + 1] + ... + a[i]

i:        1    2     3    4       5    6     7    8
lowbit:   1    2     1    4       1    2     1    8
covers:  [1]  [1,2]  [3] [1..4]  [5]  [5,6]  [7] [1..8]

As a picture, each cell "owns" a stretch of the array:

TEXT
a:      1     2     3     4     5     6     7     8
        |     |     |     |     |     |     |     |
tree1 โ”€โ”€โ”˜     |     |     |     |     |     |     |
tree2 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜     |     |     |     |     |     |      (covers 1-2)
tree3 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜     |     |     |     |     |
tree4 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜     |     |     |     |      (covers 1-4)
tree5 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜     |     |     |
tree6 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜     |     |      (covers 5-6)
tree7 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜     |
tree8 โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”˜      (covers 1-8)

Query: prefix sum

To get prefix(i) = a[1] + ... + a[i], add tree[i], then strip the lowest set bit (i -= i & -i) and repeat until i is 0. Each step jumps to the next block that ends right before the current one starts.

TEXT
prefix(7):  i = 7 (111)  add tree[7] = a7
            i = 6 (110)  add tree[6] = a5 + a6
            i = 4 (100)  add tree[4] = a1..a4
            i = 0        stop

The number of steps is the number of 1-bits in i, at most log2(n) + 1.

Update: add to a position

To add delta to a[i], we must fix every cell that covers position i: add delta to tree[i], then move to the next such cell with i += i & -i, until we pass n.

TEXT
update(5): i = 5 (101)  tree[5] += delta
           i = 6 (110)  tree[6] += delta
           i = 8 (1000) tree[8] += delta
           i = 16       beyond n = 8, stop

Again at most about log2(n) steps. Both loops walk bit patterns: query removes low bits, update adds them.

Implementation

Python A Fenwick tree with update and range sum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the first printed line against the table: tree[1] = 5, tree[2] = 5 + 8 = 13, tree[3] = 6, tree[4] = 5 + 8 + 6 + 3 = 22, and so on.

Notice range_sum(left, right) is the difference of two prefixes, which works because addition can be undone by subtraction. That is why Fenwick trees fit sums and counts naturally, but not min or max (you cannot "subtract" a minimum).

Setting a value, and counting the steps

The tree handles additions. To set position i to a new value, add new - old, so keep the plain array too. The next demo also counts loop steps to show how few there are.

Python Set a value and count the steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The number of query steps equals the count of 1-bits in the index: 1000 is 1111101000 (6 ones) and 999 is 1111100111 (8 ones). An update from position 1 climbs by powers of two, so it takes about log2(n) steps.

Brute force vs Fenwick

If you update and query repeatedly:

Method Update Prefix/range query Many mixed operations
Plain array O(1) O(n) slow queries
Prefix-sum array O(n) O(1) slow updates
Fenwick tree O(log n) O(log n) balanced

For q operations on n items, the first two cost O(q ร— n) in the worst case; the Fenwick tree costs O(q log n).

Counting inversions

An inversion in a list is a pair of positions i < j with a[i] > a[j]. It measures how unsorted a list is: a sorted list has 0, a reversed list of n items has n(n-1)/2.

Brute force: compare every pair, O(nยฒ).

With a Fenwick tree: scan left to right. When you reach value x, the number of earlier values greater than x is the number of earlier elements minus those that are โ‰ค x. The Fenwick tree holds a count per value ("how many times has this value appeared so far"), so prefix(x) tells you how many earlier elements are โ‰ค x. Total O(n log n). First, map the values to ranks 1..m so the tree stays small (this is called coordinate compression).

Python Counting inversions with a Fenwick tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trace for [3, 1, 2, 5, 4] (ranks equal the values here):

TEXT
value 3: earlier = 0, count of earlier <= 3 is 0 -> adds 0. tree holds {3}
value 1: earlier = 1, count <= 1 is 0 -> adds 1  (3 > 1)
value 2: earlier = 2, count <= 2 is 1 -> adds 1  (3 > 2)
value 5: earlier = 3, count <= 5 is 3 -> adds 0
value 4: earlier = 4, count <= 4 is 3 -> adds 1  (5 > 4)
total = 3

Range update, point query

Turn the tree around by storing differences: let d[i] = a[i] - a[i-1]. Then a[i] is the prefix sum of d. Adding v to every element in [l, r] becomes two point updates: d[l] += v and d[r+1] -= v. A point query is prefix(i).

Python Range add, point query

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

(Supporting both range update and range sum needs two Fenwick trees; a lazy segment tree is usually simpler.)

Finding the k-th element

If the tree stores counts, you can find the smallest index whose prefix count is at least k with a binary descent: try to jump by the highest power of two first.

Python k-th smallest with binary descent

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A 2D Fenwick tree

The same trick works in two dimensions: nest the loops. tree[i][j] covers a rectangle ending at (i, j); update and query each take O(log R ร— log C). Rectangle sums use inclusion-exclusion with four prefix queries.

Python 2D Fenwick tree for rectangle sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Persistent segment tree: querying the past

A Fenwick tree or an ordinary segment tree is ephemeral: an update overwrites the old data, so you can only ask about the present. A persistent structure keeps every earlier version alive and queryable. The trick is path copying. An update changes only the nodes on one root-to-leaf path, which is O(log n) nodes. So you copy just those nodes, point them at the unchanged children of the old version, and get a new root. Old roots still describe the old data, and the two versions share almost all of their memory.

TEXT
version 1:           version 2 (after one update):
    R1                    R2          <- only the path R2, B2, D2 is new
   /  \                  /  \
  A    B                A    B2       <- A is shared with version 1
 / \  / \                   /  \
.  . C  D                  C    D2    <- C is shared too

A famous use is the k-th smallest number in a range a[l..r], answered online. Compress the values to ranks 0..m-1. Build the versions one element at a time: version i is a segment tree over value ranks whose leaves count how many of the first i elements have that rank, so version i is version i - 1 plus one increment. The counts of elements in positions l..r are then version[r] - version[l - 1] node by node, and finding the k-th smallest is a descent: go left if the left count difference is at least k, otherwise subtract it from k and go right. Memory is O(n log n) nodes in total, and each query is O(log n) with no rebuilding.

Python Persistent segment tree: k-th smallest in a range

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each of the 8 versions added only the 3 or 4 nodes on one root-to-leaf path (31 nodes in total), instead of eight separate trees of 13 nodes each (104). Persistence is also how functional languages implement immutable maps, and how some databases offer "time travel" reads.

2D Fenwick trees

The two-dimensional Fenwick tree for rectangle sums is covered above in "A 2D Fenwick tree": it applies the same lowbit loop in both coordinates, so each update and query costs O(log n * log m). If you also need range updates with range queries in 2D, the standard route is to keep four Fenwick tables, in the same spirit as the two-table trick in one dimension.

Complexity

Operation Time Space
Build (naive: n updates) O(n log n) O(n)
Build (parent propagation) O(n) O(n)
Point update O(log n)
Prefix query O(log n)
Range sum O(log n) (two prefixes)
2D update/query O(log R ร— log C) O(R ร— C)

Fenwick tree or segment tree?

Pick a Fenwick tree for sums, counts and anything with an inverse operation: it is smaller, faster in practice and easy to write. Pick a segment tree when you need min/max/gcd, arbitrary combine functions, or general range updates with lazy propagation. If the data never changes, prefix sums or a sparse table are simpler still.

Common mistakes

  • Using index 0. Fenwick trees are 1-based; 0 & -0 is 0, so a loop starting at 0 never advances.
  • Forgetting that add adds, it does not set. To set, add the difference from the old value.
  • Wrong boundary for range sums: it is prefix(right) - prefix(left - 1), not prefix(left).
  • Not compressing coordinates when values are huge (like 10^9) or negative, which makes the tree too big or indexes invalid.
  • Using it for min/max with an in-place update. A plain Fenwick tree cannot "subtract" a minimum.
  • Allocating size instead of size + 1 cells.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does i & -i compute for a positive integer i?

    In two's complement, -i flips all bits above the lowest set bit, so i & -i keeps only that lowest set bit.
  2. 2. In a Fenwick tree with n = 8, which positions does tree[6] cover?

    6 is 110 in binary, its lowbit is 2, so tree[6] covers the 2 elements ending at position 6: positions 5 and 6.
  3. 3. How is the sum of positions 3 to 7 computed?

    The sum of a range is the prefix up to its end minus the prefix just before its start.
  4. 4. How many steps does prefix(i) take?

    Each step removes the lowest set bit of i, so the loop ends after as many steps as i has 1-bits.
  5. 5. Why is a Fenwick tree a good fit for counting inversions?

    With a counter per value, a prefix query gives the number of earlier elements not greater than x; the rest are the inversions ending at the current element.

Summary

  • A Fenwick tree (binary indexed tree) stores partial sums in a flat 1-based array: tree[i] covers the lowbit(i) elements ending at i.
  • prefix(i) strips low bits (i -= i & -i), add(i, delta) adds them (i += i & -i); both take O(log n).
  • Range sum is prefix(r) - prefix(l - 1); it needs an operation with an inverse, so it suits sums and counts, not min or max.
  • Build in O(n) by pushing each cell's value to its parent.
  • Applications: counting inversions with coordinate compression, range add with point query via differences, k-th element by binary descent, and 2D rectangle sums.
  • Use a segment tree for general combine functions and lazy range updates.

Next: Sparse Tables and RMQ