Course contentsShow
← Computer Science
Lesson 647 of 2,87215. Tries and Specialized TreesFree lesson

Segment Tree Variants and Functions

Adapting segment trees for different aggregate functions: sum, min, max, GCD, and handling non-commutative operations.

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() or max()
  • 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.