Prefix Sums and Difference Arrays

Your bank statement shows a running balance after each transaction. Suppose you want to know how much you spent between the 10th and the 20th of the month. You do not add up eleven days of transactions. You take the balance after the 20th and subtract the balance before the 10th.

That subtraction trick is the whole idea behind prefix sums. If you store the running total once, then the total of any stretch of data is the difference of two stored numbers. It is the standard way to answer many "sum of a range" questions quickly, and it opens the door to a surprising number of subarray problems.

This article also covers the mirror image, the difference array, which makes it cheap to apply many range updates.

• How to build a prefix sum array and answer range-sum queries in O(1).
• How to get the index convention right, so there are no off-by-one errors.
• How to combine prefix sums with a hash map to count subarrays with a given sum.
• Prefix and suffix products, and 2D prefix sums.
• How a difference array turns many range updates into O(1) each.

You are given an array a of n numbers and q queries. Each query gives two positions left and right, and asks for the sum of a[left..right], including both ends.

Brute force. For each query, loop from left to right and add. One query costs O(n), so q queries cost O(n × q). With n = q = 100,000 that is ten billion steps.

Prefix sums. Precompute the running totals once, in O(n). Each query is then a single subtraction, O(1), for a total of O(n + q).

Here is the convention we will use throughout:

prefix[i] is the sum of the first i elements of a, that is a[0] + ... + a[i - 1]. So prefix[0] = 0 (the sum of nothing), and prefix has length n + 1.

Each entry builds on the one before it: prefix[i + 1] = prefix[i] + a[i].

With this convention:

The sum of a[left..right] (inclusive) equals prefix[right + 1] - prefix[left].

Why? prefix[right + 1] is the total of everything from position 0 through right. prefix[left] is the total of everything from 0 through left - 1. Subtracting removes the part before left, leaving exactly a[left..right].

The leading 0 is not decoration. It makes the formula work when left = 0, because then we subtract prefix[0] = 0, and no special case is needed.

Dry run for a = [3, 1, 4, 1, 5, 9, 2, 6]:

So prefix = [0, 3, 4, 8, 9, 14, 23, 25, 31]. For the query left = 2, right = 5 (the elements 4, 1, 5, 9): prefix[6] - prefix[2] = 23 - 4 = 19, and indeed 4 + 1 + 5 + 9 = 19.

// File: Main.javaimport java.util.Arrays;public class Main {    static class PrefixSum {        private final long[] prefix;      // prefix[i] = sum of the first i elements        PrefixSum(int[] a) {            prefix = new long[a.length + 1];            for (int i = 0; i < a.length; i++) {                prefix[i + 1] = prefix[i] + a[i];            }        }        // Sum of a[left..right], both ends included.        long sum(int left, int right) {            if (left < 0 || right >= prefix.length - 1 || left > right) {                throw new IndexOutOfBoundsException("bad range " + left + ".." + right);            }            return prefix[right + 1] - prefix[left];        }        @Override        public String toString() {            return Arrays.toString(prefix);        }    }    public static void main(String[] args) {        int[] a = {3, 1, 4, 1, 5, 9, 2, 6};        PrefixSum ps = new PrefixSum(a);        System.out.println(ps);        System.out.println(ps.sum(2, 5) + " " + ps.sum(0, 7) + " " + ps.sum(4, 4) + " " + ps.sum(0, 0));        try {            ps.sum(5, 2);        } catch (IndexOutOfBoundsException e) {            System.out.println("error: " + e.getMessage());        }        int matches = 0;        for (int left = 0; left < a.length; left++) {            long brute = 0;            for (int right = left; right < a.length; right++) {                brute += a[right];                if (brute == ps.sum(left, right)) {                    matches++;                }            }        }        System.out.println(matches + " of 36 ranges match the brute force");    }}

[0, 3, 4, 8, 9, 14, 23, 25, 31]19 31 5 3error: bad range 5..236 of 36 ranges match the brute force

Complexity: building is O(n) time and O(n) space. Each query is O(1).

Prefix sums work for static data. If the array changes between queries, you must rebuild (O(n)) or use a structure designed for updates, such as the Fenwick tree in Range Queries and Disjoint Set Union.

Problem. Count the contiguous subarrays whose elements sum to k. The numbers may be negative. For [1, 2, 3] and k = 3, the answer is 2 (the subarrays [1, 2] and [3]).

Brute force. For each start, extend the end and keep a running sum: O(n^2).

Why not a sliding window? Because of negative numbers. As we saw in the last article, shrinking a window does not necessarily move the sum in a predictable direction.

Prefix sums. The sum of the subarray a[i..j] is prefix[j + 1] - prefix[i]. We want it to be k, which means prefix[i] = prefix[j + 1] - k. So, as we sweep j from left to right, keeping the current prefix total p, the question becomes: how many earlier prefix totals equal p - k? Each such earlier prefix is the start of a subarray ending here with sum k. A hash map from prefix value to the number of times it has occurred answers that in O(1).

One detail: the "empty prefix" with value 0 (before the first element) must be in the map from the start, with count 1. Otherwise subarrays that begin at position 0 would never be counted.

Dry run for [1, 2, 3], k = 3:

// File: Main.javaimport java.util.HashMap;import java.util.Map;public class Main {    // Brute force: O(n^2).    static int countBrute(int[] a, int k) {        int count = 0;        for (int start = 0; start < a.length; start++) {            long sum = 0;            for (int end = start; end < a.length; end++) {                sum += a[end];                if (sum == k) {                    count++;                }            }        }        return count;    }    // Prefix sums and a hash map: O(n) time, O(n) space, works with negative numbers.    static int countWithMap(int[] a, long k) {        Map<Long, Integer> seen = new HashMap<>();        seen.put(0L, 1);                                   // the empty prefix        long prefix = 0;        int count = 0;        for (int x : a) {            prefix += x;            count += seen.getOrDefault(prefix - k, 0);     // earlier prefixes that make a sum of k            seen.merge(prefix, 1, Integer::sum);        }        return count;    }    public static void main(String[] args) {        int[][] inputs = {{1, 2, 3}, {1, 1, 1}, {3, 4, 7, 2, -3, 1, 4, 2}, {1, -1, 0}, {}};        int[] ks = {3, 2, 7, 0, 5};        for (int t = 0; t < inputs.length; t++) {            System.out.println(countBrute(inputs[t], ks[t]) + " " + countWithMap(inputs[t], ks[t]));        }    }}

2 22 24 43 30 0

The input [1, -1, 0] with k = 0 has three subarrays that sum to zero ([1, -1], [1, -1, 0] and [0]), and it also contains negative numbers, which would have broken a sliding window. The map version handles it in O(n).

The same idea works for products. Problem: for each position, return the product of all the other elements, without using division. For [1, 2, 3, 4] the answer is [24, 12, 8, 6].

The product of everything except a[i] is (product of everything to its left) times (product of everything to its right). Do two passes. Going left to right, keep a running product of the elements before i and store it in result[i]. Going right to left, keep a running product of the elements after i and multiply it into result[i].

We avoid division because the array may contain zeros, which makes division impossible, and because it is a common interview constraint.

// File: Main.javaimport java.util.Arrays;public class Main {    static long[] productExceptSelf(int[] a) {        int n = a.length;        long[] result = new long[n];        long prefix = 1;        for (int i = 0; i < n; i++) {            result[i] = prefix;            // product of everything before i            prefix *= a[i];        }        long suffix = 1;        for (int i = n - 1; i >= 0; i--) {            result[i] *= suffix;           // multiply in the product of everything after i            suffix *= a[i];        }        return result;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(productExceptSelf(new int[] {1, 2, 3, 4})));        System.out.println(Arrays.toString(productExceptSelf(new int[] {1, 0, 3, 4})));        System.out.println(Arrays.toString(productExceptSelf(new int[] {0, 0, 2})));        System.out.println(Arrays.toString(productExceptSelf(new int[] {5})));        System.out.println(Arrays.toString(productExceptSelf(new int[] {})));    }}

[24, 12, 8, 6][0, 12, 0, 0][0, 0, 0][1][]

Time O(n), and extra space O(1) beyond the output array. Products grow fast, so even a long can overflow for long arrays of large numbers. A real problem would state limits that keep the answer in range, and you should ask.

For a grid, let P[r][c] be the sum of the rectangle from the top-left corner (0, 0) to (r - 1, c - 1). Again we use an extra row and column of zeros. Build it with inclusion and exclusion:

P[r + 1][c + 1] = m[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c]

(the cell itself, plus the rectangle above, plus the rectangle to the left, minus the overlap that was counted twice).

The sum of any rectangle with corners (r1, c1) and (r2, c2) is then:

P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

(the big rectangle, minus the strip above it, minus the strip to its left, plus back the corner that was removed twice).

// File: Main.javapublic class Main {    static class NumMatrix {        private final long[][] p;        NumMatrix(int[][] m) {            int rows = m.length;            int cols = rows == 0 ? 0 : m[0].length;            p = new long[rows + 1][cols + 1];            for (int r = 0; r < rows; r++) {                for (int c = 0; c < cols; c++) {                    p[r + 1][c + 1] = m[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c];                }            }        }        long sumRegion(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];        }    }    public static void main(String[] args) {        int[][] grid = {            {3, 0, 1, 4, 2},            {5, 6, 3, 2, 1},            {1, 2, 0, 1, 5},            {4, 1, 0, 1, 7},            {1, 0, 3, 0, 5}        };        NumMatrix nm = new NumMatrix(grid);        System.out.println(nm.sumRegion(2, 1, 4, 3));        System.out.println(nm.sumRegion(1, 1, 2, 2));        System.out.println(nm.sumRegion(1, 2, 2, 4));        System.out.println(nm.sumRegion(0, 0, 4, 4));    }}

8111258

Building takes O(rows × cols), and each query takes O(1). Check the first answer by hand: rows 2 to 4 and columns 1 to 3 hold 2, 0, 1, then 1, 0, 1, then 0, 3, 0, which add up to 8.

Prefix sums turn "many range sums" into cheap queries. A difference array turns "many range updates" into cheap updates.

Problem. You have an array of n zeros. You are given many updates, each saying "add v to every element from position l to position r". After all updates, output the final array.

Brute force. Each update loops over its range: O(n) per update, so O(n × u) for u updates.

Difference array. Instead of tracking the values, track the changes between neighbours: diff[i] = a[i] - a[i - 1]. Now consider the effect of adding v to the range [l, r]:

• the jump into the range at position l grows by v, so diff[l] += v;
• the jump out of the range at position r + 1 shrinks by v, so diff[r + 1] -= v;
• all differences inside the range stay the same.

That is two array writes per update, no matter how long the range. After all updates, one pass of prefix sums over diff rebuilds the real array: a[i] = diff[0] + ... + diff[i]. We make diff one slot longer than a so that r + 1 is always a valid index.

Example. Flight bookings: there are n flights. Each booking [first, last, seats] reserves seats seats on every flight from first to last (flights are numbered from 1). Return the total seats booked on each flight. With n = 5 and bookings [1, 2, 10], [2, 3, 20], [2, 5, 25], the answer is [10, 55, 45, 25, 25].

Convert to 0-based positions and apply the updates:

Now take running totals of diff: 10, 55, 45, 25, 25 (the last slot, -25, is only the sentinel).

// File: Main.javaimport java.util.Arrays;public class Main {    static long[] buildDiff(int[][] bookings, int n) {        long[] diff = new long[n + 1];                 // one extra slot for the "r + 1" write        for (int[] b : bookings) {            int first = b[0] - 1;                      // convert 1-based flight numbers to 0-based            int last = b[1] - 1;            diff[first] += b[2];            diff[last + 1] -= b[2];        }        return diff;    }    static long[] totals(int[][] bookings, int n) {        long[] diff = buildDiff(bookings, n);        long[] answer = new long[n];        long running = 0;        for (int i = 0; i < n; i++) {            running += diff[i];                        // a prefix sum over the differences            answer[i] = running;        }        return answer;    }    public static void main(String[] args) {        int[][] bookings = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};        System.out.println(Arrays.toString(buildDiff(bookings, 5)));        System.out.println(Arrays.toString(totals(bookings, 5)));        System.out.println(Arrays.toString(totals(new int[][] {{1, 2, 10}, {2, 2, 15}}, 2)));        System.out.println(Arrays.toString(totals(new int[][] {}, 3)));    }}

[10, 45, -10, -20, 0, -25][10, 55, 45, 25, 25][10, 25][0, 0, 0]

Complexity: each update is O(1), so u updates cost O(u), plus one O(n) pass to rebuild. The total is O(n + u) instead of O(n × u). Prefix sums and difference arrays are inverses of each other: a prefix sum turns differences into values, and a difference turns values into differences.

• Index convention confusion. Decide: is prefix[i] the sum of the first i elements (length n + 1, starts with 0), or up to and including i? Use one, and write it in a comment. With our convention the range sum is prefix[right + 1] - prefix[left].
• Forgetting the leading zero in the prefix array, or forgetting to put 0 -> 1 in the hash map for "subarray sum equals k".
• int overflow. Use long for prefix totals and products.
• Querying with left > right or out-of-range positions. Validate, or document the assumption.
• Writing diff[r + 1] without an extra slot. The array must have n + 1 entries.
• 1-based versus 0-based input. Flight numbers, positions and ranges in problem statements are often 1-based. Convert once, at the boundary.
• Using prefix sums when the array changes. They are for static data.
• Assuming a sliding window works for exact sums with negatives. It does not. Use prefix sums and a map.
• Division in product-except-self. It fails for zeros and may overflow. Use prefix and suffix products.

class BuggyPrefix {    private final int[] prefix;    BuggyPrefix(int[] a) {        prefix = new int[a.length];        prefix[0] = a[0];        for (int i = 1; i < a.length; i++) {            prefix[i] = prefix[i - 1] + a[i];        }    }    int sum(int left, int right) {        return prefix[right] - prefix[left];    }}

// File: Main.javapublic class Main {    static int pivotIndex(int[] a) {        long total = 0;        for (int x : a) {            total += x;        }        long leftSum = 0;        for (int i = 0; i < a.length; i++) {            if (leftSum == total - leftSum - a[i]) {                return i;            }            leftSum += a[i];        }        return -1;    }    public static void main(String[] args) {        System.out.println(pivotIndex(new int[] {1, 7, 3, 6, 5, 6}));        System.out.println(pivotIndex(new int[] {1, 2, 3}));        System.out.println(pivotIndex(new int[] {2, 1, -1}));        System.out.println(pivotIndex(new int[] {}));        System.out.println(pivotIndex(new int[] {5}));    }}

3-10-10

// File: Main.javaimport java.util.Arrays;public class Main {    static long[] applyUpdates(int n, int[][] updates) {        long[] diff = new long[n + 1];        for (int[] u : updates) {            diff[u[0]] += u[2];            diff[u[1] + 1] -= u[2];        }        long[] result = new long[n];        long running = 0;        for (int i = 0; i < n; i++) {            running += diff[i];            result[i] = running;        }        return result;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(applyUpdates(5, new int[][] {{1, 3, 2}, {2, 4, 3}, {0, 2, -2}})));        System.out.println(Arrays.toString(applyUpdates(3, new int[][] {{0, 2, 7}})));        System.out.println(Arrays.toString(applyUpdates(0, new int[][] {})));    }}

[-2, 0, 3, 5, 3][7, 7, 7][]

// File: Main.javapublic class Main {    static class BuggyPrefix {        private final int[] prefix;        BuggyPrefix(int[] a) {            prefix = new int[a.length];            prefix[0] = a[0];            for (int i = 1; i < a.length; i++) {                prefix[i] = prefix[i - 1] + a[i];            }        }        int sum(int left, int right) {            return prefix[right] - prefix[left];        }    }    static class FixedPrefix {        private final long[] prefix;        FixedPrefix(int[] a) {            prefix = new long[a.length + 1];            for (int i = 0; i < a.length; i++) {                prefix[i + 1] = prefix[i] + a[i];            }        }        long sum(int left, int right) {            return prefix[right + 1] - prefix[left];        }    }    public static void main(String[] args) {        int[] a = {3, 1, 4, 1, 5};        System.out.println("buggy sum(0, 2) = " + new BuggyPrefix(a).sum(0, 2) + ", fixed = " + new FixedPrefix(a).sum(0, 2));        System.out.println("buggy sum(1, 3) = " + new BuggyPrefix(a).sum(1, 3) + ", fixed = " + new FixedPrefix(a).sum(1, 3));        try {            new BuggyPrefix(new int[] {});        } catch (ArrayIndexOutOfBoundsException e) {            System.out.println("buggy constructor crashes on an empty array");        }    }}

buggy sum(0, 2) = 5, fixed = 8buggy sum(1, 3) = 5, fixed = 6buggy constructor crashes on an empty array

// File: Main.javapublic class Main {    static int subarraysDivByK(int[] a, int k) {        int[] count = new int[k];        count[0] = 1;                                   // the empty prefix has remainder 0        int remainder = 0;        int answer = 0;        for (int x : a) {            remainder = Math.floorMod(remainder + x, k);            answer += count[remainder];            count[remainder]++;        }        return answer;    }    public static void main(String[] args) {        System.out.println(subarraysDivByK(new int[] {4, 5, 0, -2, -3, 1}, 5));        System.out.println(subarraysDivByK(new int[] {5}, 9));        System.out.println(subarraysDivByK(new int[] {5}, 5));        System.out.println(subarraysDivByK(new int[] {-1, 2, 9}, 2));        System.out.println(subarraysDivByK(new int[] {}, 3));    }}

70120

• Next: Greedy Algorithms and Interval Problems deals with ranges again, but asks for the best way to choose or merge them.
• Later: Range Queries and Disjoint Set Union shows what to do when the array changes between queries (Fenwick and segment trees).
• Practice habit: every time you see "sum of a range", "number of subarrays with ...", or "apply updates to ranges", ask whether a prefix sum or a difference array fits before you write a loop.