Least You Need to Know: Prefix Sums, Range Aggregates, and Subtracting History
Open lesson
Prefix sums precompute cumulative totals so a range sum becomes one subtraction of two histories. This is one of the highest-leverage preprocessing tricks in algorithmic problem solving.