Lessons from Range Sum

Two points:

$1.$ Prefix sums convert range queries into constant-time subtractions. This is a telescoping pattern: $sum[i, j] = prefix[j] - prefix[i-1]$.

$2.$ Precomputing cumulative values (sums, products, XORs) speeds up repeated queries. The pattern: spend $O(n)$ once to answer $O(1)$ later.