Range-query data structures · HTML
Support add(i,delta) and prefix(r)=aggregate(a[0:r]); derive a range by canceling two prefixes.
Recognition signals
- Point updates and range queries interleave online
- Queries reduce to prefixes
- The aggregate has an inverse
- Compressed coordinates support rank frequencies
- A smaller constant than a segment tree is desirable
False friends
| Signal | Why it is different |
|---|
| Complex range assignment | A basic Fenwick tree is unnatural here; consider a lazy segment tree. |
| Non-invertible dynamic aggregate | Dynamic range minimum cannot be canceled from two prefixes; use a segment tree. |
Core invariant
In 1-based indexing, tree[i] stores the aggregate on (i-lowbit(i),i]; a query chain partitions a prefix into disjoint blocks.
State, transition, and processing order
| Item | Definition |
|---|
| State | An n+1 tree array; the public API is 0-based and shifts indices on entry. |
| Transition | add climbs with i+=lowbit(i); prefix collects blocks while i-=lowbit(i). |
| Frontier / order | An update moves toward larger ancestor blocks; a query repeatedly clears its lowest set bit to reach zero. |
Python skeleton
class Fenwick:
def __init__(self, n):
self.n = n
self.t = [0] * (n + 1)
def add(self, index, delta):
i = index + 1
while i <= self.n:
self.t[i] += delta
i += i & -i
def prefix(self, right):
total, i = 0, right
while i:
total += self.t[i]
i -= i & -i
return total
def range_sum(self, left, right):
return self.prefix(right) - self.prefix(left)
Correctness sketch
- lowbit uniquely determines every stored block.
- The add chain reaches exactly the blocks containing the changed position.
- The prefix descent covers the requested prefix with disjoint blocks.
- Canceling two prefixes leaves exactly [left,right).
Complexity
| Time | Space | Parameters |
|---|
| O(log n) per update, prefix, or range sum | O(n) | n array positions; repeated-add construction costs O(n log n) |
Edge cases
- Use an exclusive right boundary
- An empty interval returns zero
- Internal indices must be 1-based
- Assignment must become a delta
- Equal compressed values share one rank
Error patterns
| Pattern | Why it fails / fix |
|---|
| Updating internal index zero | lowbit(0)=0 causes an infinite loop. |
| Endpoint drift | Fix prefix(r) as [0,r) everywhere. |
| Treating set as add | Assigning x requires delta=x-old. |
Selection and exclusion rules
- Point add plus prefix or range sum: Fenwick.
- Complex aggregates or range updates: segment tree.
- Fully static data: prefix sums or a sparse table.
- For rank counts, compress coordinates and choose strict versus non-strict prefixes explicitly.
Original micro-example
| Part | Detail |
|---|
| Result | The new range sum is 8. |
| Scenario | For [2,0,3,1], add 4 at index 1 and query [1,4). |
| Walkthrough | add changes every block containing the second item; prefix(4)-prefix(1)=10-2. |
Recall prompts
My notes