30.02Intermediate / Advanced4 topics13 min4 interactive animations

Disjoint sparse table

The disjoint sparse table answers any associative range query in O(1) by storing prefix and suffix values around the middle of every block, with no overlap between the two parts it combines.

Learning goals

Describe the levels of a disjoint sparse table and the values stored in each
Pick the right level for a query from the highest bit of l XOR r
Use the structure for sums, products and XOR, which a sparse table cannot handle
Pad the array to a power of two with the operation's identity

Prerequisites

Sparse tablePrefix sumsBit manipulation

The sparse table fails for sums because its blocks overlap. The disjoint version removes the overlap: any range that crosses the middle of some block is split at that middle into a suffix of the left half and a prefix of the right half, and both are already stored.

30.02.1

Associative queries

The disjoint sparse table works for any **associative** operation: sum, product, XOR, min, GCD, string concatenation, matrix product. It does not need the operation to be idempotent or invertible. It takes O(n log n) time and space to build, like the sparse table, and answers each query with a single combination of two stored values.

The array length must be a power of two, so pad the end with the operation's identity (0 for sum, 1 for product, 0 for XOR). The animation does this for you: the preset "Length not a power of two (padded)" uses 5 values and 3 padding cells.

Java

1class DisjointSparseTable {
2    private final int[][] t;                     // t[j][i]: for the level-j block holding i, op from i towards the middle
3    private final IntBinaryOperator op;
4    DisjointSparseTable(int[] a, int identity, IntBinaryOperator op) {
5        this.op = op;
6        int m = 1;
7        while (m < a.length) m <<= 1;            // pad to a power of two with the identity
8        int[] v = new int[m];
9        Arrays.fill(v, identity);
10        System.arraycopy(a, 0, v, 0, a.length);
11        int H = Integer.numberOfTrailingZeros(m);
12        t = new int[H + 1][];
13        t[0] = v;
14        for (int j = 1; j <= H; j++) {
15            t[j] = new int[m];
16            int half = 1 << (j - 1);
17            for (int start = 0; start < m; start += 2 * half) {
18                int mid = start + half;
19                t[j][mid - 1] = v[mid - 1];
20                for (int i = mid - 2; i >= start; i--) t[j][i] = op.applyAsInt(v[i], t[j][i + 1]);         // towards the middle
21                t[j][mid] = v[mid];
22                for (int i = mid + 1; i < start + 2 * half; i++) t[j][i] = op.applyAsInt(t[j][i - 1], v[i]);   // away from it
23            }
24        }
25    }
26    int query(int l, int r) {                    // inclusive, 0-based
27        if (l == r) return t[0][l];
28        int j = 32 - Integer.numberOfLeadingZeros(l ^ r);
29        return op.applyAsInt(t[j][l], t[j][r]);
30    }
31}

Disjoint sparse table: O(1) queries for any associative operation

Interactive · edit the input

level 0: the values

Setup

n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).

Step 1 / 6

Java

1int[][] t;                                       // t[j][i]: in the level-j block holding i, the op from i towards the block's middle
2void build(int[] a) {                            // n is a power of two (pad with the identity)
3    int n = a.length, H = Integer.numberOfTrailingZeros(n);
4    t = new int[H + 1][n];
5    t[0] = a.clone();
6    for (int j = 1; j <= H; j++) {
7        int half = 1 << (j - 1);
8        for (int start = 0; start < n; start += 2 * half) {
9            int mid = start + half;
10            t[j][mid - 1] = a[mid - 1];
11            for (int i = mid - 2; i >= start; i--) t[j][i] = a[i] + t[j][i + 1];       // suffix sums towards the middle
12            t[j][mid] = a[mid];
13            for (int i = mid + 1; i < start + 2 * half; i++) t[j][i] = t[j][i - 1] + a[i];   // prefix sums away from it
14        }
15    }
16}
17int query(int l, int r) {
18    if (l == r) return t[0][l];
19    int j = 32 - Integer.numberOfLeadingZeros(l ^ r);       // the level where l and r are in different halves of one block
20    return t[j][l] + t[j][r];
21}

Live state

0 cells computed

size

levels

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L5	n=8 size=8 levels=3	n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).
2	L13	level=1 block size=2	Level 1: in each block of 2, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
3	L13	level=2 block size=4	Level 2: in each block of 4, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
4	L13	level=3 block size=8	Level 3: in each block of 8, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
5	L19	l=1 r=5 l ^ r=4 level=3	l ^ r = 1 ^ 5 = 4, whose highest set bit is 2, so level 3: l and r lie in the same block of 8 but in different halves, which means the middle of that block is between them.
6	L20	t[j][l]=6 t[j][r]=7 return=13	t[3][1] + t[3][5] = 6 + 7 = 13. Two reads and no overlap, so it works for operations that are not idempotent, such as sum and product.

30.02.2

Prefix/suffix per block

At level j the array is cut into blocks of 2^j and each block into two halves. In the left half, cell i stores the combination of a[i..mid-1], a **suffix** of the left half that ends at the middle. In the right half, cell i stores the combination of a[mid..i], a **prefix** of the right half that starts at the middle. Blocks of one level do not overlap, hence the name 'disjoint'.

In the animation each level is drawn as its own row, with the left halves in one colour and the right halves in another. For the default input 3 1 4 1 5 2 3 2, level 2 is 4 1 4 5 | 7 2 3 5: in the first block of four, cells 0 and 1 hold 3 + 1 = 4 and 1 (sums that end at the middle), and cells 2 and 3 hold 4 and 4 + 1 = 5 (sums that start at it).

Java

1static int[] level(int[] a, int j) {             // the level-j row for sums; a.length is a power of two
2    int n = a.length, half = 1 << (j - 1);
3    int[] row = new int[n];
4    for (int start = 0; start < n; start += 2 * half) {
5        int mid = start + half;
6        row[mid - 1] = a[mid - 1];
7        for (int i = mid - 2; i >= start; i--) row[i] = a[i] + row[i + 1];        // suffix sums towards the middle
8        row[mid] = a[mid];
9        for (int i = mid + 1; i < start + 2 * half; i++) row[i] = row[i - 1] + a[i];   // prefix sums away from it
10    }
11    return row;
12}

Disjoint sparse table: O(1) queries for any associative operation

Interactive · edit the input

level 0: the values

Setup

n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).

Step 1 / 6

Java

1int[][] t;                                       // t[j][i]: in the level-j block holding i, the op from i towards the block's middle
2void build(int[] a) {                            // n is a power of two (pad with the identity)
3    int n = a.length, H = Integer.numberOfTrailingZeros(n);
4    t = new int[H + 1][n];
5    t[0] = a.clone();
6    for (int j = 1; j <= H; j++) {
7        int half = 1 << (j - 1);
8        for (int start = 0; start < n; start += 2 * half) {
9            int mid = start + half;
10            t[j][mid - 1] = a[mid - 1];
11            for (int i = mid - 2; i >= start; i--) t[j][i] = a[i] + t[j][i + 1];       // suffix sums towards the middle
12            t[j][mid] = a[mid];
13            for (int i = mid + 1; i < start + 2 * half; i++) t[j][i] = t[j][i - 1] + a[i];   // prefix sums away from it
14        }
15    }
16}
17int query(int l, int r) {
18    if (l == r) return t[0][l];
19    int j = 32 - Integer.numberOfLeadingZeros(l ^ r);       // the level where l and r are in different halves of one block
20    return t[j][l] + t[j][r];
21}

Live state

0 cells computed

size

levels

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L5	n=8 size=8 levels=3	n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).
2	L13	level=1 block size=2	Level 1: in each block of 2, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
3	L13	level=2 block size=4	Level 2: in each block of 4, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
4	L13	level=3 block size=8	Level 3: in each block of 8, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
5	L19	l=1 r=5 l ^ r=4 level=3	l ^ r = 1 ^ 5 = 4, whose highest set bit is 2, so level 3: l and r lie in the same block of 8 but in different halves, which means the middle of that block is between them.
6	L20	t[j][l]=6 t[j][r]=7 return=13	t[3][1] + t[3][5] = 6 + 7 = 13. Two reads and no overlap, so it works for operations that are not idempotent, such as sum and product.

30.02.3

Static range sums/products

For sums you could use ordinary prefix sums, but for products a prefix array fails when a value is zero (division is impossible) and when the modulus is not prime. The disjoint sparse table needs no division at all, so it answers modular products in O(1) even with zeros and non-prime moduli, after an O(n log n) build.

Use long and reduce modulo after every multiplication. The preset "Range product" multiplies positions 2 to 6 of 2 1 3 2 1 2 3 1 and gets 36, reading two stored values: 6 and 6.

Java

1class ModProduct {
2    private static final long MOD = 1_000_000_007L;
3    private final long[][] t;
4    ModProduct(int[] a) {
5        int m = 1;
6        while (m < a.length) m <<= 1;
7        long[] v = new long[m];
8        Arrays.fill(v, 1);                       // the identity of the product
9        for (int i = 0; i < a.length; i++) v[i] = a[i] % MOD;
10        int H = Integer.numberOfTrailingZeros(m);
11        t = new long[H + 1][];
12        t[0] = v;
13        for (int j = 1; j <= H; j++) {
14            t[j] = new long[m];
15            int half = 1 << (j - 1);
16            for (int start = 0; start < m; start += 2 * half) {
17                int mid = start + half;
18                t[j][mid - 1] = v[mid - 1];
19                for (int i = mid - 2; i >= start; i--) t[j][i] = v[i] * t[j][i + 1] % MOD;
20                t[j][mid] = v[mid];
21                for (int i = mid + 1; i < start + 2 * half; i++) t[j][i] = t[j][i - 1] * v[i] % MOD;
22            }
23        }
24    }
25    long query(int l, int r) {
26        if (l == r) return t[0][l];
27        int j = 32 - Integer.numberOfLeadingZeros(l ^ r);
28        return t[j][l] * t[j][r] % MOD;
29    }
30}

Disjoint sparse table: O(1) queries for any associative operation

Interactive · edit the input

level 0: the values

Setup

n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).

Step 1 / 6

Java

1int[][] t;                                       // t[j][i]: in the level-j block holding i, the op from i towards the block's middle
2void build(int[] a) {                            // n is a power of two (pad with the identity)
3    int n = a.length, H = Integer.numberOfTrailingZeros(n);
4    t = new int[H + 1][n];
5    t[0] = a.clone();
6    for (int j = 1; j <= H; j++) {
7        int half = 1 << (j - 1);
8        for (int start = 0; start < n; start += 2 * half) {
9            int mid = start + half;
10            t[j][mid - 1] = a[mid - 1];
11            for (int i = mid - 2; i >= start; i--) t[j][i] = a[i] + t[j][i + 1];       // suffix sums towards the middle
12            t[j][mid] = a[mid];
13            for (int i = mid + 1; i < start + 2 * half; i++) t[j][i] = t[j][i - 1] + a[i];   // prefix sums away from it
14        }
15    }
16}
17int query(int l, int r) {
18    if (l == r) return t[0][l];
19    int j = 32 - Integer.numberOfLeadingZeros(l ^ r);       // the level where l and r are in different halves of one block
20    return t[j][l] + t[j][r];
21}

Live state

0 cells computed

size

levels

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L5	n=8 size=8 levels=3	n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).
2	L13	level=1 block size=2	Level 1: in each block of 2, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
3	L13	level=2 block size=4	Level 2: in each block of 4, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
4	L13	level=3 block size=8	Level 3: in each block of 8, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
5	L19	l=1 r=5 l ^ r=4 level=3	l ^ r = 1 ^ 5 = 4, whose highest set bit is 2, so level 3: l and r lie in the same block of 8 but in different halves, which means the middle of that block is between them.
6	L20	t[j][l]=6 t[j][r]=7 return=13	t[3][1] + t[3][5] = 6 + 7 = 13. Two reads and no overlap, so it works for operations that are not idempotent, such as sum and product.

30.02.4

O(1) queries

To answer [l, r] with l < r, find the level whose block has l in its left half and r in its right half. That is the level given by the highest set bit of l ^ r: the positions agree above that bit and differ at it, so they fall in the same block of size 2^j but in different halves. With j = 32 - Integer.numberOfLeadingZeros(l ^ r), the answer is t[j][l] combined with t[j][r].

In the preset "Range sum" the query [1, 5] has 1 ^ 5 = 4, whose highest bit is bit 2, so level 3: the animation combines t[3][1] = 6 and t[3][5] = 7 to get 13. When l == r the answer is the single value, which is level 0. Everything is two array reads and one operation: O(1).

l	r	l ^ r	level j	block of size 2^j	left half \| right half
1	5	100	3	[0, 7]	[0, 3] \| [4, 7]
0	1	001	1	[0, 1]	[0] \| [1]
2	3	001	1	[2, 3]	[2] \| [3]
3	4	111	3	[0, 7]	[0, 3] \| [4, 7]

Java

1static int levelOf(int l, int r) {               // the level used for l < r; level j holds blocks of size 2^j
2    return 32 - Integer.numberOfLeadingZeros(l ^ r);
3}
4static int blockStart(int l, int r) {            // where that block starts
5    int j = levelOf(l, r);
6    return l >> j << j;
7}

Disjoint sparse table: O(1) queries for any associative operation

Interactive · edit the input

level 0: the values

Setup

n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).

Step 1 / 6

Java

1int[][] t;                                       // t[j][i]: in the level-j block holding i, the op from i towards the block's middle
2void build(int[] a) {                            // n is a power of two (pad with the identity)
3    int n = a.length, H = Integer.numberOfTrailingZeros(n);
4    t = new int[H + 1][n];
5    t[0] = a.clone();
6    for (int j = 1; j <= H; j++) {
7        int half = 1 << (j - 1);
8        for (int start = 0; start < n; start += 2 * half) {
9            int mid = start + half;
10            t[j][mid - 1] = a[mid - 1];
11            for (int i = mid - 2; i >= start; i--) t[j][i] = a[i] + t[j][i + 1];       // suffix sums towards the middle
12            t[j][mid] = a[mid];
13            for (int i = mid + 1; i < start + 2 * half; i++) t[j][i] = t[j][i - 1] + a[i];   // prefix sums away from it
14        }
15    }
16}
17int query(int l, int r) {
18    if (l == r) return t[0][l];
19    int j = 32 - Integer.numberOfLeadingZeros(l ^ r);       // the level where l and r are in different halves of one block
20    return t[j][l] + t[j][r];
21}

Live state

0 cells computed

size

levels

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L5	n=8 size=8 levels=3	n = 8 is a power of two. Level j splits the array into blocks of 2^j; in every block each cell stores the sum from itself to the block's middle (left half) or from the middle to itself (right half).
2	L13	level=1 block size=2	Level 1: in each block of 2, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
3	L13	level=2 block size=4	Level 2: in each block of 4, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
4	L13	level=3 block size=8	Level 3: in each block of 8, the left half stores running values towards the middle and the right half stores running values away from it. No block overlaps another, hence 'disjoint'.
5	L19	l=1 r=5 l ^ r=4 level=3	l ^ r = 1 ^ 5 = 4, whose highest set bit is 2, so level 3: l and r lie in the same block of 8 but in different halves, which means the middle of that block is between them.
6	L20	t[j][l]=6 t[j][r]=7 return=13	t[3][1] + t[3][5] = 6 + 7 = 13. Two reads and no overlap, so it works for operations that are not idempotent, such as sum and product.

Practice ladder

Now try it yourself

Easy

Range Sum Query - Immutable

Medium

Product of the Last K Numbers
Range Product Queries of Powers

Advanced

Static Range Sum Queries (CSES)
Range Product Queries of Powers

Key takeaways

Each level splits blocks into halves and stores suffix values left of the middle and prefix values right of it.
A query uses the level given by the highest bit of l XOR r: two reads, no overlap.
It works for any associative operation, including sums, products and XOR, at O(n log n) memory.