Advanced · Module 19 · Lesson 5
Segment tree
General range queries, point/range updates, and lazy propagation.
Lesson 119 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Segment Tree Range Query
Consume fully covered ranges without visiting every value
Query
[1,4]
Visited state
1
Covered nodes
0
Range sum
0
Why this step happens
Start at the root representing the entire array.
Accepted nodes must be disjoint and fully contained in the query.
Theory lesson · Step-by-step
Understand Segment tree
General range queries, point/range updates, and lazy propagation.
Worked approach
Trace the reasoning step by step
- 1Build leaves from input.
- 2Merge children into parents.
- 3For a query, skip disjoint segments and accept fully covered ones.
- 4Descend for partial overlap and lazy-propagate range updates.
Concrete example
Query sum indexes 1…3 in [2,1,3,4].
- 1Split the query across covered tree nodes.
- 2Combine sums 1 + 3 + 4.
Range sum is 8 in O(log n) visited canonical segments.
What must remain true (Loop Invariant)
Each node stores the merge of its segment; parent values remain consistent with both children.
Cost Model
Complexity & Trade-offs
When to use it
- Large constraints requiring specialized string, range, geometry, or network tools.
- Repeated queries or updates that justify preprocessing.
- Problems with a strong algebraic, heuristic, or residual invariant.
Common mistakes
- Using a specialized structure without checking its operation assumptions.
- Mixing zero-based and one-based indexes.
- Memorizing formulas without proving what each stored value means.
Practice prompts
- Reproduce the worked Segment tree example without looking at the trace.
- Change one input condition and explain whether the Segment tree invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check