Section Recap

You now have four powerful array techniques:

$1.$ Prefix sums: Precompute cumulative sums for $O(1)$ range queries. Works in 1D and 2D.

$2.$ Difference arrays: The inverse of prefix sums. Enables $O(1)$ range updates.

$3.$ Two pointers: Use sorted structure to find pairs in $O(n)$ without extra space.

$4.$ Sliding window: Solve subarray problems in $O(n)$ by processing each element at most twice. These techniques combine with everything else you'll learn. Learn them, and half of competitive programming problems become tractable. In the next section, I'll show you stacks, a simple data structure with surprising power.