Graph Theory37 sections · 1633 units
Open in Course

Path Sum Queries

(Sum instead of maximum)

To find the sum of values on a path, use the same algorithm but with a sum segment tree instead of a max segment tree. The path walk logic is identical. You query each chain segment for the sum, then add all the sums together. The segment tree stores range sums instead of range maximums.

This works for any associative operation: min, max, sum, GCD, XOR, etc. Change the segment tree's merge function. The HLD structure remains the same regardless of the operation.