Segment Trees, Fenwick Trees & Sparse Tables
Answer range queries with updates in O(log n). Fenwick (BIT) for prefix sums and counting, segment trees for any associative operation with lazy propagation, and sparse tables for static min/max.
Which structure?
| Need | Structure | Build | Query | Update |
|---|---|---|---|---|
| range sum, no updates | prefix sums | O(n) | O(1) | ✗ |
| range min/max/gcd, no updates | sparse table | O(n log n) | O(1) | ✗ |
| prefix sums + point updates, counting | Fenwick tree (BIT) | O(n) | O(log n) | O(log n) |
| any associative op + point updates | segment tree | O(n) | O(log n) | O(log n) |
| range updates + range queries | segment tree + lazy propagation | O(n) | O(log n) | O(log n) |
Fenwick tree (Binary Indexed Tree)
Index i (1-based) stores the sum of a block of length i & −i ending at i. Prefix queries and point updates each touch O(log n) nodes.
class BIT:
def __init__(self, n):
self.n = n
self.t = [0] * (n + 1)
def add(self, i, delta): # a[i] += delta, i is 1-based
while i <= self.n:
self.t[i] += delta
i += i & -i
def prefix(self, i): # a[1] + ... + a[i]
s = 0
while i > 0:
s += self.t[i]
i -= i & -i
return s
def range_sum(self, l, r): # inclusive, 1-based
return self.prefix(r) - self.prefix(l - 1)
struct BIT {
int n; vector<long long> t;
BIT(int n) : n(n), t(n + 1, 0) {}
void add(int i, long long d) { for (; i <= n; i += i & -i) t[i] += d; }
long long prefix(int i) { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; }
long long range(int l, int r) { return prefix(r) - prefix(l - 1); }
};
Counting with a BIT + coordinate compression
Values can be huge or negative, but only their relative order matters. Map them to ranks 1..m, then use the BIT as a frequency table.
def count_smaller(nums):
ranks = {v: i + 1 for i, v in enumerate(sorted(set(nums)))}
bit = BIT(len(ranks))
res = []
for x in reversed(nums):
r = ranks[x]
res.append(bit.prefix(r - 1)) # how many smaller values are to the right
bit.add(r, 1)
return res[::-1]
vector<int> countSmaller(vector<int>& nums) {
vector<int> sorted_(nums);
sort(sorted_.begin(), sorted_.end());
sorted_.erase(unique(sorted_.begin(), sorted_.end()), sorted_.end());
BIT bit(sorted_.size());
vector<int> res(nums.size());
for (int i = nums.size() - 1; i >= 0; i--) {
int r = lower_bound(sorted_.begin(), sorted_.end(), nums[i]) - sorted_.begin() + 1;
res[i] = bit.prefix(r - 1);
bit.add(r, 1);
}
return res;
}
Inversion count, Reverse Pairs, Count of Range Sum and Create Sorted Array through Instructions are all this pattern.
Range update, point query
Store a difference array in the BIT: add(l, v); add(r + 1, −v); then prefix(i) is the value at i.
Segment tree
A binary tree over the array: each node stores the aggregate (sum, min, max, gcd…) of a segment. Works for any associative operation.
class SegTree:
"""Iterative (bottom-up) segment tree for an associative op."""
def __init__(self, data, op=max, identity=float("-inf")):
self.n = len(data)
self.op, self.id = op, identity
self.t = [identity] * (2 * self.n)
self.t[self.n:] = data
for i in range(self.n - 1, 0, -1):
self.t[i] = op(self.t[2 * i], self.t[2 * i + 1])
def update(self, i, value): # a[i] = value, 0-based
i += self.n
self.t[i] = value
while i > 1:
i //= 2
self.t[i] = self.op(self.t[2 * i], self.t[2 * i + 1])
def query(self, l, r): # op over a[l..r), 0-based half-open
res_l = res_r = self.id
l += self.n; r += self.n
while l < r:
if l & 1:
res_l = self.op(res_l, self.t[l]); l += 1
if r & 1:
r -= 1; res_r = self.op(self.t[r], res_r)
l //= 2; r //= 2
return self.op(res_l, res_r)
struct SegTree { // range max, point assign
int n; vector<long long> t;
SegTree(int n) : n(n), t(2 * n, LLONG_MIN) {}
void update(int i, long long v) {
for (t[i += n] = v; i > 1; i >>= 1) t[i >> 1] = max(t[i], t[i ^ 1]);
}
long long query(int l, int r) { // [l, r)
long long res = LLONG_MIN;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, t[l++]);
if (r & 1) res = max(res, t[--r]);
}
return res;
}
};
The iterative version is short and fast. The recursive version is easier to extend with lazy propagation.
Recursive segment tree with lazy propagation
Range add + range sum: a lazy tag on a node means "every element in my segment still needs +tag". Push tags down only when you visit children.
class LazySegTree:
def __init__(self, n):
self.n = n
self.sum = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def _apply(self, node, l, r, v):
self.sum[node] += v * (r - l + 1)
self.lazy[node] += v
def _push(self, node, l, r):
if self.lazy[node]:
m = (l + r) // 2
self._apply(2 * node, l, m, self.lazy[node])
self._apply(2 * node + 1, m + 1, r, self.lazy[node])
self.lazy[node] = 0
def add(self, ql, qr, v, node=1, l=0, r=None): # a[ql..qr] += v
if r is None: r = self.n - 1
if qr < l or r < ql:
return
if ql <= l and r <= qr:
self._apply(node, l, r, v)
return
self._push(node, l, r)
m = (l + r) // 2
self.add(ql, qr, v, 2 * node, l, m)
self.add(ql, qr, v, 2 * node + 1, m + 1, r)
self.sum[node] = self.sum[2 * node] + self.sum[2 * node + 1]
def query(self, ql, qr, node=1, l=0, r=None): # sum a[ql..qr]
if r is None: r = self.n - 1
if qr < l or r < ql:
return 0
if ql <= l and r <= qr:
return self.sum[node]
self._push(node, l, r)
m = (l + r) // 2
return self.query(ql, qr, 2 * node, l, m) + self.query(ql, qr, 2 * node + 1, m + 1, r)
struct LazySeg { // range add, range sum
int n; vector<long long> sum, lz;
LazySeg(int n) : n(n), sum(4 * n, 0), lz(4 * n, 0) {}
void apply(int x, int l, int r, long long v) { sum[x] += v * (r - l + 1); lz[x] += v; }
void push(int x, int l, int r) {
if (!lz[x]) return;
int m = (l + r) / 2;
apply(2 * x, l, m, lz[x]); apply(2 * x + 1, m + 1, r, lz[x]);
lz[x] = 0;
}
void add(int ql, int qr, long long v, int x, int l, int r) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) { apply(x, l, r, v); return; }
push(x, l, r);
int m = (l + r) / 2;
add(ql, qr, v, 2 * x, l, m); add(ql, qr, v, 2 * x + 1, m + 1, r);
sum[x] = sum[2 * x] + sum[2 * x + 1];
}
long long query(int ql, int qr, int x, int l, int r) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return sum[x];
push(x, l, r);
int m = (l + r) / 2;
return query(ql, qr, 2 * x, l, m) + query(ql, qr, 2 * x + 1, m + 1, r);
}
void add(int l, int r, long long v) { add(l, r, v, 1, 0, n - 1); }
long long query(int l, int r) { return query(l, r, 1, 0, n - 1); }
};
What can a node store?
Anything you can merge from two children:
- sum, min, max, gcd, xor, count of zeros
- (max subarray sum) with
(total, best prefix, best suffix, best)per node - sorted lists (merge sort tree) for "count ≤ x in range" in O(log² n)
Sparse table (static range min/max)
st[j][i] = min of a[i .. i + 2ʲ − 1]. Any range is covered by two overlapping power-of-two blocks, and min/max don't care about overlap → O(1) query.
class SparseTable:
def __init__(self, a):
n = len(a)
self.log = [0] * (n + 1)
for i in range(2, n + 1):
self.log[i] = self.log[i // 2] + 1
self.st = [a[:]]
j = 1
while (1 << j) <= n:
prev = self.st[-1]
self.st.append([min(prev[i], prev[i + (1 << (j - 1))]) for i in range(n - (1 << j) + 1)])
j += 1
def query(self, l, r): # min of a[l..r] inclusive
j = self.log[r - l + 1]
return min(self.st[j][l], self.st[j][r - (1 << j) + 1])
Works for any idempotent operation (min, max, gcd, and, or) — not sum.
Square-root decomposition (bonus)
Split the array into blocks of size √n, keep an aggregate per block. Updates O(1) or O(√n), queries O(√n). Easy to write and flexible when a segment tree's merge is awkward (and the basis of Mo's algorithm for offline queries).
Common mistakes
- Mixing 0-based and 1-based indices in a BIT (index 0 loops forever in
add). - Forgetting coordinate compression when values are up to 10⁹.
- Too-small segment tree arrays (use 4n for recursive).
- Forgetting to push lazy tags before recursing into children.
- Using a sparse table for sums (overlap double-counts).
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.