Prefix Sum mind map
Precompute cumulative sums for range queries.
Core idea: Store the aggregate before each position so a range becomes the difference of two histories.
Mnemonic: Accumulate → subtract → answer · Cost: O(n) build · O(1) range query
Query: Range difference
Signal: Many immutable sum queries target arbitrary subarrays.
Move: Store prefix before each index; answer [l, r] with prefix[r + 1] − prefix[l].
Examples: Range Sum Query, Pivot Index, Running Sum
Match: Earlier prefix map
Signal: A subarray must hit a target sum, remainder, or balance.
Move: At each prefix, count or locate the earlier prefix that would complete the condition.
Examples: Subarray Sum K, Divisible Subarrays, Contiguous Array
Update: Difference array
Signal: Many range updates happen before final values are read.
Move: Write only boundary deltas, then accumulate once to materialize every update.
Examples: Range Addition, Car Pooling, Corporate Flight Bookings
Expand: Suffix & 2D inclusion
Signal: The range extends around one index or across a rectangular region.
Move: Combine left/right products, or add and subtract overlapping 2D prefix rectangles.
Examples: Product Except Self, Matrix Region Sum, Largest Balanced Region