What is a Segment Tree? What problems does it solve?

Difficulty: 6/10

range queries, point updates, lazy propagation

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.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions