Decoded

Prefix Sum

Stores running sums so subarray sums can be found quickly.

1. Original Array

3
idx 0
5
idx 1
2
idx 2
-1
idx 3
4
idx 4
6
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

Where It's Used

  • Calculating the sum of subarrays quickly.
  • Problems involving range sum queries.
  • Counting subarrays that satisfy a condition.
  • Reducing repeated summation of overlapping ranges.

Problems Using This Pattern

Subarray Sum Equals K

Prefix Sum + HashMap

Range Sum Query Immutable

Prefix Sum

Continuous Subarray Sum

Prefix Sum + HashMap

Find Pivot Index

Prefix Sum