Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A Segment Tree is a binary tree that stores aggregate information (sum, min, max, gcd) about segments of an array
A Segment Tree is a binary tree that stores aggregate information (sum, min, max, gcd) about segments of an array.
Each leaf holds one array element; each internal node holds the aggregate of its children's segments.
It answers range queries (e.g.
"sum of arr[l..r]") in O(log n) and supports point updates in O(log n), all with O(n) construction and O(n) space.
How It Works
The tree is stored in a flat array of size ~4n.
Node 1 (index 1) covers [0, n-1]; node i covers [l, r], its left child 2i covers [l, mid], and right child 2i+1 covers [mid+1, r].
A range query walks the tree: if a node's segment is fully inside the query, return its aggregate; if fully outside, skip it; otherwise recurse into both children.
A point update only recomputes the O(log n) nodes on the path from the root to the updated leaf.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Build | O(n) | O(n) |
| Range Query (sum/min/max) | O(log n) | O(log n) stack |
| Point Update | O(log n) | O(1) |
| Range Update (lazy) | O(log n) | O(n) lazy array |
| Storage | 4n array nodes | O(n) |
Best Use Cases
- Range sum / min / max queries with point updates (classic competitive programming)
- Range updates with lazy propagation (range add, range assign)
- RMQ (Range Minimum Query) and segment statistics
- Dynamic prefix/suffix aggregate problems
- Spatial data (segment trees generalize to 2D for geometry queries)
Worked Example
Build, query (1,4), and update index 2 on [2, 5, 1, 8, 3, 7]
Input: array = [2, 5, 1, 8, 3, 7]; query sum(1,4); update idx 2 → 10- 1 Build: leaves hold the 6 elements; internal nodes merge children so the root holds the total 2+5+1+8+3+7 = 26.
- 2 Query sum(1,4): decompose the range into covered segments — node(s) for 5, then 1+8, then 3.
- 3 Sum(1,4) = 5 + 1 + 8 + 3 = 17, assembled from O(log n) node aggregates.
- 4 Update index 2 to 10: recompute only the O(log n) nodes on the path from that leaf to the root.
- 5 The root total becomes 26 − 1 + 10 = 35 after the update.
Pseudocode
function build(node, l, r):
if l == r:
tree[node] = arr[l]
return
mid = (l + r) / 2
build(2*node, l, mid)
build(2*node+1, mid+1, r)
tree[node] = tree[2*node] + tree[2*node+1] function query(node, l, r, ql, qr):
if ql <= l and r <= qr: return tree[node]
if qr < l or r < ql: return 0
mid = (l + r) / 2
left = query(2*node, l, mid, ql, qr)
right = query(2*node+1, mid+1, r, ql, qr)
return left + right function update(node, l, r, idx, val):
if l == r:
tree[node] = val; return
mid = (l + r) / 2
if idx <= mid:
update(2*node, l, mid, idx, val)
else:
update(2*node+1, mid+1, r, idx, val)
tree[node] = tree[2*node] + tree[2*node+1] Build
Build the tree, then query ranges or update points in O(log n).