collections/segment_tree_utils library

Segment tree for associative range queries (sum / min / max) — roadmap #495.

Answers range queries (sum, minimum, or maximum over an inclusive index range) in O(log n) with O(log n) point updates. A plain array makes one of the two cheap and the other O(n); the segment tree balances both by storing each internal node's combined value over a contiguous span.

This is an iterative (bottom-up) segment tree: the leaves live in _tree[n .. 2n) and each internal node i holds combine(_tree[2i], _tree[2i+1]). The combine operation must be associative and commutative — sum, min, and max all are — because the iterative range walk may merge the left and right partial results in either order.

Classes

SegmentTree

A segment tree over num supporting point updates and range queries.

Typedefs

SegmentCombine = num Function(num a, num b)

Combines two values into one (must be associative and commutative).