Segment Tree
A tree data structure capable of storing intervals or segments, allowing for efficient range queries and updates.
Build a tree
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
If you have an array and need to find the sum of elements from index L to R frequently, a simple loop takes O(n). A Segment Tree precomputes partial sums in a tree structure, allowing both queries and updates in O(log n).
Concept
A Segment Tree is a full binary tree where each node represents an interval. The root represents the entire array `[0, n-1]`. Its children represent the left half `[0, mid]` and right half `[mid+1, n-1]`. Leaves represent individual elements `[i, i]`.
How it Works
- Build: Construct tree from array. `tree[i] = tree[2*i] + tree[2*i+1]` (for sum).
- Query(L, R): Combine values from nodes that are fully within `[L, R]`.
- Update(i, val): Update leaf node for index `i` and recalculate values up to the root.
- Range Update: (Advanced) Uses Lazy Propagation to defer updates for O(log n).
Step-by-Step Breakdown
- Start at root covering `[0, n-1]`.
- If node's range is completely inside `[L, R]`, return node value.
- If node's range is completely outside `[L, R]`, return 0.
- Otherwise, partial overlap: recurse left and right, then sum the results.
When to Use
- Range queries (Sum, Min, Max, GCD) on an array.
- When element updates are frequent (unlike Prefix Sum which is static).
- Computational Geometry (finding intersecting rectangles).
When NOT to Use
- When the array is static (use Prefix Sum Array for O(1) query).
- When memory is extremely tight (approx 4n space).
- When high-dimensional data is involved (KD-Tree might be better).
How to Identify
Keywords: "Range Sum Query", "Range Minimum Query", "Mutable Array", "Frequent Updates".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.