30.05Intermediate / Advanced5 topics16 min5 interactive animations

Range-query transformations

Transform a range-query problem into an easier one: difference arrays, prefix sums, offline sorting, coordinate compression and query reordering with Mo's algorithm.

Learning goals

Apply many range updates with a difference array and read the result with one prefix pass
Answer range sums in O(1) with prefix sums
Answer queries offline by sorting them so a simple structure suffices
Compress coordinates and reorder queries with Mo's algorithm

Prerequisites

Prefix sumsSortingFenwick tree

Many hard-looking range problems become easy once you change the form of the data (differences, prefixes) or the order in which you answer (sorted, blocked). The queries are the same; only the way of asking changes.

30.05.1

Difference arrays

A **difference array** d stores d[i] = a[i] - a[i - 1]. Adding v to every element of a[l..r] changes only two differences: d[l] += v and d[r + 1] -= v. So any number of range additions cost O(1) each, and one prefix-sum pass over d rebuilds the final array in O(n). It is the right tool when all updates come first and the array is read afterwards.

The array d needs one extra cell for r + 1, or a check for r + 1 < n. The existing animation for difference arrays shows the two touched cells per update and the final prefix pass.

Java

1class DifferenceArray {
2    private final long[] d;
3    DifferenceArray(int n) { d = new long[n + 1]; }          // one extra cell for r + 1
4    void rangeAdd(int l, int r, long v) {        // inclusive
5        d[l] += v;
6        d[r + 1] -= v;
7    }
8    long[] result() {                            // the final array: prefix sums of d
9        long[] a = new long[d.length - 1];
10        long run = 0;
11        for (int i = 0; i < a.length; i++) { run += d[i]; a[i] = run; }
12        return a;
13    }
14}

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).

30.05.2

Prefix sums

A **prefix sum** array p with p[i] = a[0] + ... + a[i - 1] answers any range sum in O(1): sum(l..r) = p[r + 1] - p[l]. The extra leading zero makes l = 0 need no special case. Prefix sums are the inverse of difference arrays: one turns a sequence into running totals, the other turns running totals back into steps.

The same idea works for any invertible operation: XOR (p[r + 1] ^ p[l]), counting a value, and even products when no value is zero. Use long for the sums to avoid overflow, as in long[] p = new long[n + 1].

Java

1static long[] prefixSums(int[] a) {
2    long[] p = new long[a.length + 1];          // p[0] = 0: the sum of nothing
3    for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
4    return p;
5}
6static long rangeSum(long[] p, int l, int r) { return p[r + 1] - p[l]; }     // inclusive [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).

30.05.3

Offline sorting

When all queries are known in advance (**offline**), you may answer them in any order. Sorting them lets a simple structure do the work. To count the elements <= x in a[l..r] for many (l, r, x), sort the queries by x and the elements by value; insert elements into a Fenwick tree (as a 1 at their position) in increasing order, and for each query first insert all elements <= x, then read a range count.

The cost is O((n + q) log n) with no complicated structure. The existing animation for distinct values in ranges uses the same idea with a different sort key: queries sorted by right endpoint, and a Fenwick tree that marks the last copy of each value.

Java

1static int[] countAtMostOffline(int[] a, int[][] queries) {      // queries {l, r, x}: how many a[i] <= x with l <= i <= r
2    int n = a.length;
3    Integer[] byValue = new Integer[n];
4    for (int i = 0; i < n; i++) byValue[i] = i;
5    Arrays.sort(byValue, Comparator.comparingInt(i -> a[i]));
6    Integer[] order = new Integer[queries.length];
7    for (int i = 0; i < order.length; i++) order[i] = i;
8    Arrays.sort(order, Comparator.comparingInt(i -> queries[i][2]));      // answer in increasing x
9    int[] bit = new int[n + 1];
10    int[] ans = new int[queries.length];
11    int next = 0;
12    for (int qi : order) {
13        int[] q = queries[qi];
14        while (next < n && a[byValue[next]] <= q[2]) {
15            for (int i = byValue[next] + 1; i <= n; i += i & -i) bit[i]++;     // mark this position
16            next++;
17        }
18        int hi = 0, lo = 0;
19        for (int i = q[1] + 1; i > 0; i -= i & -i) hi += bit[i];
20        for (int i = q[0]; i > 0; i -= i & -i) lo += bit[i];
21        ans[qi] = hi - lo;
22    }
23    return ans;
24}

Distinct values in ranges: sweep by right endpoint + Fenwick tree

Interactive · edit the input

array

marked: latest copy of each value

Fenwick tree bit[1..n]

0bit[1]

0bit[2]

0bit[3]

0bit[4]

0bit[5]

0bit[6]

0bit[7]

answers (by query)

?0-3

?2-5

?1-6

?4-4

Setup

A range [l, r] holds as many distinct values as there are positions in it that are the LAST copy of their value among positions up to r. So sweep r from left to right, keep a 1 only on the latest copy of each value in a Fenwick tree, and answer each query ending at r with a range sum. Queries are answered offline, sorted by r.

Step 1 / 17

Java

1static int[] distinctInRanges(int[] a, int[][] queries) {         // queries[k] = {l, r}
2    int n = a.length; int[] bit = new int[n + 1], ans = new int[queries.length];
3    Integer[] order = new Integer[queries.length]; for (int k = 0; k < order.length; k++) order[k] = k;
4    Arrays.sort(order, Comparator.comparingInt(k -> queries[k][1]));     // offline: answer queries by right endpoint
5    Map<Integer, Integer> last = new HashMap<>(); int q = 0;
6    for (int i = 0; i < n; i++) {
7        Integer prev = last.put(a[i], i);
8        if (prev != null) add(bit, prev, -1);                          // the value's earlier copy no longer counts
9        add(bit, i, +1);                                               // only the latest copy of each value is marked
10        while (q < order.length && queries[order[q]][1] == i) {
11            int[] qr = queries[order[q]];
12            ans[order[q++]] = sum(bit, i) - sum(bit, qr[0] - 1);       // marked positions inside [l, r] = distinct values
13        }
14    }
15    return ans;
16}

Live state

queries

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L4	n=7 queries=4	A range [l, r] holds as many distinct values as there are positions in it that are the LAST copy of their value among positions up to r. So sweep r from left to right, keep a 1 only on the latest copy of each value in a Fenwick tree, and answer each query ending at r with a range sum. Queries are answered offline, sorted by r.
2	L9	i=0 value=1	Mark index 0, the latest copy of 1: add +1 in the Fenwick tree.
3	L9	i=1 value=2	Mark index 1, the latest copy of 2: add +1 in the Fenwick tree.
4	L8	i=2 value=1 earlier copy=0	1 already appeared at index 0: unmark that copy (add −1 there), because only the latest copy counts.
5	L9	i=2 value=1	Mark index 2, the latest copy of 1: add +1 in the Fenwick tree.
6	L9	i=3 value=3	Mark index 3, the latest copy of 3: add +1 in the Fenwick tree.
7	L12	query=[0, 3] prefix(r)=3 prefix(l-1)=0 answer=3	Query [0, 3] ends here: marked positions in it = prefix(3) − prefix(-1) = 3 − 0 = 3 distinct values.
8	L8	i=4 value=2 earlier copy=1	2 already appeared at index 1: unmark that copy (add −1 there), because only the latest copy counts.
9	L9	i=4 value=2	Mark index 4, the latest copy of 2: add +1 in the Fenwick tree.
10	L12	query=[4, 4] prefix(r)=3 prefix(l-1)=2 answer=1	Query [4, 4] ends here: marked positions in it = prefix(4) − prefix(3) = 3 − 2 = 1 distinct values.
11	L8	i=5 value=3 earlier copy=3	3 already appeared at index 3: unmark that copy (add −1 there), because only the latest copy counts.
12	L9	i=5 value=3	Mark index 5, the latest copy of 3: add +1 in the Fenwick tree.
13	L12	query=[2, 5] prefix(r)=3 prefix(l-1)=0 answer=3	Query [2, 5] ends here: marked positions in it = prefix(5) − prefix(1) = 3 − 0 = 3 distinct values.
14	L8	i=6 value=1 earlier copy=2	1 already appeared at index 2: unmark that copy (add −1 there), because only the latest copy counts.
15	L9	i=6 value=1	Mark index 6, the latest copy of 1: add +1 in the Fenwick tree.
16	L12	query=[1, 6] prefix(r)=3 prefix(l-1)=0 answer=3	Query [1, 6] ends here: marked positions in it = prefix(6) − prefix(0) = 3 − 0 = 3 distinct values.
17	L15	return=[3, 3, 3, 1]	Answers in input order: [3, 3, 3, 1]. O((n + q) log n) overall; a naive scan per query would cost O(n q).

30.05.4

Coordinate compression

**Coordinate compression** replaces each value by its rank among the distinct values, so a structure indexed by value needs only as many cells as there are distinct values, not the size of the value range. Sort the distinct values and find each rank by binary search, or store ranks in a hash map. Order is preserved, so comparisons still work, but distances are lost.

Use it before a Fenwick tree or an array of counts when values reach 10^9 but there are only 10^5 of them. For ranges given as pairs of endpoints, compress all endpoints together (and often r + 1 as well) so that the compressed segments still cover the same elements. The existing animation shows the sorted unique values and the new rank of each.

Java

1static int[] compress(int[] a) {                 // rank among the distinct values, starting at 0
2    int[] sorted = Arrays.stream(a).distinct().sorted().toArray();
3    int[] rank = new int[a.length];
4    for (int i = 0; i < a.length; i++) rank[i] = Arrays.binarySearch(sorted, a[i]);
5    return rank;
6}

Coordinate compression: ranks and the inverse mapping

Interactive · edit the input

int[] arr · length 6

100

5000000

100

999999

-20

012345

Value being rankedIts rank slot

sorted distinct values (inverse mapping)

-20rank 0

7rank 1

100rank 2

999999rank 3

5000000rank 4

ranks of the input

?idx 0

?idx 1

?idx 2

?idx 3

?idx 4

?idx 5

Setup

6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.

Step 1 / 8

Java

1static int[] denseRank(int[] a) {
2    int[] sorted = Arrays.stream(a).distinct().sorted().toArray();        // sorted[rank] is the inverse mapping
3    int[] rank = new int[a.length];
4    for (int i = 0; i < a.length; i++) rank[i] = Arrays.binarySearch(sorted, a[i]);   // rank = index among the distinct values
5    return rank;
6}
7static int[] ordinalRank(int[] a) {
8    Integer[] idx = new Integer[a.length]; for (int i = 0; i < idx.length; i++) idx[i] = i;
9    Arrays.sort(idx, Comparator.comparingInt(i -> a[i]));                  // stable: equal values keep their input order
10    int[] rank = new int[a.length];
11    for (int r = 0; r < idx.length; r++) rank[idx[r]] = r;                  // the r-th smallest element gets rank r
12    return rank;
13}

Live state

values

distinct

range

-20..5000000

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	values=6 distinct=5 range=-20..5000000	6 values spread over 5000021 possible numbers, but only the relative order matters for many algorithms. Replace each value by its rank (5 distinct ranks 0..4) and use arrays of that small size.
2	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2.
3	L4	value=5000000 rank=4	5000000 is at index 4 among the sorted distinct values (binary search): rank 4.
4	L4	value=7 rank=1	7 is at index 1 among the sorted distinct values (binary search): rank 1.
5	L4	value=100 rank=2	100 is at index 2 among the sorted distinct values (binary search): rank 2. A repeated value reuses its earlier rank.
6	L4	value=999999 rank=3	999999 is at index 3 among the sorted distinct values (binary search): rank 3.
7	L4	value=-20 rank=0	-20 is at index 0 among the sorted distinct values (binary search): rank 0.
8	L5	return=[2, 4, 1, 2, 3, 0]	Ranks [2, 4, 1, 2, 3, 0]. The inverse mapping turns a rank back into the original value in O(1).

30.05.5

Query reordering

**Mo's algorithm** answers many range queries offline by reordering them so that a window [curL, curR] moves as little as possible. Sort queries by the block of their left end (blocks of size about sqrt n), and inside a block by right end. The window then moves O((n + q) sqrt n) steps in total, and each step adds or removes one element in O(1), as long as the answer can be updated incrementally (distinct count, frequencies, sums of squares).

In the preset "Mo order" the five queries 0:4 7:9 2:6 5:9 1:3 on a 10-element array take 19 pointer moves; "Same queries, input order" needs 41. Both give the same answers [3, 3, 3, 4, 3]: only the cost differs. Always expand the window before shrinking it, so the counts never go negative.

Java

1static int[] mo(int[] a, int[][] queries, int maxValue) {        // number of distinct values in each query range
2    int B = Math.max(1, (int) Math.sqrt(a.length));
3    Integer[] order = new Integer[queries.length];
4    for (int i = 0; i < order.length; i++) order[i] = i;
5    Arrays.sort(order, (x, y) -> queries[x][0] / B != queries[y][0] / B
6        ? Integer.compare(queries[x][0] / B, queries[y][0] / B)
7        : Integer.compare(queries[x][1], queries[y][1]));            // block of l, then r ascending
8    int[] cnt = new int[maxValue + 1], ans = new int[queries.length];
9    int curL = 0, curR = -1, distinct = 0;
10    for (int q : order) {
11        int l = queries[q][0], r = queries[q][1];
12        while (curL > l) if (cnt[a[--curL]]++ == 0) distinct++;      // grow left
13        while (curR < r) if (cnt[a[++curR]]++ == 0) distinct++;      // grow right
14        while (curL < l) if (--cnt[a[curL++]] == 0) distinct--;      // shrink left
15        while (curR > r) if (--cnt[a[curR--]] == 0) distinct--;      // shrink right
16        ans[q] = distinct;
17    }
18    return ans;
19}

Query reordering (Mo's algorithm): distinct values in ranges

Interactive · edit the input

a[] (the window is highlighted)

count of each value in the window

0v=1

0v=2

0v=3

0v=4

0v=5

0v=6

0v=7

0v=8

0v=9

Setup

5 querys are answered with one sliding window that moves from one query to the next, updating counts as it grows or shrinks. Sorting by (block of l, then r) with blocks of 3 makes the window travel far less.

Step 1 / 7

Java

1int[] mo(int[] a, int[][] queries) {             // number of distinct values in each query range
2    int B = Math.max(1, (int) Math.sqrt(a.length));
3    Integer[] order = new Integer[queries.length];
4    for (int i = 0; i < order.length; i++) order[i] = i;
5    Arrays.sort(order, (x, y) -> queries[x][0] / B != queries[y][0] / B
6        ? Integer.compare(queries[x][0] / B, queries[y][0] / B)
7        : Integer.compare(queries[x][1], queries[y][1]));         // block of l, then r ascending
8    int[] cnt = new int[maxValue + 1], ans = new int[queries.length];
9    int curL = 0, curR = -1, distinct = 0;
10    for (int q : order) {
11        int l = queries[q][0], r = queries[q][1];
12        while (curL > l) if (cnt[a[--curL]]++ == 0) distinct++;       // grow left
13        while (curR < r) if (cnt[a[++curR]]++ == 0) distinct++;       // grow right
14        while (curL < l) if (--cnt[a[curL++]] == 0) distinct--;       // shrink left
15        while (curR > r) if (--cnt[a[curR--]] == 0) distinct--;       // shrink right
16        ans[q] = distinct;
17    }
18    return ans;
19}

Live state

0 pointer moves

queries

block size

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L2	queries=5 block size=3	5 querys are answered with one sliding window that moves from one query to the next, updating counts as it grows or shrinks. Sorting by (block of l, then r) with blocks of 3 makes the window travel far less.
2	L16	query=1:3 #=5 moves=5 distinct=3	Query 5 = [1, 3]: the window moved 5 steps and holds 3 distinct values.
3	L16	query=0:4 #=1 moves=2 distinct=3	Query 1 = [0, 4]: the window moved 2 steps and holds 3 distinct values.
4	L16	query=2:6 #=3 moves=4 distinct=3	Query 3 = [2, 6]: the window moved 4 steps and holds 3 distinct values.
5	L16	query=5:9 #=4 moves=6 distinct=4	Query 4 = [5, 9]: the window moved 6 steps and holds 4 distinct values.
6	L16	query=7:9 #=2 moves=2 distinct=3	Query 2 = [7, 9]: the window moved 2 steps and holds 3 distinct values.
7	L18	return=[3, 3, 3, 4, 3] pointer moves=19	Answers in input order: [3, 3, 3, 4, 3]. The window made 19 pointer moves; the input order would need 41. In general Mo's order costs O((n + q) × sqrt n) moves.

Practice ladder

Now try it yourself

Easy

Range Addition
Corporate Flight Bookings

Medium

Car Pooling
Count of Smaller Numbers After Self
Range Sum Query 2D - Immutable

Advanced

Count of Range Sum
Range Frequency Queries
Distinct Values Queries (CSES)

Key takeaways

Difference arrays make range adds O(1); prefix sums make range sums O(1): they are inverses.
Offline queries can be sorted so a Fenwick tree or two pointers answers them.
Compress coordinates to ranks; reorder queries into blocks (Mo) so the window moves O((n + q) sqrt n) in total.