Prefix Sum

Pre-computes cumulative sums to find the sum of any subarray in constant time.

The Approach

Create a prefix sum array where `prefix[i]` is the sum of all elements up to `i-1` in the original array.
The sum of a subarray from index `i` to `j` can then be calculated as `prefix[j+1] - prefix[i]`.
Often used with a HashMap to find subarrays with a specific sum by checking for `current_sum - target_sum`.

Types of Prefix Sum

Static Prefix Sum

Used for immutable arrays to answer multiple range sum queries efficiently.

1. Original Array

idx 0

idx 1

idx 2

-1

idx 3

idx 4

idx 5

2. Build Prefix Sum Array

idx -1

idx 0

idx 1

idx 2

idx 3

idx 4

idx 5

3. Query Subarray Sum

Find sum of subarray from index 2 to 5.

prefix[r+1]

prefix[l]

Sum

HashMap with Prefix Sum

Used to count subarrays with a specific sum by storing frequencies of prefix sums.

1. Original Array

idx 0

idx 1

idx 2

-1

idx 3

idx 4

idx 5

2. Build Prefix Sum Array

idx -1

idx 0

idx 1

idx 2

idx 3

idx 4

idx 5

3. Query Subarray Sum

Find sum of subarray from index 2 to 5.

prefix[r+1]

prefix[l]

Sum

Common Problems

Subarray Sum Equals K

Prefix Sum + HashMap

Range Sum Query Immutable

Prefix Sum

Continuous Subarray Sum

Prefix Sum + HashMap

Find Pivot Index

Prefix Sum