Segment Trees

Range Queries on Mutable Arrays

1:00

How segment trees answer range queries and point updates on mutable arrays in O(log n) by storing aggregates at every node of a binary tree over the array.

By the end, you can

Explain why segment trees beat prefix sums on mutable arrays and when each structure is preferable.
Describe what value every node (leaf and internal) stores in a sum segment tree.
Trace the O(n) build procedure and explain why the complexity is O(n) and not O(n log n).
Apply the three-case range-query rule and identify the O(log n) nodes that contribute to a query result.
Trace a point update through the tree, identifying which nodes are re-merged and why.
Name at least four valid merge functions and state the property they must satisfy.
Explain what lazy propagation defers and how it maintains O(log n) range-update complexity.
Compare segment trees, prefix sums, and Fenwick trees and choose the appropriate structure for a given workload.

Up next in String Algorithms, Advanced DP & Competitive Techniques