Prefix Sum

Precompute cumulative sums so range-sum queries become O(1) instead of O(n): prefix[i] = sum(arr[0..i-1]), so sum(l,r) = prefix[r+1] - prefix[l]. Extends to prefix XOR and 2D prefix sum for matrices, and is frequently combined with a hash map to count subarrays matching a target sum — store prefix_sum → count, look up prefix_sum - k.

Sub-patterns

• A — 1D Running Prefix Sum. The base case: one pass builds the prefix array, then range queries are O(1).
• B — Prefix Sum + Hash Map. Store prefix-sum counts in a hash map to count subarrays matching a target sum.
• C — 2D / Matrix Prefix Sum. Extends the same idea to rectangular range-sum queries.
• D — Prefix XOR. Same structure, XOR instead of addition.

Practice set (10)

• Easy — Range Sum Query - Immutable, Running Sum of 1d Array, Find Pivot Index
• Medium — Subarray Sum Equals K, Product of Array Except Self, Continuous Subarray Sum, Contiguous Array, Range Sum Query 2D - Immutable, Subarray Sums Divisible by K
• Hard — Maximum Size Subarray Sum Equals k (Premium)