Prefix Sum. - rFronteddu/general_wiki GitHub Wiki

Problems:

• Range Sum Query - base
• Find Pivot Index - sliding
• Corporate Flight Bookings - range updates
• Subarray Sum Equals K - map
• Continuous Subarray Sum - modulo, used to detect multiples. **
• Contiguous Array - binary prefix trick
• Count of Range Sum - merge sort, balanced tree ***
• Range Sum Query 2D – Immutable - rectangle inclusion/exclusion *
• Shortest Subarray with Sum at Least K - 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]