Segment tree
Applies to: general
A segment tree answers range queries (sum, min, max) and point updates on an array, both in O(log n), by storing aggregates over halves of the range in a binary tree. It is the heavier cousin of a prefix-sum array, used when the data also changes.
range-sum(2, 5) -> walk the tree, combine the few nodes covering [2,5]