Questions
20 of 26
What is a Segment Tree? What problems does it solve?
Difficulty: 5/10
Segment Tree
A Segment Tree is a tree data structure for answering range queries efficiently while supporting updates. Each node represents an interval of the underlying array and stores an aggregate such as sum, minimum, maximum, or greatest common divisor. With a suitable merge operation, both range queries and point updates can be performed in O(log n).
javascript
- 1
Build: O(n).
- 2
Point update: O(log n).
- 3
Range query: O(log n) for standard segment-tree operations.
- 4
Uses O(n) memory, commonly around 4n for a recursive implementation.
- 5
Useful for dynamic range sum, min, max, and similar associative queries.
Follow-up Questions
- How would you implement lazy propagation?
- When would a Fenwick Tree be preferable?