## What is it? Prefix Sum (also called cumulative sum) preprocesses an array so that any range sum query `sum(i, j)` can be answered in O(1) time. Instead of summing every time, you precompute running totals. ## How it works **Build:** - `prefix[0] = 0` - `prefix[i] = prefix[i-1] + arr[i-1]` for i from 1 to n **Query (sum from index l to r inclusive):** - `sum(l, r) = prefix[r+1] - prefix[l]` ## When to use - Multiple range sum queries on a static array - Subarray sum problems (combined with a hash map for the "sum equals k" pattern) - 2D prefix sums for matrix range queries - Difference arrays for range update + point query ## Key Points - O(n) build, O(1) query — ideal when queries vastly outnumber updates - Zero-indexed prefix array of size n+1 eliminates off-by-one errors - For "subarray sum equals k": use a HashMap storing prefix sum frequencies