Sign in to watch this lesson
Algorithms - Trees and Range Queries · 4:59
Fenwick Tree
A Fenwick tree stores, at every index, the sum of a run of values as long as the index's lowest set bit, which i & -i extracts in one instruction. Queries strip bits off the index and updates add them, so both take O(log n) in about a dozen lines of code. We draw the staircase of bars, walk sum(13) and add(10), handle range updates with two trees, find where a running total first reaches a target with a single descent, and time it on a Mac against square-root blocks, a plain array and a naive range loop.
You will learn
- Explain what T[i] stores in a 1-based Fenwick tree (the sum of the lowbit(i) values ending at i) and compute lowbit with i & -i
- Implement sum(i) with i -= i & -i and add(i, d) with i += i & -i, both O(log n), and range sums as sum(r) - sum(l - 1)
- Support range add and range sum with two Fenwick trees over D[j] and j * D[j]: prefix(i) = (i + 1) S1(i) - S2(i)
- Find the first index whose prefix sum reaches x in O(log n) by descending through powers of two, and count inversions with a Fenwick tree