Prefix Sum.

Problems:

• Range Sum Query * - base
• Find Pivot Index - * - Sliding, Prefix
• Corporate Flight Bookings - Range Updates
• Subarray Sum Equals K - Prefix Sum, HashMap
• Continuous Subarray Sum - Prefix + HashMap Variant
  • prefixSum % k
  • Used to detect multiples.
• Contiguous Array - Binary Prefix Trick
  • 0 → -1
  • 1 → +1
  • Equal prefix sums → equal number of 0s and 1s.
• Binary Subarrays With Sum - Counting Subarrays
  • prefix + hashmap counting
• Count of Range Sum - Hard Prefix + Ordered Structure
  • prefix + merge sort / balanced tree
• Range Sum Query 2D – Immutable
  • rectangle = inclusion-exclusion
• Shortest Subarray with Sum at Least K- Advanced Prefix + Monotonic Deque
  • prefix + monotonic deque

Theory

A prefix sum array stores the sum of elements up to index i.

Array	Prefix Sum	Formula
nums = [2, 4, 6, 8]	prefix = [2, 6, 12, 20]	prefix[i] = nums[0] + nums[1] + ... + nums[i]

The formula in an iterative form:

prefix[0] = nums[0];
for (int i = 1; i < n; i++)
    prefix[i] = prefix[i - 1] + nums[i];

Observations

Once you have prefix sums, you can compute any subarray sum in O(1). This converts many problems from O(n²) → O(n).

For subarray [l, r]:

• sum(l,r) = prefix[r] - prefix[l-1]

Example:

Array	Prefix	Sum
nums = [2,4,6,8]	prefix = [2,6,12,20]	sum(1,3) = 20 - 2 = 18

Prefix sum with HashMap

Prefix can be used with HashMap when solving problems like Find number of subarrays with sum = k

Key identity:

• prefix[j] - prefix[i] = k

Rearrange:

• prefix[i] = prefix[j] - k

So while scanning we can count how many prefixSum == currentSum - k

Algorithm:

map[0] = 1
sum = 0

for num in nums:
    sum += num
    count += map[sum - k]
    map[sum]++

Difference Array Trick (Range Updates)

Instead of updating every element to add +5 to a range [l,r]

Use:

• diff[l] += 5
• diff[r+1] -= 5

Then compute prefix to apply updates. This is used in problems like Flight Bookings.

2D Prefix Sum

For matrices: Used for fast rectangle queries such as sum(x1,y1,x2,y2)

Formula:

• P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]