Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Prefix Sum
DSA

Prefix Sum

Learn how prefix sums enable efficient range-sum queries and transform repeated calculations into constant-time operations.

Prefix Sum answers range queries efficiently by preprocessing cumulative information.

Its core idea:

“Compute once, reuse many times” — store running totals, then any range is a subtraction.

Focus on recognizing:

Repeated subarray/range queries → Prefix Sum

Core Template

public int[] buildPrefixSum(int[] arr) {
    int n = arr.length;
    int[] prefix = new int[n];

    prefix[0] = arr[0];

    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }

    return prefix;
}

public int rangeSum(int[] prefix, int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];
}
from itertools import accumulate

def build_prefix_sum(arr):
    return list(accumulate(arr))

def range_sum(prefix, l, r):
    if l == 0:
        return prefix[r]
    return prefix[r] - prefix[l - 1]
vector<int> buildPrefixSum(vector<int>& arr) {
    vector<int> prefix(arr.size());
    partial_sum(arr.begin(), arr.end(), prefix.begin());
    return prefix;
}

int rangeSum(vector<int>& prefix, int l, int r) {
    if (l == 0) return prefix[r];
    return prefix[r] - prefix[l - 1];
}
function buildPrefixSum(arr) {
  const prefix = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i - 1] + arr[i];
  }
  return prefix;
}

function rangeSum(prefix, l, r) {
  if (l === 0) return prefix[r];
  return prefix[r] - prefix[l - 1];
}

Brute force pays O(n) per query; prefix sum pays O(n) once and O(1) forever after.

Pattern 1: Subarray Sum Equals K

Watch the prefix of [1,2,3,4,5] fill in, then sum(1..3) resolve to a single subtraction: 10 − 1 = 9. Press ▶ to animate.

Prefix Sums (Build + O(1) Range Queries)

Precompute a prefix-sum array P where P[i] is the sum of the first i+1 elements. Then ANY subarray sum is a single subtraction: sum(l..r) = P[r] − P[l-1]. Build once in O(n), answer every range query in O(1).

Walk through the array left-to-right building the prefix array where P[i] = sum of first i+1 elements. On the input, seed P[0]=1, then P[1]=P[0]+2=3, P[2]=3+3=6, P[3]=6+4=10, P[4]=10+5=15. The last element gives the total sum for free. Each step uses the previous prefix -- one pass, O(n) time, O(n) space. This precomputation turns any range-sum query into O(1).

ARRAY VISUALIZER
Steps –
1
0
3
1
·
2
·
3
·
4
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        P[0] = nums[0]
                      
                        2
                        for i in 1..n-1:
                      
                        3
                          P[i] = P[i-1] + nums[i]

Count subarrays whose sum equals k — prefix sums + a frequency map:

If prefix[j] − prefix[i] = k, then prefix[i] = prefix[j] − k. Count how often that value appeared before.

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);

    int sum = 0;
    int count = 0;

    for (int num : nums) {
        sum += num;

        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }

        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }

    return count;
}
from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1

    total = 0
    count = 0

    for num in nums:
        total += num
        count += seen[total - k]
        seen[total] += 1

    return count
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> seen;
    seen[0] = 1;

    int sum = 0, count = 0;

    for (int num : nums) {
        sum += num;

        auto it = seen.find(sum - k);
        if (it != seen.end()) count += it->second;

        seen[sum]++;
    }

    return count;
}
function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]);

  let sum = 0,
    count = 0;

  for (const num of nums) {
    sum += num;
    count += seen.get(sum - k) ?? 0;
    seen.set(sum, (seen.get(sum) ?? 0) + 1);
  }

  return count;
}

Prefix Sum + HashMap = subarray counting engine. The map.put(0, 1) seed counts subarrays starting at index 0.

Pattern 2: Prefix Mod (Count Subarrays Divisible by K)

Equal remainders pair up — each pair is one divisible subarray.

Count Subarrays Divisible by K (Prefix Mod)

Count subarrays whose sum is divisible by K. Two prefix sums with the SAME remainder mod K have a subarray between them summing to a multiple of K — so answer = number of ways to pair equal remainders.

arr = [4,5,0,-2,-3,1], K=3. Walk left to right tracking run = (run + x) % 3, and count how many previous prefixes shared each remainder (seed {0:1} for the empty prefix). Each matching pair adds one divisible subarray. Final answer = 6. The running remainder and answer live in the state chips; the array itself is only traversed.

ARRAY VISUALIZER
Steps –
4
0
5
1
0
2
-2
3
-3
4
1
5
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        count = {0: 1}               // empty prefix
                      
                        2
                        run = 0
                      
                        3
                        for x in nums:
                      
                        4
                          run = (run + x) % K
                      
                        5
                          answer += count[run]++;    // pairs with same mod

Transform the prefix before storing it — equal remainders bracket a divisible subarray:

public int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);

    int sum = 0, count = 0;

    for (int num : nums) {
        sum += num;
        int mod = ((sum % k) + k) % k;   // normalize negatives

        count += map.getOrDefault(mod, 0);
        map.put(mod, map.getOrDefault(mod, 0) + 1);
    }

    return count;
}
def subarrays_div_by_k(nums, k):
    seen = {0: 1}
    total = 0
    count = 0

    for num in nums:
        total += num
        mod = total % k          # Python % is already non-negative

        count += seen.get(mod, 0)
        seen[mod] = seen.get(mod, 0) + 1

    return count
int subarraysDivByK(vector<int>& nums, int k) {
    unordered_map<int, int> seen;
    seen[0] = 1;

    int sum = 0, count = 0;

    for (int num : nums) {
        sum += num;
        int mod = ((sum % k) + k) % k;   // normalize negatives

        count += seen[mod]++;
    }

    return count;
}
function subarraysDivByK(nums, k) {
  const seen = new Map([[0, 1]]);

  let sum = 0,
    count = 0;

  for (const num of nums) {
    sum += num;
    const mod = ((sum % k) + k) % k;

    count += seen.get(mod) ?? 0;
    seen.set(mod, (seen.get(mod) ?? 0) + 1);
  }

  return count;
}

Same engine, transformed key: sum % k instead of raw sum.

  • Range updates → Difference Array — the inverse trick.
  • Matrix queries → 2D Prefix Sum — inclusion-exclusion over corners.
  • Max contiguous sum → Kadane — prefix thinking with a reset rule.

Common Mistakes

Forgetting the map.put(0, 1) seed.

Without it, every valid subarray starting at index 0 goes uncounted.

Off-by-one in range queries.

sum(l..r) = prefix[r] − prefix[l−1] — the l−1 is the whole point of the formula.

Negative mods in C++/Java.

((sum % k) + k) % k normalizes; Python’s % already returns non-negative values.

Complexity

OperationTime
BuildO(n)
Range queryO(1)
Subarray countO(n)

My Private Notes

Notes are auto-saved locally to this device.