Sign in to watch this lesson
Advanced - Data Structures and Range Queries · 3:42
Segment Tree - Custom Merges and Tree Descent
A segment-tree node can store anything that merges associatively, as long as the merge has the right identity: (max, count) uses (−∞, 0) and gcd uses 0. Four numbers per node (sum, best prefix, best suffix, best stretch) answer the maximum subarray sum in a range with point updates, where the answer may be the bridge L.suff + R.pref across the middle. Walking down the tree instead of querying it finds the k-th one or the shortest prefix reaching a sum in O(log n) rather than O(log² n), and pruning nodes with max ≤ x finds the first value above x.
You will learn
- Design custom segment-tree merges such as (max, count) and gcd, with the correct identity element
- Implement the four-field node (sum, pref, suff, ans) for range maximum-subarray queries with point updates
- Find the k-th one/zero and the shortest prefix with sum ≥ x by descending the tree in O(log n)
- Avoid the classic bugs: wrong identities, empty-vs-non-empty leaves, missing pruning in get_first, and O(log² n) binary searches