Lessons from Prefix Sums

Five patterns to remember:

$1.$ Precompute once, query many times. Prefix sums trade $O(n)$ setup for $O(1)$ queries.

$2.$ Range sum = difference of two prefix values. The formula $pref[r] - pref[l-1]$ is universal.

$3.$ HashMap + prefix sums solves "count subarrays with property X" problems.

$4.$ Prefix and suffix together handle "all except current" scenarios.

$5.$ 2D prefix sums use inclusion-exclusion for rectangle queries. These patterns appear everywhere: subarray sums, grids, string problems. The core idea stays the same.