DSA Notes

Range Queries

Fenwick Tree

Prefix sums that can be updated, in a dozen lines.

The idea

A Fenwick tree (binary indexed tree) stores partial sums so that both “add v at position i” and “sum of the first i elements” take O(log n).

Cell i covers the last i & −i elements ending at i, where i & −i is the lowest set bit of i. A prefix sum hops downwards with i −= i & −i; an update hops upwards with i += i & −i.

It is shorter and faster than a segment tree when sums are all you need. A typical use is counting inversions: scan the array, and for each element ask how many earlier elements are larger.

Sample problem

315. Count of Smaller Numbers After Self ↗ Hard

For each element of an array, count how many elements to its right are smaller than it.

nums = [5,2,6,1]
output = [2,1,1,0]

Why the solution works

Comparing every pair is O(n²). Scan from right to left instead, so that when an element is reached, everything to its right has already been seen.

Keep a count of the values seen so far, indexed by value. “How many seen values are smaller than x” is then a prefix sum of those counts, and seeing a new value is a point update: exactly the two operations a Fenwick tree does in O(log n).

Values can be huge or negative, so they are first replaced by their rank among the distinct values. i & −i isolates the lowest set bit of i: sum strips it to walk down, add adds it to walk up.

Complexity: O(n log n) time, O(n) memory.

Watch out

  • Positions start at 1. With index 0, i += i & -i never moves.
  • When values are large, compress them to 1..n first.
  • Range sums come from two prefix sums, which only works for operations that can be undone, such as addition.
Watch it run

Try your own input

Practise on LeetCode