Segment Tree Basics
A segment tree is a binary tree built over an array that answers range queries, such as the sum or minimum over a slice, and supports point updates, both in logarithmic time. A plain array does range sums fast but updates break a precomputed prefix.
Structure
Each leaf holds one array element. Each internal node stores the combined result, such as the sum, of the range covered by its two children. The root covers the whole array, and the tree has about twice as many nodes as elements.
Querying and updating
- To query a range, start at the root and descend, fully using nodes whose range lies inside the query and splitting nodes that partly overlap.
- To update an element, change the matching leaf and walk up the tree recomputing each ancestor.
Both operations touch only a logarithmic number of nodes because the tree height is logarithmic. Lazy propagation extends this to fast range updates.
Key idea
Storing combined results over halving ranges makes both queries and updates logarithmic.