Groups
Prefix sums precompute running totals so any range sum [l, r] can be answered in O(1) time as prefix[r] - prefix[l-1].
Coordinate compression replaces large, sparse, or arbitrary values with small consecutive integers while preserving relative order.