8.06Beginner / Intermediate7 topics20 min7 interactive animations

Prefix/suffix methods

Prefix and suffix techniques precompute running totals so queries become O(1): prefix sums, equilibrium index, prefix products, product except self, prefix XOR, difference arrays and the Imos method for many range updates.

Learning goals

Answer range sum queries in O(1) after O(n) preprocessing
Compute products without division
Apply many range updates with a difference array
Combine prefix and suffix information

Prerequisites

Subarrays and subsequences

8.06.1

Prefix sums

A prefix-sum array stores p[i] = a[0] + ... + a[i - 1], with p[0] = 0. Then sum(l..r) = p[r + 1] - p[l], in O(1) per query after an O(n) build. Use long when values are large.

Change the array and the query range in the animation.

Java

1long[] p = new long[a.length + 1];
2for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
3long rangeSum = p[r + 1] - p[l];       // sum of a[l..r]

Prefix sums and O(1) range queries

Interactive · edit the input

int[] arr · length 8

-1

-2

01234567

Being comparedIn the query rangeAlready checked

prefix[]

·1

·2

·3

·4

·5

·6

·7

·8

Setup

prefix has n + 1 slots. prefix[0] = 0 is the sum of nothing, which removes every special case for l = 0.

Step 1 / 10

Java

1static int[] buildPrefix(int[] arr) {
2    int[] prefix = new int[arr.length + 1];      // prefix[i] = arr[0] + ... + arr[i-1]
3    for (int i = 0; i < arr.length; i++) {
4        prefix[i + 1] = prefix[i] + arr[i];
5    }
6    return prefix;
7}
8
9static int rangeSum(int[] prefix, int l, int r) {   // sum of arr[l..r]
10    return prefix[r + 1] - prefix[l];
11}

Live state

0 additions

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L2	n=8	prefix has n + 1 slots. prefix[0] = 0 is the sum of nothing, which removes every special case for l = 0.
2	L4	i=0 arr[i]=3 prefix[i+1]=3	prefix[1] = prefix[0] + arr[0] = 0 + 3 = 3.
3	L4	i=1 arr[i]=-1 prefix[i+1]=2	prefix[2] = prefix[1] + arr[1] = 3 + -1 = 2.
4	L4	i=2 arr[i]=4 prefix[i+1]=6	prefix[3] = prefix[2] + arr[2] = 2 + 4 = 6.
5	L4	i=3 arr[i]=1 prefix[i+1]=7	prefix[4] = prefix[3] + arr[3] = 6 + 1 = 7.
6	L4	i=4 arr[i]=5 prefix[i+1]=12	prefix[5] = prefix[4] + arr[4] = 7 + 5 = 12.
7	L4	i=5 arr[i]=9 prefix[i+1]=21	prefix[6] = prefix[5] + arr[5] = 12 + 9 = 21.
8	L4	i=6 arr[i]=-2 prefix[i+1]=19	prefix[7] = prefix[6] + arr[6] = 21 + -2 = 19.
9	L4	i=7 arr[i]=6 prefix[i+1]=25	prefix[8] = prefix[7] + arr[7] = 19 + 6 = 25.
10	L10	l=2 r=5 prefix[r+1]=21 prefix[l]=2 return=19	Sum of arr[2..5] = prefix[6] - prefix[2] = 21 - 2 = 19. Building took O(n) once; every query afterwards is O(1).

8.06.2

Equilibrium index

An equilibrium index has equal sums to its left and to its right (the element itself excluded). Compute the total once, then scan keeping the left sum; the right sum is total - left - a[i]. O(n) time, O(1) space.

The preset without an equilibrium shows the -1 result.

Java

1static int equilibrium(int[] a) {
2    long total = 0;
3    for (int x : a) total += x;
4    long left = 0;
5    for (int i = 0; i < a.length; i++) {
6        if (left == total - left - a[i]) return i;
7        left += a[i];
8    }
9    return -1;
10}

Equilibrium index (left sum = right sum)

Interactive · edit the input

int[] arr · length 6

012345

Candidate pivotEquilibriumLeft of the pivot

Setup

Total = 28. For a pivot i, right = total - left - a[i], so no second pass is needed.

Step 1 / 6

Java

1static int equilibrium(int[] a) {
2    long total = 0;
3    for (int x : a) total += x;
4    long left = 0;
5    for (int i = 0; i < a.length; i++) {
6        long right = total - left - a[i];
7        if (left == right) return i;
8        left += a[i];
9    }
10    return -1;
11}

Live state

total

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L3	total=28	Total = 28. For a pivot i, right = total - left - a[i], so no second pass is needed.
2	L7	i=0 left=0 a[i]=1 right=27	Left 0 vs right 27: not balanced here.
3	L7	i=1 left=1 a[i]=7 right=20	Left 1 vs right 20: not balanced here.
4	L7	i=2 left=8 a[i]=3 right=17	Left 8 vs right 17: not balanced here.
5	L7	i=3 left=11 a[i]=6 right=11	Left 11 equals right 11: index 3 balances the array.
6	L7	return=3	Return 3. One pass after computing the total: O(n) time, O(1) space.

8.06.3

Prefix products

Prefix products work like prefix sums with multiplication: out[i] is the product of everything before index i. Beware of overflow (use long or BigInteger) and of zeros, which make every later prefix zero. Division-based range products fail when a value is zero.

The first pass of the next animation builds exactly this array.

Java

1long[] prefix = new long[a.length + 1];
2prefix[0] = 1;
3for (int i = 0; i < a.length; i++) prefix[i + 1] = prefix[i] * a[i];   // may overflow for large inputs

Product of array except self (prefix, then suffix)

Interactive · edit the input

int[] arr · length 4

0123

Current indexAlready filled

out[]

Setup

Nothing lies to the left of index 0, so its left product is 1. No division is used, so zeros are handled correctly.

Step 1 / 9

Java

1static int[] productExceptSelf(int[] a) {
2    int n = a.length;
3    int[] out = new int[n];
4    out[0] = 1;
5    for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];       // product of everything left of i
6    int right = 1;
7    for (int i = n - 1; i >= 0; i--) {
8        out[i] *= right;                                               // times everything right of i
9        right *= a[i];
10    }
11    return out;
12}

Live state

out[0]

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L4	out[0]=1	Nothing lies to the left of index 0, so its left product is 1. No division is used, so zeros are handled correctly.
2	L5	i=1 out[1]=1	out[1] = out[0] x a[0] = 1 x 1 = 1: the product of everything left of 1.
3	L5	i=2 out[2]=2	out[2] = out[1] x a[1] = 1 x 2 = 2: the product of everything left of 2.
4	L5	i=3 out[3]=6	out[3] = out[2] x a[2] = 2 x 3 = 6: the product of everything left of 3.
5	L8	i=3 right=1 out[3]=6	Multiply out[3] by the product to its right (1): out[3] = 6.
6	L8	i=2 right=4 out[2]=8	Multiply out[2] by the product to its right (4): out[2] = 8.
7	L8	i=1 right=12 out[1]=12	Multiply out[1] by the product to its right (12): out[1] = 12.
8	L8	i=0 right=24 out[0]=24	Multiply out[0] by the product to its right (24): out[0] = 24.
9	L11	return=[24, 12, 8, 6]	Result [24, 12, 8, 6] in two O(n) passes with O(1) extra space beyond the output.

8.06.4

Product except self

For each index, the product of all other elements equals (product of everything left) × (product of everything right). One pass builds the left products into the output; a second pass from the right multiplies in a running right product. O(n) time, no division, so zeros are handled correctly.

Try the one-zero and two-zero presets.

Java

1static int[] productExceptSelf(int[] a) {
2    int n = a.length;
3    int[] out = new int[n];
4    out[0] = 1;
5    for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];
6    int right = 1;
7    for (int i = n - 1; i >= 0; i--) { out[i] *= right; right *= a[i]; }
8    return out;
9}

Product of array except self (prefix, then suffix)

Interactive · edit the input

int[] arr · length 4

0123

Current indexAlready filled

out[]

Setup

Nothing lies to the left of index 0, so its left product is 1. No division is used, so zeros are handled correctly.

Step 1 / 9

Java

1static int[] productExceptSelf(int[] a) {
2    int n = a.length;
3    int[] out = new int[n];
4    out[0] = 1;
5    for (int i = 1; i < n; i++) out[i] = out[i - 1] * a[i - 1];       // product of everything left of i
6    int right = 1;
7    for (int i = n - 1; i >= 0; i--) {
8        out[i] *= right;                                               // times everything right of i
9        right *= a[i];
10    }
11    return out;
12}

Live state

out[0]

No condition evaluated on this step

Execution trace (dry run table)Show 9 steps

Step	Line	State	What happens
1	L4	out[0]=1	Nothing lies to the left of index 0, so its left product is 1. No division is used, so zeros are handled correctly.
2	L5	i=1 out[1]=1	out[1] = out[0] x a[0] = 1 x 1 = 1: the product of everything left of 1.
3	L5	i=2 out[2]=2	out[2] = out[1] x a[1] = 1 x 2 = 2: the product of everything left of 2.
4	L5	i=3 out[3]=6	out[3] = out[2] x a[2] = 2 x 3 = 6: the product of everything left of 3.
5	L8	i=3 right=1 out[3]=6	Multiply out[3] by the product to its right (1): out[3] = 6.
6	L8	i=2 right=4 out[2]=8	Multiply out[2] by the product to its right (4): out[2] = 8.
7	L8	i=1 right=12 out[1]=12	Multiply out[1] by the product to its right (12): out[1] = 12.
8	L8	i=0 right=24 out[0]=24	Multiply out[0] by the product to its right (24): out[0] = 24.
9	L11	return=[24, 12, 8, 6]	Result [24, 12, 8, 6] in two O(n) passes with O(1) extra space beyond the output.

8.06.5

Prefix XOR

XOR is its own inverse (x ^ x = 0), so prefix XOR gives range XOR queries: xor(l..r) = p[r + 1] ^ p[l]. The same idea finds subarrays with XOR zero or a target value using a hash map of prefix values.

Pick a range and watch the equal prefix parts cancel.

Java

1int[] p = new int[a.length + 1];
2for (int i = 0; i < a.length; i++) p[i + 1] = p[i] ^ a[i];
3int rangeXor = p[r + 1] ^ p[l];

Prefix XOR and range XOR queries

Interactive · edit the input

int[] arr · length 6

012345

Queried rangePrefix being built

p[] (p[i] = XOR of the first i values)

Setup

p[0] = 0 is the XOR of nothing. Each next prefix XORs one more value.

Step 1 / 8

Java

1static int[] build(int[] a) {
2    int[] p = new int[a.length + 1];
3    for (int i = 0; i < a.length; i++) p[i + 1] = p[i] ^ a[i];
4    return p;
5}
6static int rangeXor(int[] p, int l, int r) {
7    return p[r + 1] ^ p[l];            // equal prefixes cancel: x ^ x = 0
8}

Live state

p[0]

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	p[0]=0	p[0] = 0 is the XOR of nothing. Each next prefix XORs one more value.
2	L3	i=0 p[1]=5	p[1] = p[0] ^ a[0] = 0 ^ 5 = 5.
3	L3	i=1 p[2]=7	p[2] = p[1] ^ a[1] = 5 ^ 2 = 7.
4	L3	i=2 p[3]=0	p[3] = p[2] ^ a[2] = 7 ^ 7 = 0.
5	L3	i=3 p[4]=1	p[4] = p[3] ^ a[3] = 0 ^ 1 = 1.
6	L3	i=4 p[5]=8	p[5] = p[4] ^ a[4] = 1 ^ 9 = 8.
7	L3	i=5 p[6]=11	p[6] = p[5] ^ a[5] = 8 ^ 3 = 11.
8	L7	l=1 r=4 p[r+1]=8 p[l]=5 return=13	XOR of a[1..4] = p[5] ^ p[1] = 8 ^ 5 = 13. Each query is O(1) after the O(n) build.

8.06.6

Difference array

A difference array stores d[i] = a[i] - a[i - 1]. Adding v to a whole range [l, r] then needs only two updates: d[l] += v and d[r + 1] -= v. After all updates, one prefix-sum pass rebuilds the array. M range updates and one rebuild cost O(M + n) instead of O(M·n).

Enter updates as l, r, v triples in the animation.

Java

1int[] d = new int[n + 1];
2for (int[] u : updates) { d[u[0]] += u[2]; d[u[1] + 1] -= u[2]; }   // u = {l, r, v}
3int run = 0;
4for (int i = 0; i < n; i++) { run += d[i]; a[i] += run; }

Difference array: many range updates

Interactive · edit the input

updates (l,r,v)

1,3,+2

2,5,+3

0,1,-1

diff[]

arr[]

·0

·1

·2

·3

·4

·5

·6

Setup

Instead of touching every index of each range (O(n) per update), record only where each update starts and stops.

Step 1 / 15

Java

1static int[] applyUpdates(int n, int[][] updates) {   // each update adds v to arr[l..r]
2    int[] diff = new int[n + 1];
3    for (int[] u : updates) {
4        diff[u[0]] += u[2];                          // start adding v at l
5        diff[u[1] + 1] -= u[2];                      // stop after r
6    }
7    int[] arr = new int[n];
8    int running = 0;
9    for (int i = 0; i < n; i++) {
10        running += diff[i];
11        arr[i] = running;
12    }
13    return arr;
14}

Live state

0 writes

updates

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L2	n=7 updates=3	Instead of touching every index of each range (O(n) per update), record only where each update starts and stops.
2	L4	l=1 r=3 v=2	diff[1] += 2: from index 1 onward, everything is raised by 2.
3	L5	l=1 r=3 v=2	diff[4] -= 2: cancel the change after index 3. Each update cost O(1).
4	L4	l=2 r=5 v=3	diff[2] += 3: from index 2 onward, everything is raised by 3.
5	L5	l=2 r=5 v=3	diff[6] -= 3: cancel the change after index 5. Each update cost O(1).
6	L4	l=0 r=1 v=-1	diff[0] += -1: from index 0 onward, everything is lowered by 1.
7	L5	l=0 r=1 v=-1	diff[2] -= -1: cancel the change after index 1. Each update cost O(1).
8	L11	i=0 diff[i]=-1 running=-1	running += diff[0] → -1, so arr[0] = -1. A prefix sum of diff rebuilds the array.
9	L11	i=1 diff[i]=2 running=1	running += diff[1] → 1, so arr[1] = 1. A prefix sum of diff rebuilds the array.
10	L11	i=2 diff[i]=4 running=5	running += diff[2] → 5, so arr[2] = 5. A prefix sum of diff rebuilds the array.
11	L11	i=3 diff[i]=0 running=5	running += diff[3] → 5, so arr[3] = 5. A prefix sum of diff rebuilds the array.
12	L11	i=4 diff[i]=-2 running=3	running += diff[4] → 3, so arr[4] = 3. A prefix sum of diff rebuilds the array.
13	L11	i=5 diff[i]=0 running=3	running += diff[5] → 3, so arr[5] = 3. A prefix sum of diff rebuilds the array.
14	L11	i=6 diff[i]=-3 running=0	running += diff[6] → 0, so arr[6] = 0. A prefix sum of diff rebuilds the array.
15	L13	return=[-1, 1, 5, 5, 3, 3, 0]	3 updates applied in O(1) each, plus one O(n) pass: O(n + q) instead of O(n · q).

8.06.7

Imos method

The Imos method (named after a Japanese competitive programmer) is this difference-array trick applied to counting overlaps: mark +1 at each interval start and -1 just after each end, then take a running sum to get how many intervals cover each point. It extends to 2D by marking four corners.

It answers “how many intervals cover point x?” for all x in O(n + M).

Java

1int[] cover = new int[maxCoord + 2];
2for (int[] iv : intervals) { cover[iv[0]]++; cover[iv[1] + 1]--; }   // inclusive [start, end]
3for (int x = 1; x <= maxCoord; x++) cover[x] += cover[x - 1];       // cover[x] = intervals containing x

Difference array: many range updates

Interactive · edit the input

updates (l,r,v)

1,3,+2

2,5,+3

0,1,-1

diff[]

arr[]

·0

·1

·2

·3

·4

·5

·6

Setup

Instead of touching every index of each range (O(n) per update), record only where each update starts and stops.

Step 1 / 15

Java

1static int[] applyUpdates(int n, int[][] updates) {   // each update adds v to arr[l..r]
2    int[] diff = new int[n + 1];
3    for (int[] u : updates) {
4        diff[u[0]] += u[2];                          // start adding v at l
5        diff[u[1] + 1] -= u[2];                      // stop after r
6    }
7    int[] arr = new int[n];
8    int running = 0;
9    for (int i = 0; i < n; i++) {
10        running += diff[i];
11        arr[i] = running;
12    }
13    return arr;
14}

Live state

0 writes

updates

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L2	n=7 updates=3	Instead of touching every index of each range (O(n) per update), record only where each update starts and stops.
2	L4	l=1 r=3 v=2	diff[1] += 2: from index 1 onward, everything is raised by 2.
3	L5	l=1 r=3 v=2	diff[4] -= 2: cancel the change after index 3. Each update cost O(1).
4	L4	l=2 r=5 v=3	diff[2] += 3: from index 2 onward, everything is raised by 3.
5	L5	l=2 r=5 v=3	diff[6] -= 3: cancel the change after index 5. Each update cost O(1).
6	L4	l=0 r=1 v=-1	diff[0] += -1: from index 0 onward, everything is lowered by 1.
7	L5	l=0 r=1 v=-1	diff[2] -= -1: cancel the change after index 1. Each update cost O(1).
8	L11	i=0 diff[i]=-1 running=-1	running += diff[0] → -1, so arr[0] = -1. A prefix sum of diff rebuilds the array.
9	L11	i=1 diff[i]=2 running=1	running += diff[1] → 1, so arr[1] = 1. A prefix sum of diff rebuilds the array.
10	L11	i=2 diff[i]=4 running=5	running += diff[2] → 5, so arr[2] = 5. A prefix sum of diff rebuilds the array.
11	L11	i=3 diff[i]=0 running=5	running += diff[3] → 5, so arr[3] = 5. A prefix sum of diff rebuilds the array.
12	L11	i=4 diff[i]=-2 running=3	running += diff[4] → 3, so arr[4] = 3. A prefix sum of diff rebuilds the array.
13	L11	i=5 diff[i]=0 running=3	running += diff[5] → 3, so arr[5] = 3. A prefix sum of diff rebuilds the array.
14	L11	i=6 diff[i]=-3 running=0	running += diff[6] → 0, so arr[6] = 0. A prefix sum of diff rebuilds the array.
15	L13	return=[-1, 1, 5, 5, 3, 3, 0]	3 updates applied in O(1) each, plus one O(n) pass: O(n + q) instead of O(n · q).

Practice ladder

Now try it yourself

Easy

Build the prefix sums of {2, 4, 6, 8} and answer sum(1..3)
Compute range XOR over {5, 2, 7}

Medium

Product except self of {1, 2, 3, 4} without division
Apply updates (0, 2, +5) and (1, 3, +2) to {0, 0, 0, 0} with a difference array

Advanced

Count the subarrays whose XOR is zero using prefix XOR and a hash map

Key takeaways

Preprocessing with prefix totals turns each range query into O(1).
Product except self = left product × right product, no division.
Difference arrays make range updates O(1) each and rebuild with one pass.