Segment Tree

Array: 5, 3, 8, 2, 7, 1, 6, 4. Question: what's the sum of a range, like a[2..5]? Adding them up each time costs O(n). A segment tree answers it in O(log n) — and unlike a prefix-sum array, it still works when values change.