Range-query data structures · HTML
Given associative merge and identity, maintain set(i,x) and the aggregate query(l,r) on half-open intervals.
Recognition signals
- Queries and updates interleave
- Adjacent summaries can be merged
- min, max, gcd, or structured summaries are needed
- A point change should touch logarithmically many nodes
- Lazy propagation may later extend range updates
False friends
| Signal | Why it is different |
|---|
| Static idempotent RMQ | With no updates, a Sparse Table answers in O(1). |
| Only point add and prefix sum | A Fenwick tree is shorter and has smaller constants. |
Core invariant
Every internal node always equals merge(left-child summary, right-child summary).
State, transition, and processing order
| Item | Definition |
|---|
| State | An iterative array of length 2*size; leaves start at size and unused leaves hold identity. |
| Transition | After changing a leaf, recompute ancestors; a query collects its canonical decomposition into left and right accumulators. |
| Frontier / order | l and r climb inward from the leaf layer; complete nodes passed by either boundary enter its accumulator. |
Python skeleton
class SegmentTree:
def __init__(self, a, merge=min, identity=float('inf')):
self.merge, self.id = merge, identity
self.n = 1
while self.n < len(a): self.n *= 2
self.t = [identity] * (2 * self.n)
self.t[self.n:self.n+len(a)] = a
for i in range(self.n-1, 0, -1):
self.t[i] = merge(self.t[2*i], self.t[2*i+1])
def set(self, i, value):
i += self.n; self.t[i] = value
while i > 1:
i //= 2
self.t[i] = self.merge(self.t[2*i], self.t[2*i+1])
def query(self, l, r):
l += self.n; r += self.n
left = right = self.id
while l < r:
if l & 1: left = self.merge(left, self.t[l]); l += 1
if r & 1: r -= 1; right = self.merge(self.t[r], right)
l //= 2; r //= 2
return self.merge(left, right)
Correctness sketch
- Bottom-up construction establishes every initial summary.
- A point affects only ancestors of its leaf; recomputing them restores the invariant.
- Query nodes are disjoint and exactly cover the requested interval.
- Two ordered accumulators preserve correctness even when merge is not commutative.
Complexity
| Time | Space | Parameters |
|---|
| O(n) build and O(log n) update/query | O(n) | n elements; size is the next power of two |
Edge cases
- An empty query returns identity
- merge must be associative, not necessarily commutative
- The identity for max over negatives is not zero
- Noncommutative merges require order
- Padding leaves hold identity
Error patterns
| Pattern | Why it fails / fix |
|---|
| Wrong identity | It must truly be neutral for merge over the value domain. |
| Inclusive/exclusive drift | Keep query(l,r) right-exclusive. |
| Reversing the right accumulator | Use merge(tree[r],right). |
Selection and exclusion rules
- Dynamic point updates plus an associative summary: segment tree.
- Invertible prefix sums: prefer Fenwick.
- Static idempotent queries: Sparse Table.
- For range updates, define lazy-tag composition before implementation.
| Relation | Template | Boundary |
|---|
| static alternative | Sparse table static RMQ | There are no updates and the operation is idempotent |
Original micro-example
| Part | Detail |
|---|
| Result | query(1,4) changes from 1 to 0. |
| Scenario | Track minima in [5,1,7,2,4] and change index 2 to 0. |
| Walkthrough | Only that leaf and its ancestors change; a few complete nodes cover the query. |
Recall prompts
My notes