Prefix sums and difference arrays

Imagine a ride-sharing app that needs to answer thousands of queries like “how many rides happened between hour 3 and hour 7?” on the same dataset. If the app recomputes that sum from scratch every time, each query costs O(n). With q queries, that becomes O(n × q) work.

That is fine for one query. It is terrible for ten thousand.

Prefix sums solve this by doing one O(n) preprocessing pass up front. After that, every range-sum query becomes O(1): just a subtraction. Difference arrays flip the idea around: instead of answering range queries fast, they make range updates fast.

These two techniques are simple, but they show up everywhere: dashboards, spreadsheets, image processing, analytics, and competitive programming.

Building a prefix sum array

The core idea is simple: store the running total as you move left to right.

For the array:

arr = [3, 1, 4, 1, 5, 9]

we build a new array called prefix where prefix[i] means: the sum of the first i elements.

That definition is why most implementations use a sentinel at the front:

• prefix[0] = 0
• prefix[1] = 3
• prefix[2] = 4
• prefix[3] = 8
• prefix[4] = 9
• prefix[5] = 14
• prefix[6] = 23

Step by step:

• prefix[0] = 0
• prefix[1] = prefix[0] + arr[0] = 3
• prefix[2] = prefix[1] + arr[1] = 4
• prefix[3] = prefix[2] + arr[2] = 8
• prefix[4] = prefix[3] + arr[3] = 9
• prefix[5] = prefix[4] + arr[4] = 14
• prefix[6] = prefix[5] + arr[5] = 23

The general formula is:

prefix[i] = prefix[i-1] + arr[i-1]

Why the i-1 on arr? Because prefix is deliberately one element longer than the original array. That extra zero at the front makes the math cleaner later.

arr = [3, 1, 4, 1, 5, 9]
prefix = [0] * (len(arr) + 1)

for i in range(1, len(arr) + 1):
    prefix[i] = prefix[i - 1] + arr[i - 1]

print(prefix)  # [0, 3, 4, 8, 9, 14, 23]

int[] arr = {3, 1, 4, 1, 5, 9};
int[] prefix = new int[arr.length + 1];

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

System.out.println(Arrays.toString(prefix));

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

vector<int> arr = {3, 1, 4, 1, 5, 9};
vector<int> prefix(arr.size() + 1, 0);

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

for (int x : prefix) cout << x << ' ';

Complexity: building the prefix array takes O(n) time and O(n) extra space. The payoff comes when you answer many queries afterward.

Answering range queries

Suppose we want the sum from index l to index r, inclusive.

The magic formula is:

sum(l, r) = prefix[r+1] - prefix[l]

Why does this work?

• prefix[r+1] contains the sum of elements 0..r
• prefix[l] contains the sum of elements 0..l-1
• subtracting removes everything before l
• what remains is exactly l..r

Using our array [3, 1, 4, 1, 5, 9] and prefix array [0, 3, 4, 8, 9, 14, 23]:

• sum(1, 3) = prefix[4] - prefix[1] = 9 - 3 = 6 → 1 + 4 + 1 = 6
• sum(2, 5) = prefix[6] - prefix[2] = 23 - 4 = 19 → 4 + 1 + 5 + 9 = 19
• sum(0, 4) = prefix[5] - prefix[0] = 14 - 0 = 14 → 3 + 1 + 4 + 1 + 5 = 14

That is the entire trick. The preprocessing did all the heavy lifting.

arr = [3, 1, 4, 1, 5, 9]
prefix = [0] * (len(arr) + 1)

for i in range(1, len(arr) + 1):
    prefix[i] = prefix[i - 1] + arr[i - 1]

def range_sum(l, r):
    return prefix[r + 1] - prefix[l]

print(range_sum(1, 3))  # 6
print(range_sum(2, 5))  # 19
print(range_sum(0, 4))  # 14

int[] arr = {3, 1, 4, 1, 5, 9};
int[] prefix = new int[arr.length + 1];

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

static int rangeSum(int[] prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

vector<int> arr = {3, 1, 4, 1, 5, 9};
vector<int> prefix(arr.size() + 1, 0);

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

auto range_sum = [&](int l, int r) {
    return prefix[r + 1] - prefix[l];
};

Now the complexity tradeoff becomes clear:

• build once: O(n)
• each query: O(1)
• total for many queries: O(n + q) instead of O(n × q)

Difference arrays for range updates

Now switch to the opposite problem.

You have an array of zeros and many updates like:

• add 3 to every index in [1, 4]
• add 2 to every index in [3, 6]
• add -1 to every index in [0, 2]

If you update every element one by one, each operation costs O(n) in the worst case. With m updates, that becomes O(n × m).

A difference array makes each update O(1).

The rule is:

• D[l] += val → start the effect here
• D[r+1] -= val → cancel the effect after the range

Then, after all updates, take a cumulative sum of D to reconstruct the final array.

That is why difference arrays feel like the inverse of prefix sums:

• prefix sum = cumulative sum of the original array
• difference array = store changes, then cumulative-sum them back into the original

Let us apply the three updates to an array of length 8.

After marking only the boundaries, the difference array becomes:

D = [-1, 3, 0, 3, 0, -3, 0, -2, 0]

Now cumulative-sum it:

• index 0: -1
• index 1: -1 + 3 = 2
• index 2: 2 + 0 = 2
• index 3: 2 + 3 = 5
• index 4: 5 + 0 = 5
• index 5: 5 - 3 = 2
• index 6: 2 + 0 = 2
• index 7: 2 - 2 = 0

Final array:

[-1, 2, 2, 5, 5, 2, 2, 0]

n = 8
updates = [(1, 4, 3), (3, 6, 2), (0, 2, -1)]
diff = [0] * (n + 1)

for l, r, val in updates:
    diff[l] += val
    if r + 1 < len(diff):
        diff[r + 1] -= val

result = [0] * n
running = 0
for i in range(n):
    running += diff[i]
    result[i] = running

print(result)  # [-1, 2, 2, 5, 5, 2, 2, 0]

int n = 8;
int[][] updates = {
    {1, 4, 3},
    {3, 6, 2},
    {0, 2, -1}
};

int[] diff = new int[n + 1];
for (int[] u : updates) {
    int l = u[0], r = u[1], val = u[2];
    diff[l] += val;
    if (r + 1 < diff.length) {
        diff[r + 1] -= val;
    }
}

int[] result = new int[n];
int running = 0;
for (int i = 0; i < n; i++) {
    running += diff[i];
    result[i] = running;
}

int n = 8;
vector<array<int, 3>> updates = {
    {1, 4, 3},
    {3, 6, 2},
    {0, 2, -1}
};

vector<int> diff(n + 1, 0);
for (auto [l, r, val] : updates) {
    diff[l] += val;
    if (r + 1 < (int)diff.size()) {
        diff[r + 1] -= val;
    }
}

vector<int> result(n, 0);
int running = 0;
for (int i = 0; i < n; i++) {
    running += diff[i];
    result[i] = running;
}

This pattern is perfect when you have many range updates but only need the final array once at the end.

2D prefix sums

Prefix sums also extend naturally to grids.

Imagine a 4×4 matrix of ride counts by day and hour block, or pixel intensities in an image:

2 1 3 4
0 6 3 2
7 2 1 5
4 3 8 1

If you repeatedly ask for sums of sub-rectangles, recomputing every cell inside the rectangle is too slow.

The 2D version stores a prefix matrix P where P[i][j] is the sum of everything in the rectangle from (0,0) to (i-1,j-1).

The build formula is:

P[i][j] = grid[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

The - P[i-1][j-1] part matters because the top-left area got added twice.

That is the same inclusion-exclusion idea you use in probability or set counting.

For region sums, the formula is:

sum(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

A concrete example

Take the rectangle from rows 1..2 and columns 1..3:

6 3 2
2 1 5

The direct sum is 6 + 3 + 2 + 2 + 1 + 5 = 19.

Using the prefix matrix:

• take the big rectangle ending at (2,3)
• subtract the extra rows above it
• subtract the extra columns left of it
• add back the top-left overlap once

So:

sum(1,1,2,3) = P[3][4] - P[1][4] - P[3][1] + P[1][1]

That is the whole mental picture:

1. add the large rectangle you want to end at the bottom-right corner,
2. subtract the top strip,
3. subtract the left strip,
4. add back the corner overlap because you subtracted it twice.

grid = [
    [2, 1, 3, 4],
    [0, 6, 3, 2],
    [7, 2, 1, 5],
    [4, 3, 8, 1],
]

rows, cols = len(grid), len(grid[0])
P = [[0] * (cols + 1) for _ in range(rows + 1)]

for i in range(1, rows + 1):
    for j in range(1, cols + 1):
        P[i][j] = (
            grid[i - 1][j - 1]
            + P[i - 1][j]
            + P[i][j - 1]
            - P[i - 1][j - 1]
        )

def region_sum(r1, c1, r2, c2):
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

print(region_sum(1, 1, 2, 3))  # 19

int[][] grid = {
    {2, 1, 3, 4},
    {0, 6, 3, 2},
    {7, 2, 1, 5},
    {4, 3, 8, 1}
};

int rows = grid.length;
int cols = grid[0].length;
int[][] P = new int[rows + 1][cols + 1];

for (int i = 1; i <= rows; i++) {
    for (int j = 1; j <= cols; j++) {
        P[i][j] = grid[i - 1][j - 1]
                + P[i - 1][j]
                + P[i][j - 1]
                - P[i - 1][j - 1];
    }
}

static int regionSum(int[][] P, int r1, int c1, int r2, int c2) {
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
}

vector<vector<int>> grid = {
    {2, 1, 3, 4},
    {0, 6, 3, 2},
    {7, 2, 1, 5},
    {4, 3, 8, 1}
};

int rows = grid.size();
int cols = grid[0].size();
vector<vector<int>> P(rows + 1, vector<int>(cols + 1, 0));

for (int i = 1; i <= rows; i++) {
    for (int j = 1; j <= cols; j++) {
        P[i][j] = grid[i - 1][j - 1]
                + P[i - 1][j]
                + P[i][j - 1]
                - P[i - 1][j - 1];
    }
}

auto region_sum = [&](int r1, int c1, int r2, int c2) {
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1];
};

For a static grid with many rectangle queries, this is one of the cleanest optimizations you can learn.

When to use each technique

A simple rule of thumb:

• if the data is static and queries are frequent, think prefix sum
• if updates are batched and you only need the final result later, think difference array
• if you need both updates and queries online, you probably need a more advanced tree structure

Practical applications

These techniques are not just interview tricks.

• Running totals in spreadsheets: monthly sales, balances, cumulative progress.
• Image processing: integral images let you sum rectangular pixel blocks quickly for blur, box filters, and feature detection.
• Competitive programming: prefix sums appear with counts, parity, XOR, products, and frequency arrays.
• Database range aggregates: analytics systems often precompute partial totals to answer dashboard queries faster.

Once you notice the pattern — “same data, many contiguous range questions” — prefix sums start appearing everywhere.

Common pitfalls

1. Off-by-one errors

   • Decide what prefix[i] means.
   • In this post, it means “sum of the first i elements.”
   • That is why the query formula uses prefix[r+1] - prefix[l].

2. Integer overflow

   • If the array can hold large values, the prefix sums may exceed int.
   • Use long in Java or long long / int64_t in C++ when needed.

3. Forgetting the sentinel

   • prefix[0] = 0 is not cosmetic.
   • It makes queries that start at index 0 work naturally.

4. Confusing inclusive and exclusive bounds

   • The array range [l, r] is inclusive here.
   • The prefix array is effectively using an exclusive right endpoint.
   • Mixing those conventions is the source of many bugs.

When your answer is wrong by exactly one chunk on the left or right, suspect the indexing before anything else.

Practice problems

• Range Sum Query - Immutable (#303) — Easy
• Subarray Sum Equals K (#560) — Medium
• Corporate Flight Bookings (#1109) — Medium (difference array)
• Matrix Block Sum (#1314) — Medium (2D prefix)
• Product of Array Except Self (#238) — Medium (prefix product idea)

A good progression is: start with immutable range sums, then move to difference arrays, then learn how prefix ideas combine with hash maps in subarray problems.

What’s next

Next up: fast and slow pointers.

Prefix sums teach you how to preprocess cumulative information. Fast/slow pointers teach a different kind of efficiency: how to learn structural information from a sequence in one pass without extra memory.