Range query problems appear frequently in competitive programming and technical interviews. Knowing which data structure to reach for – and why – separates candidates who brute-force O(n) queries from those who solve problems in O(1) or O(log n). This guide covers every major range query pattern with working Python code.
Prefix Sum Array
The prefix sum array is the foundation of all range query work. Build it once in O(n), then answer any range sum query in O(1).
1D Prefix Sum
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, left, right):
# inclusive [left, right], 0-indexed
return prefix[right + 1] - prefix[left]
nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = build_prefix(nums)
print(range_sum(prefix, 1, 4)) # sum of indices 1..4 = 1+4+1+5 = 11
The key formula: sum(l, r) = prefix[r+1] - prefix[l]. Using a 1-indexed prefix array with a leading zero avoids off-by-one errors.
2D Prefix Sum
For matrix range sums, extend the idea to two dimensions. Build takes O(m*n), queries answer in O(1).
def build_2d_prefix(matrix):
m, n = len(matrix), len(matrix[0])
prefix = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
prefix[i][j] = (matrix[i-1][j-1]
+ prefix[i-1][j]
+ prefix[i][j-1]
- prefix[i-1][j-1])
return prefix
def query_2d(prefix, r1, c1, r2, c2):
# all inclusive, 0-indexed input
return (prefix[r2+1][c2+1]
- prefix[r1][c2+1]
- prefix[r2+1][c1]
+ prefix[r1][c1])
Inclusion-exclusion gives the formula: add the full rectangle, subtract the two overlapping strips, add back the doubly-subtracted corner.
Use when: data is static (immutable), you need sum queries only, and you want the simplest possible solution.
Difference Array
When you need to perform many range updates on an array and only read values at the end, the difference array is O(1) per update versus O(n) for naive.
def range_update(diff, left, right, val):
diff[left] += val
if right + 1 < len(diff):
diff[right + 1] -= val
def reconstruct(diff):
result = []
running = 0
for d in diff:
running += d
result.append(running)
return result
n = 6
diff = [0] * (n + 1)
range_update(diff, 1, 3, 5) # add 5 to indices 1..3
range_update(diff, 2, 5, -2) # subtract 2 from indices 2..5
print(reconstruct(diff)[:n]) # [0, 5, 3, 3, -2, -2]
Use when: you have many offline range increment/decrement operations and only need the final state. Classic problem: “apply N flight bookings and report seat counts.”
Sparse Table
The sparse table answers range minimum (or maximum) queries in O(1) after O(n log n) preprocessing. It works only on immutable data and only for idempotent operations (min, max, GCD – but not sum).
import math
def build_sparse_table(arr):
n = len(arr)
k = int(math.log2(n)) + 1
# sparse[j][i] = min of arr[i .. i + 2^j - 1]
sparse = [[0] * n for _ in range(k)]
sparse[0] = arr[:]
for j in range(1, k):
for i in range(n - (1 << j) + 1):
sparse[j][i] = min(sparse[j-1][i],
sparse[j-1][i + (1 << (j-1))])
return sparse
def query_min(sparse, left, right):
j = int(math.log2(right - left + 1))
return min(sparse[j][left],
sparse[j][right - (1 << j) + 1])
arr = [2, 4, 3, 1, 6, 7, 8, 9, 1, 7]
st = build_sparse_table(arr)
print(query_min(st, 0, 4)) # 1
The trick: two overlapping windows of length 2^j cover the entire range. For idempotent functions, overlapping is fine. This is called a Range Minimum Query (RMQ) structure.
Use when: static data, min/max/GCD queries, and you need the absolute fastest query time.
Binary Indexed Tree (Fenwick Tree)
The BIT supports both point updates and prefix sum queries in O(log n) time with a very small constant. It uses a clever bit manipulation trick to navigate a compressed implicit tree.
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta):
# 1-indexed
while i 0:
s += self.tree[i]
i -= i & (-i) # move to parent in query direction
return s
def range_query(self, left, right):
# inclusive, 1-indexed
return self.query(right) - self.query(left - 1)
bit = BIT(8)
for idx, val in enumerate([3,1,4,1,5,9,2,6], start=1):
bit.update(idx, val)
print(bit.range_query(2, 5)) # 1+4+1+5 = 11
The key insight: i & (-i) isolates the lowest set bit of i. Adding it moves to the next responsible ancestor for updates; subtracting it moves toward the root for queries.
Common use: counting inversions, order statistics, frequency prefix sums. Often easier to code correctly under pressure than a segment tree.
Segment Tree
The segment tree is the most powerful and flexible range query structure. It supports range queries AND range updates in O(log n) per operation, for any associative function.
Basic Segment Tree (Point Update, Range Sum)
class SegTree:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (2 * self.n)
# build
for i in range(self.n):
self.tree[self.n + i] = nums[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def update(self, i, val):
# set position i to val
i += self.n
self.tree[i] = val
while i > 1:
i //= 2
self.tree[i] = self.tree[2*i] + self.tree[2*i+1]
def query(self, left, right):
# sum [left, right) half-open
res = 0
left += self.n
right += self.n
while left < right:
if left & 1:
res += self.tree[left]
left += 1
if right & 1:
right -= 1
res += self.tree[right]
left //= 2
right //= 2
return res
st = SegTree([3,1,4,1,5,9,2,6])
print(st.query(1, 5)) # 1+4+1+5 = 11
st.update(2, 10) # set index 2 to 10
print(st.query(1, 5)) # 1+10+1+5 = 17
Lazy Propagation for Range Updates
When you need to apply the same update to an entire range (e.g., add 5 to all elements in [l, r]), lazy propagation defers the work until it is needed.
class LazySegTree:
def __init__(self, n):
self.n = n
self.tree = [0] * (4 * n)
self.lazy = [0] * (4 * n)
def push_down(self, node, start, end):
if self.lazy[node] != 0:
mid = (start + end) // 2
self.tree[2*node] += self.lazy[node] * (mid - start + 1)
self.tree[2*node+1] += self.lazy[node] * (end - mid)
self.lazy[2*node] += self.lazy[node]
self.lazy[2*node+1] += self.lazy[node]
self.lazy[node] = 0
def range_add(self, node, start, end, left, right, val):
if right < start or end < left:
return
if left <= start and end <= right:
self.tree[node] += val * (end - start + 1)
self.lazy[node] += val
return
self.push_down(node, start, end)
mid = (start + end) // 2
self.range_add(2*node, start, mid, left, right, val)
self.range_add(2*node+1, mid+1, end, left, right, val)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
def range_sum(self, node, start, end, left, right):
if right < start or end < left:
return 0
if left <= start and end <= right:
return self.tree[node]
self.push_down(node, start, end)
mid = (start + end) // 2
return (self.range_sum(2*node, start, mid, left, right) +
self.range_sum(2*node+1, mid+1, end, left, right))
Use when: you need both range updates and range queries, or when the operation is not idempotent (so sparse table cannot be used).
Coordinate Compression
Before applying any range structure, compress the value space when values are large but the number of distinct values is small.
def compress(arr):
sorted_unique = sorted(set(arr))
rank = {v: i for i, v in enumerate(sorted_unique)}
return [rank[v] for v in arr], sorted_unique
vals = [100, 500, 200, 100, 700]
compressed, mapping = compress(vals)
print(compressed) # [0, 2, 1, 0, 3]
print(mapping) # [100, 200, 500, 700]
This reduces a value range of 10^9 to a BIT/segment tree of size O(n). Critical for counting inversions, 2D query problems, and offline processing.
Which Structure to Use
| Scenario | Best Structure | Build | Query | Update |
|---|---|---|---|---|
| Static data, range sum | Prefix Sum | O(n) | O(1) | N/A |
| Offline range add, read once | Difference Array | O(n) | O(n) | O(1) |
| Static data, range min/max | Sparse Table | O(n log n) | O(1) | N/A |
| Dynamic, point update + prefix sum | Fenwick Tree (BIT) | O(n log n) | O(log n) | O(log n) |
| Dynamic, range update + range query | Segment Tree (lazy) | O(n) | O(log n) | O(log n) |
| 2D range sum, static | 2D Prefix Sum | O(mn) | O(1) | N/A |
Decision checklist:
- Is the data static (no updates)? Use prefix sum or sparse table.
- Static + min/max only? Use sparse table for O(1) queries.
- Dynamic + sum queries? BIT is simpler to code.
- Dynamic + range updates? Use segment tree with lazy propagation.
- Values too large? Compress coordinates first.
Key LeetCode Problems
- 303 – Range Sum Query Immutable: direct prefix sum application.
- 304 – Range Sum Query 2D Immutable: 2D prefix sum.
- 307 – Range Sum Query Mutable: BIT or segment tree for point updates.
- 315 – Count of Smaller Numbers After Self: BIT with coordinate compression, count inversions variant.
- 493 – Reverse Pairs: merge sort or BIT, similar to 315 but with a 2x multiplier twist.
- 1353 – Maximum Number of Events That Can Be Attended: difference array + greedy or segment tree scheduling.
A strong interview answer names the structure, states its complexity, and explains the tradeoff. Implement the simplest structure that satisfies the constraints – a prefix sum beats a segment tree when the data is immutable.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a Binary Indexed Tree (Fenwick Tree) and how does it work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A Fenwick tree supports two operations in O(log n): prefix sum query and point update. It stores partial sums in an array where index i stores the sum of a range determined by the lowest set bit of i. Update (add delta at index i): while i <= n, tree[i] += delta, then i += i & (-i) – this moves to the next responsible ancestor. Prefix sum query (sum from 1 to i): while i > 0, result += tree[i], then i -= i & (-i) – this moves to the parent. The expression i & (-i) isolates the lowest set bit, which is the key insight. Compared to a segment tree, a Fenwick tree is simpler to implement and has a smaller constant factor, but supports fewer operation types (sums only, not arbitrary range queries).”}},{“@type”:”Question”,”name”:”When should you use a sparse table vs a segment tree for range queries?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use a sparse table when the array is static (no updates) and the query operation is idempotent (min, max, GCD – not sum). Sparse table builds in O(n log n) and answers range minimum/maximum queries in O(1) using precomputed overlapping intervals. Use a segment tree when the array requires updates (point updates or range updates with lazy propagation), or when the query operation is not idempotent (range sum, range product). Segment tree builds in O(n) and answers queries and updates in O(log n). For the classic static RMQ problem with millions of queries, sparse table is the fastest.”}},{“@type”:”Question”,”name”:”What is a difference array and when do you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A difference array enables range updates in O(1). Build: diff[0] = arr[0], diff[i] = arr[i] – arr[i-1]. Range update (add val to arr[l..r]): diff[l] += val, diff[r+1] -= val. After all updates, reconstruct the array with a prefix sum pass: arr[i] = arr[i-1] + diff[i]. Use when you have many range update operations and only need the final array values (not intermediate states). Example: LC 1094 (Car Pooling), LC 1109 (Corporate Flight Bookings), LC 370 (Range Addition). Time complexity: O(1) per update, O(n) to reconstruct. Compare to segment tree with lazy propagation which is O(log n) per update but supports range queries between updates.”}},{“@type”:”Question”,”name”:”How does a 2D prefix sum work?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Build: prefix[i][j] = sum of all elements in the rectangle from (0,0) to (i-1,j-1). Formula: prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] – prefix[i-1][j-1]. Range sum query for rectangle (r1,c1) to (r2,c2) (0-indexed): result = prefix[r2+1][c2+1] – prefix[r1][c2+1] – prefix[r2+1][c1] + prefix[r1][c1]. The inclusion-exclusion formula subtracts the two overlapping strips and adds back the doubly-subtracted corner. Build time: O(m*n). Query time: O(1). This is LC 304 (Range Sum Query 2D – Immutable).”}},{“@type”:”Question”,”name”:”How do you solve the "count of range sum" or "smaller number after itself" problems with a BIT?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”These problems (LC 315, LC 493) use a BIT with coordinate compression. For "count of smaller numbers after self" (LC 315): process the array right to left. For each element, query the BIT for the count of elements already inserted that are smaller (prefix sum up to element-1). Then update the BIT at the element position. Since values can be large, compress coordinates first: map all values to ranks in [1, n]. For "reverse pairs" (LC 493): similar pattern but the condition is nums[i] > 2 * nums[j] for i < j. BIT approach runs in O(n log n) vs O(n^2) brute force, and is often preferred over merge sort for this class of problem.”}}]}
Meta coding interviews test range queries and BIT patterns. See common questions for Meta interview: range query and segment tree problems.
Databricks interviews cover efficient data aggregation and range queries. See patterns for Databricks interview: range query and data aggregation problems.
Atlassian coding rounds include range query and prefix sum problems. See patterns for Atlassian interview: range query and prefix sum problems.