codaBack to Academy
trees
Segment Tree
A Segment Tree is a binary tree used for storing intervals or segments, allowing efficient range queries and point updates. Each leaf node represents a single element, and each internal node stores the result of a merge operation (such as sum, min, or max) over its children's ranges. It is especially powerful for problems involving repeated range queries on mutable arrays.
Use Cases
- •Range sum or range minimum/maximum queries
- •Computational geometry interval problems
- •Competitive programming range update/query tasks
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(log n) | O(log n) | O(log n) |
| Space | O(n) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...