Segment Tree Variants and Functions
You'll learn how to adapt segment trees to compute different aggregate functions like sum, min, max, and GCD, and handle special cases when operations don't commute.
The Core Idea
So far, you've seen how segment trees can efficiently answer range queries and handle updates. But what exactly are we querying? The beauty of segment trees is their flexibility: the same tree structure can compute different aggregate functions over ranges by changing just the merge logic.
Common Aggregate Functions
When building and querying a segment tree, each internal node stores the result of "merging" its children. The merge operation depends on what you're computing:
- Sum: Each node stores the sum of its range. Merge by adding:
node.value = left.value + right.value - Min/Max: Each node stores the minimum or maximum in its range. Merge using
min()ormax() - GCD: Each node stores the greatest common divisor. Merge using the GCD function
- Count: Track occurrences of elements meeting a condition
All these operations are associative (grouping doesn't matter: (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)), which makes segment trees work perfectly.
Non-Commutative Operations
Some operations care about order. For example, tracking a sequence of matrix multiplications or string concatenations. Since matrix multiplication doesn't commute (A × B ≠ B × A), you must carefully maintain left-to-right order when merging child nodes. The segment tree still works—just ensure your merge function respects the ordering.
Choosing Your Function
Pick your aggregate function based on the problem: need range sums for a subarray? Use sum. Finding minimum in a window? Use min. The segment tree structure stays the same; only the merge logic changes.
Key Takeaway: Segment trees are versatile containers that work with any associative function by customizing the merge operation—sum, min, max, GCD, and even non-commutative operations like matrix multiplication all fit the same elegant structure.