Prefix Sum Technique

Say someone hands you an array of numbers. Then they keep asking you questions. What is the sum from index 2 to index 5? Now from 1 to 7? Now from 0 to 4? If you loop and add the numbers every single time, each question costs you a full walk through that range. Ask a thousand questions and you do a thousand slow walks. That is the pain. The prefix sum technique fixes it. Each question becomes one quick step.

🤔 What Is a Prefix Sum?

A prefix sum array is an array where each spot stores the running total of all numbers up to that point. Running total means you keep adding as you move from left to right.

So if your array is [3, 1, 4, 1, 5], the prefix sums are:

• spot 0 -> 3
• spot 1 -> 3 + 1 = 4
• spot 2 -> 3 + 1 + 4 = 8
• spot 3 -> 3 + 1 + 4 + 1 = 9
• spot 4 -> 3 + 1 + 4 + 1 + 5 = 14

Notice the pattern. Each prefix value is just the value before it plus the current number. You never add up from the start again.

Think of it like a running score in a cricket match. After every over the scoreboard shows the total runs so far. You do not add up every over again to know the score. You just look at the board.

🎯 Why Range Sums Become Fast

Here is the trick that makes this worth it. Once you have the prefix array, the sum of any range from left to right is just one subtraction.

The sum from left to right equals prefix[right] - prefix[left - 1].

Here is the idea in plain words:

• prefix[right] is the total from the start up to right.
• prefix[left - 1] is the total from the start up to just before left.
• Subtract the second from the first. What is left is exactly the chunk between left and right.

There is one edge case to watch. When left is 0 there is no left - 1. So the answer is simply prefix[right]. The range already starts at the very beginning.

Here is the same idea as a picture. We want the sum from index 1 to 3.

The numbers 1, 4, 1 from index 1 to 3 add up to 6. The subtraction gives the same 6 without adding anything again.

📝 Steps to Use Prefix Sums

Let us list the work clearly before we write any code. The whole thing is just one pass to build, then quick lookups after that.

1. Make a new array prefix the same size as the input array.
2. Set prefix[0] to the first element of the input array.
3. Walk from index 1 to the end. For each index i, set prefix[i] = prefix[i - 1] + arr[i].
4. To answer a range query left to right, return prefix[right] - prefix[left - 1].
5. If left is 0, just return prefix[right] so you do not read a negative index.

That is the whole technique. Building the array is one pass. Each query after that is instant.

💻 Building Prefix Sums and Answering Queries

Now let us put it together. The code below builds the prefix array from [3, 1, 4, 1, 5]. Then it answers two range questions. The sum from index 1 to 3, and the sum from index 0 to 4.

#include <stdio.h>

// Build the prefix sum array
void buildPrefix(int arr[], int prefix[], int n) {
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
}

// Answer the sum of the range left..right in O(1)
int rangeSum(int prefix[], int left, int right) {
    if (left == 0) {
        return prefix[right];
    }
    return prefix[right] - prefix[left - 1];
}

int main() {
    int arr[] = {3, 1, 4, 1, 5};
    int n = 5;
    int prefix[5];

    buildPrefix(arr, prefix, n);

    printf("Sum from index 1 to 3: %d\n", rangeSum(prefix, 1, 3));
    printf("Sum from index 0 to 4: %d\n", rangeSum(prefix, 0, 4));
    return 0;
}

Sum from index 1 to 3: 6
Sum from index 0 to 4: 14

#include <iostream>
#include <vector>
using namespace std;

// Build the prefix sum array
vector<int> buildPrefix(const vector<int>& arr) {
    vector<int> prefix(arr.size());
    prefix[0] = arr[0];
    for (size_t i = 1; i < arr.size(); i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    return prefix;
}

// Answer the sum of the range left..right in O(1)
int rangeSum(const vector<int>& prefix, int left, int right) {
    if (left == 0) {
        return prefix[right];
    }
    return prefix[right] - prefix[left - 1];
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5};
    vector<int> prefix = buildPrefix(arr);

    cout << "Sum from index 1 to 3: " << rangeSum(prefix, 1, 3) << endl;
    cout << "Sum from index 0 to 4: " << rangeSum(prefix, 0, 4) << endl;
    return 0;
}

Sum from index 1 to 3: 6
Sum from index 0 to 4: 14

public class PrefixSum {

    // Build the prefix sum array
    static int[] buildPrefix(int[] arr) {
        int[] prefix = new int[arr.length];
        prefix[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefix[i] = prefix[i - 1] + arr[i];
        }
        return prefix;
    }

    // Answer the sum of the range left..right in O(1)
    static int rangeSum(int[] prefix, int left, int right) {
        if (left == 0) {
            return prefix[right];
        }
        return prefix[right] - prefix[left - 1];
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5};
        int[] prefix = buildPrefix(arr);

        System.out.println("Sum from index 1 to 3: " + rangeSum(prefix, 1, 3));
        System.out.println("Sum from index 0 to 4: " + rangeSum(prefix, 0, 4));
    }
}

Sum from index 1 to 3: 6
Sum from index 0 to 4: 14

# Build the prefix sum array
def build_prefix(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]
    for i in range(1, len(arr)):
        prefix[i] = prefix[i - 1] + arr[i]
    return prefix

# Answer the sum of the range left..right in O(1)
def range_sum(prefix, left, right):
    if left == 0:
        return prefix[right]
    return prefix[right] - prefix[left - 1]

arr = [3, 1, 4, 1, 5]
prefix = build_prefix(arr)

print("Sum from index 1 to 3:", range_sum(prefix, 1, 3))
print("Sum from index 0 to 4:", range_sum(prefix, 0, 4))

Sum from index 1 to 3: 6
Sum from index 0 to 4: 14

// Build the prefix sum array
function buildPrefix(arr) {
  const prefix = new Array(arr.length);
  prefix[0] = arr[0];
  for (let i = 1; i < arr.length; i++) {
    prefix[i] = prefix[i - 1] + arr[i];
  }
  return prefix;
}

// Answer the sum of the range left..right in O(1)
function rangeSum(prefix, left, right) {
  if (left === 0) {
    return prefix[right];
  }
  return prefix[right] - prefix[left - 1];
}

const arr = [3, 1, 4, 1, 5];
const prefix = buildPrefix(arr);

console.log("Sum from index 1 to 3:", rangeSum(prefix, 1, 3));
console.log("Sum from index 0 to 4:", rangeSum(prefix, 0, 4));

Sum from index 1 to 3: 6
Sum from index 0 to 4: 14

⏱️ Complexity at a Glance

Here is the time and space cost of each part.

Look at the last two rows. With plain looping, more queries means more full walks. With prefix sums you pay O(n) once to build. Then each query is basically free.

⚠️ Common Mistakes

A few slip-ups catch people the first time. Watch for these.

• Forgetting the left == 0 case and reading prefix[-1]. That gives a wrong answer or crashes.
• Mixing up prefix[left] and prefix[left - 1]. You must subtract the value just before left, not at left. Otherwise you drop one element.
• Rebuilding the prefix array for every query. Build it once, then reuse it. Rebuilding throws away the whole speed gain.
• Using prefix sums when the array keeps changing. If values get updated often, the prefix array goes stale and you keep rebuilding it. For that case a different structure fits better.

🧩 What You’ve Learned

✅ A prefix sum array stores the running total up to each index.

✅ You build it in one pass. Each spot is the spot before it plus the current number.

✅ The sum of any range is prefix[right] - prefix[left - 1], answered in O(1).

✅ When left is 0, the answer is just prefix[right].

✅ Building is O(n) once, and every query after that is O(1). That beats looping for each query.

🚀 What’s Next?

You can now answer range sums in one step. Next, learn two more array techniques that turn slow nested loops into fast single passes.

• Sliding Window Technique
• Two Pointer Technique