When to Use Range Query Data Structures
Range query problems appear frequently in senior engineering interviews and competitive programming: “find the sum of elements from index L to R,” “find the minimum in a range after multiple updates,” “count inversions in an array.” A naive approach (recompute from scratch on each query) is O(N) per query — too slow when you have many queries. Segment trees and Fenwick trees answer range queries in O(log N) with O(log N) updates.
Fenwick Tree (Binary Indexed Tree)
A Fenwick tree (BIT) is the simpler of the two structures. It supports two operations on a prefix sum array: point update (add a value to index i) and prefix query (sum of elements from index 1 to i). Range sum [L, R] = prefix(R) – prefix(L-1). The key insight: each index i in the BIT stores the sum of a specific range of elements, determined by the lowest set bit of i. The update and query both traverse O(log N) nodes.
class FenwickTree:
def __init__(self, n: int):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i: int, delta: int) -> None:
# Add delta to index i (1-indexed)
while i int:
# Sum from 1 to i (1-indexed)
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i) # move to parent
return s
def range_query(self, l: int, r: int) -> int:
return self.query(r) - self.query(l - 1)
# Build from array in O(N log N):
def build(arr):
n = len(arr)
bit = FenwickTree(n)
for i, v in enumerate(arr, 1):
bit.update(i, v)
return bit
# LeetCode 307: Range Sum Query - Mutable
# bit.update(i+1, new_val - old_val) for point update
# bit.range_query(l+1, r+1) for range sum
Time: O(N log N) build, O(log N) update and query. Space: O(N). Limitation: only supports operations that have inverses (sum, XOR) — not min/max (no inverse).
Segment Tree
A segment tree is a binary tree where each node stores an aggregate (sum, min, max, gcd) for a range of the array. The root covers [0, N-1]; each internal node covers the union of its children’s ranges. Leaves are individual elements. Building takes O(N); each query and update takes O(log N).
class SegmentTree:
def __init__(self, nums: list[int]):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 0, 0, self.n - 1)
def _build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2*node+1, start, mid)
self._build(nums, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def update(self, node, start, end, idx, val):
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if idx int:
if r < start or end < l:
return 0 # neutral element for sum
if l <= start and end <= r:
return self.tree[node] # fully covered
mid = (start + end) // 2
left = self.query(2*node+1, start, mid, l, r)
right = self.query(2*node+2, mid+1, end, l, r)
return left + right
# Usage:
st = SegmentTree([1, 3, 5, 7, 9])
st.query(0, 0, 4, 1, 3) # sum of indices 1..3 = 15
st.update(0, 0, 4, 1, 10) # set index 1 to 10
Lazy Propagation: Range Updates in O(log N)
Without lazy propagation, updating a range [L, R] requires O(N) point updates. Lazy propagation defers updates: mark a node as “pending update” (lazy tag) and only propagate the tag when you need to access the node’s children. This achieves O(log N) range updates.
# Range add + range sum with lazy propagation
class LazySegTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n)
self.lazy = [0] * (4 * n) # pending add values
def _push_down(self, node, start, end):
if self.lazy[node] != 0:
mid = (start + end) // 2
left, right = 2*node+1, 2*node+2
# Apply lazy to children
self.tree[left] += self.lazy[node] * (mid - start + 1)
self.tree[right] += self.lazy[node] * (end - mid)
self.lazy[left] += self.lazy[node]
self.lazy[right] += self.lazy[node]
self.lazy[node] = 0
def range_update(self, node, start, end, l, r, val):
if r < start or end < l:
return
if l <= start and end <= r:
self.tree[node] += val * (end - start + 1)
self.lazy[node] += val
return
self._push_down(node, start, end)
mid = (start + end) // 2
self.range_update(2*node+1, start, mid, l, r, val)
self.range_update(2*node+2, mid+1, end, l, r, val)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def range_query(self, node, start, end, l, r):
if r < start or end < l:
return 0
if l <= start and end <= r:
return self.tree[node]
self._push_down(node, start, end)
mid = (start + end) // 2
return (self.range_query(2*node+1, start, mid, l, r) +
self.range_query(2*node+2, mid+1, end, l, r))
Range Minimum Query (RMQ)
Segment tree for range minimum: change the merge operation from + to min(), and the neutral element from 0 to float(‘inf’). Updates and queries work identically. Common problem: LeetCode 2407 (Longest Increasing Subsequence II) can be solved with a segment tree querying the maximum dp value over a range of previous values.
Counting Inversions with BIT
Count inversions (pairs i arr[j]) using a BIT. Process elements left to right. For each element x: query BIT for count of elements already inserted that are greater than x = (elements inserted so far) – BIT.query(x). Then update BIT at position x. Total time: O(N log N) after coordinate compression if values are large.
def count_inversions(arr):
from sortedcontainers import SortedList
# Coordinate compress
sorted_vals = sorted(set(arr))
rank = {v: i+1 for i, v in enumerate(sorted_vals)}
bit = FenwickTree(len(sorted_vals))
inversions = 0
for i, x in enumerate(arr):
r = rank[x]
# elements already seen with rank > r
inversions += i - bit.query(r)
bit.update(r, 1)
return inversions
When to Use Which
| Use case | Best structure |
|---|---|
| Point update + prefix sum | Fenwick tree (simpler, faster constant) |
| Range update + range query (sum) | Lazy segment tree |
| Range min/max query | Segment tree (BIT cannot do min/max) |
| Counting inversions | Fenwick tree + coordinate compression |
| 2D range sum | 2D Fenwick tree |
Key Problems to Practice
- LeetCode 307: Range Sum Query — Mutable (BIT)
- LeetCode 315: Count of Smaller Numbers After Self (BIT + coordinate compression)
- LeetCode 327: Count of Range Sum (merge sort or BIT)
- LeetCode 2158: Amount of New Area Painted Each Day (lazy segment tree)
- LeetCode 699: Falling Squares (segment tree range max)