Overview
Prefix sums answer range-sum queries instantly — until a single element changes and the whole prefix array must be rebuilt. Range-query trees fix this by storing partial aggregates over blocks of the array so that both a point update and a range query touch only O(log n) blocks.
A Fenwick tree (binary indexed tree) is a remarkably short structure for prefix sums with updates, built entirely on the lowest-set-bit trick. A segment tree is more general: each node stores an aggregate (sum, min, max, gcd) for a segment, and with lazy propagation it also supports updating whole ranges at once. These appear in harder interview rounds and constantly in competitive programming.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Fenwick: update / prefix query | O(log n) |
| Segment tree: build | O(n) |
| Segment tree: update / query | O(log n) |
| Range update with lazy propagation | O(log n) |
Patterns to recognise
Point update, range query
Use it for: Range sum query – mutable.
Fenwick tree for sums; segment tree for min/max.
Counting with a BIT
Use it for: Count of smaller numbers after self, reverse pairs, inversions.
Compress values, scan the array, query how many earlier values fall in a range, then add the current one.
Range update
Use it for: Booking counts, falling squares.
Segment tree with lazy tags, or a Fenwick tree over a difference array.
Code template
class Fenwick:
def __init__(self, n):
self.tree = [0] * (n + 1)
def add(self, i, delta): # a[i] += delta, 0-indexed
i += 1
while i < len(self.tree):
self.tree[i] += delta
i += i & -i
def prefix(self, i): # sum of a[0:i]
total = 0
while i > 0:
total += self.tree[i]
i -= i & -i
return total
def range_sum(self, left, right): # sum of a[left..right]
return self.prefix(right + 1) - self.prefix(left)
struct Fenwick {
vector<long long> tree;
explicit Fenwick(int n) : tree(n + 1, 0) {}
void add(int i, long long delta) { // a[i] += delta, 0-indexed
for (++i; i < (int)tree.size(); i += i & -i) tree[i] += delta;
}
long long prefix(int i) const { // sum of a[0, i)
long long total = 0;
for (; i > 0; i -= i & -i) total += tree[i];
return total;
}
long long rangeSum(int left, int right) const { // sum of a[left..right]
return prefix(right + 1) - prefix(left);
}
};
Common mistakes
- Fenwick trees are 1-indexed internally; mixing conventions causes infinite loops at index 0.
- Segment-tree arrays need about 4n slots when built recursively.
- For an update that sets a value (rather than adds), add the difference from the old value.
Quick check
Three questions on Range Queries. Get all three right to earn +15 XP.
-
A segment tree answers a range query and applies a point update in:
Both touch only O(log n) nodes on the way down the tree.
-
When is a plain prefix-sum array a better choice than a segment tree?
Static data gives O(1) queries with far less code.
-
In a Fenwick tree, what does i & (-i) give you?
Adding or subtracting that value moves between the nodes responsible for index i.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Range Sum Query – MutableLeetCode Medium +40
- Corporate Flight BookingsLeetCode Medium +40
- Count of Smaller Numbers After SelfLeetCode Hard +70
- Reverse PairsLeetCode Hard +70
- Count of Range SumLeetCode Hard +70
- My Calendar IIILeetCode Hard +70
- Falling SquaresLeetCode Hard +70
Stuck on Range Queries?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor