0

Prefix Sum

Precompute cumulative aggregates so any range query becomes constant time.

Newinterview weight 6010 problems1 visualisers
18
mastery
Attempts logged
0
Predicted success on the next one
33%
Solved here
0 / 10

What you actually need to hold in your head

  • Range sum is P[r+1] minus P[l]
  • Prefix XOR behaves the same way
  • Difference arrays handle range updates
  • 2D prefix sums via inclusion and exclusion
Comfortable with these first
Arrays18%Hashing18%
Next in the path
Matrix

Watch it run

Step through the algorithm before you write it.

Prefix Sum & Subarray CountM

Count subarrays summing to k. Every subarray sum is a difference of two prefix sums, so a map of seen prefixes does it in one pass.

O(n)

Patterns in this topic

The trigger phrases are what you are training yourself to notice.

Prefix Sum / Prefix XORO(n) build, O(1) per query

Store cumulative totals so any range reduces to a difference of two prefixes, then use a map to count how often a required prefix appeared.

subarray sum equals krange sum query

Prefix Sum problems

Ordered by sheet phase, so the early ones are the highest signal.

0 / 10 solved
1
Contiguous Array
MPrefix Sum
2
Longest Subarray with Sum K
MPrefix Sum
3
Find Pivot Index
EPrefix Sum
4
Car Pooling
MPrefix Sum
5
Count Subarrays with Given XOR
HPrefix Sum
6
Corporate Flight Bookings
MPrefix Sum
7
Maximum Size Subarray Sum Equals kpremium
MPrefix Sum
8
Number of Submatrices That Sum to Target
HPrefix Sum
9
Range Sum Query 2D - Immutable
MPrefix Sum
10
Product of the Last K Numbers
MPrefix Sum