PK

PKBytes

Explore tracks
Chapter 30: Static Range Queries and Decomposition Techniques
30.03Intermediate / Advanced5 topics14 min5 interactive animations

Square-root decomposition

Square root decomposition cuts an array into blocks of about sqrt(n) and keeps one summary per block, giving simple O(sqrt n) queries and updates for problems that are awkward for trees.

Learning goals

  • Build block sums and choose the block size
  • Update a point and answer a range query by combining whole blocks and partial blocks
  • Make range updates cheap with lazy block tags
  • Weigh rebuilding against incremental updates

Prerequisites

ArraysPrefix sumsFenwick and segment trees

Cut a book into chapters. To count words from page 40 to page 260, add the stored totals of the whole chapters and count the few pages at the two ends by hand. The best chapter length balances the number of chapters against the pages per chapter: about the square root of the page count.

30.03.1

Block sums

Split n elements into blocks of size B, so block b covers indices b × B to (b + 1) × B - 1 (the last may be shorter), and store the sum of each block. There are about n / B blocks. A range query costs at most 2B single elements at the two ends plus n / B block sums, which is smallest when 2B ≈ n / B, that is B ≈ sqrt(n / 2); in practice B = sqrt(n) is used.

In the animation's default input, 12 values give B = ceil(sqrt 12) = 4 and 3 blocks. Each block is drawn as a row with its sum. The code below also shows how to find the best block size by direct search of the cost 2B + n / B.

Java
1class SqrtBlocks {
2    final int B;
3    final int[] a, sum;
4    SqrtBlocks(int[] values) {
5        a = values.clone();
6        int n = a.length;
7        B = (int) Math.ceil(Math.sqrt(n));
8        sum = new int[(n + B - 1) / B];
9        for (int i = 0; i < n; i++) sum[i / B] += a[i];         // block of index i is i / B
10    }
11    static int bestBlockSize(int n) {            // minimises 2B + ceil(n / B), the cost of a worst-case query
12        int best = 1;
13        for (int b = 1; b <= n; b++)
14            if (2 * b + (n + b - 1) / b < 2 * best + (n + best - 1) / best) best = b;
15        return best;
16    }
17}

Square root decomposition: block sums, updates and lazy block tags

Interactive · edit the input

Your input

Try

block 0: sum = 21

40
71
12
93

block 1: sum = 19

34
85
26
67

block 2: sum = 15

58
09
710
311
Setup

12 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.

Step 1 / 7
Java
1int B; int[] a, sum, lazy;                       // block b covers a[b*B .. min(n, (b+1)*B) - 1]
2void build(int[] values) {
3    a = values; int n = a.length; B = (int) Math.ceil(Math.sqrt(n));
4    sum = new int[(n + B - 1) / B]; lazy = new int[sum.length];
5    for (int i = 0; i < n; i++) sum[i / B] += a[i];
6}
7void update(int i, int v) {                      // point update: O(1)
8    int cur = a[i] + lazy[i / B];
9    sum[i / B] += v - cur; a[i] = v - lazy[i / B];
10}
11int query(int l, int r) {                        // inclusive
12    int total = 0;
13    for (int i = l; i <= r; ) {
14        if (i % B == 0 && i + B - 1 <= r) { total += sum[i / B]; i += B; }      // a whole block: one step
15        else { total += a[i] + lazy[i / B]; i++; }                              // a partial block: element by element
16    }
17    return total;
18}
19void rangeAdd(int l, int r, int v) {
20    for (int i = l; i <= r; ) {
21        int b = i / B;
22        if (i % B == 0 && i + B - 1 <= r && (b + 1) * B <= a.length) { lazy[b] += v; sum[b] += v * B; i += B; }   // whole block: a tag
23        else { a[i] += v; sum[b] += v; i++; }                                   // partial block: touch the element
24    }
25}

Live state

0 elements touched0 blocks used

n

12

block size B

4

blocks

3

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L3n=12 block size B=4 blocks=312 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.
2L15i=2 value=1 total=1sum[2..9]: index 2 is in a partial block: add the element 1 (total 1).
3L15i=3 value=9 total=10sum[2..9]: index 3 is in a partial block: add the element 9 (total 10).
4L14i=4 block=1 total=29sum[2..9]: block 1 lies fully inside [2, 9]: add its stored sum 19 in one step (total 29).
5L15i=8 value=5 total=34sum[2..9]: index 8 is in a partial block: add the element 5 (total 34).
6L15i=9 value=0 total=34sum[2..9]: index 9 is in a partial block: add the element 0 (total 34).
7L17return=34 elements touched=4 blocks used=1Sum = 34, from 1 whole block and 4 single elements. A plain loop would have read 8.
30.03.2

Point update

A point update changes one element and the sum of its block: sum[i / B] += newValue - a[i]; a[i] = newValue. It costs O(1), which is cheaper than the O(log n) of a segment tree. This makes the structure attractive when updates are far more frequent than queries.

Choose "Point update" in the animation (a[5] becomes 20): the value changes from 8 to 20, so block 1's sum moves by 12, from 19 to 31. Only one element and one block sum are touched.

Java
1class SqrtBlocks {
2    final int B;
3    final int[] a, sum;
4    SqrtBlocks(int[] values) {
5        a = values.clone();
6        int n = a.length;
7        B = (int) Math.ceil(Math.sqrt(n));
8        sum = new int[(n + B - 1) / B];
9        for (int i = 0; i < n; i++) sum[i / B] += a[i];
10    }
11    void update(int i, int v) {                  // O(1)
12        sum[i / B] += v - a[i];
13        a[i] = v;
14    }
15}

Square root decomposition: block sums, updates and lazy block tags

Interactive · edit the input

Your input

Try

block 0: sum = 21

40
71
12
93

block 1: sum = 19

34
85
26
67

block 2: sum = 15

58
09
710
311
Setup

12 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.

Step 1 / 7
Java
1int B; int[] a, sum, lazy;                       // block b covers a[b*B .. min(n, (b+1)*B) - 1]
2void build(int[] values) {
3    a = values; int n = a.length; B = (int) Math.ceil(Math.sqrt(n));
4    sum = new int[(n + B - 1) / B]; lazy = new int[sum.length];
5    for (int i = 0; i < n; i++) sum[i / B] += a[i];
6}
7void update(int i, int v) {                      // point update: O(1)
8    int cur = a[i] + lazy[i / B];
9    sum[i / B] += v - cur; a[i] = v - lazy[i / B];
10}
11int query(int l, int r) {                        // inclusive
12    int total = 0;
13    for (int i = l; i <= r; ) {
14        if (i % B == 0 && i + B - 1 <= r) { total += sum[i / B]; i += B; }      // a whole block: one step
15        else { total += a[i] + lazy[i / B]; i++; }                              // a partial block: element by element
16    }
17    return total;
18}
19void rangeAdd(int l, int r, int v) {
20    for (int i = l; i <= r; ) {
21        int b = i / B;
22        if (i % B == 0 && i + B - 1 <= r && (b + 1) * B <= a.length) { lazy[b] += v; sum[b] += v * B; i += B; }   // whole block: a tag
23        else { a[i] += v; sum[b] += v; i++; }                                   // partial block: touch the element
24    }
25}

Live state

0 elements touched0 blocks used

n

12

block size B

4

blocks

3

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L3n=12 block size B=4 blocks=312 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.
2L15i=2 value=1 total=1sum[2..9]: index 2 is in a partial block: add the element 1 (total 1).
3L15i=3 value=9 total=10sum[2..9]: index 3 is in a partial block: add the element 9 (total 10).
4L14i=4 block=1 total=29sum[2..9]: block 1 lies fully inside [2, 9]: add its stored sum 19 in one step (total 29).
5L15i=8 value=5 total=34sum[2..9]: index 8 is in a partial block: add the element 5 (total 34).
6L15i=9 value=0 total=34sum[2..9]: index 9 is in a partial block: add the element 0 (total 34).
7L17return=34 elements touched=4 blocks used=1Sum = 34, from 1 whole block and 4 single elements. A plain loop would have read 8.
30.03.3

Range query

A query walks from l to r: whenever the current index starts a block that fits inside the range, add the stored block sum and jump B positions; otherwise add a single element and move one step. At most 2(B - 1) single elements are read (the partial blocks at the two ends) plus at most n / B whole blocks.

In the preset "Range sum across blocks" the query [2, 9] on 12 values reads 4 single elements, uses 1 whole block (block 1, indices 4 to 7) and returns 34, where a plain loop would read 8 values. In "Range inside one block" the query [4, 5] uses no whole block at all: it falls inside one block and reads 2 elements.

Java
1class SqrtBlocks {
2    final int B;
3    final int[] a, sum;
4    SqrtBlocks(int[] values) {
5        a = values.clone();
6        int n = a.length;
7        B = (int) Math.ceil(Math.sqrt(n));
8        sum = new int[(n + B - 1) / B];
9        for (int i = 0; i < n; i++) sum[i / B] += a[i];
10    }
11    long query(int l, int r) {                   // inclusive
12        long total = 0;
13        for (int i = l; i <= r; ) {
14            if (i % B == 0 && i + B - 1 <= r) { total += sum[i / B]; i += B; }   // a whole block: one step
15            else { total += a[i]; i++; }                                          // a partial block: element by element
16        }
17        return total;
18    }
19}

Square root decomposition: block sums, updates and lazy block tags

Interactive · edit the input

Your input

Try

block 0: sum = 21

40
71
12
93

block 1: sum = 19

34
85
26
67

block 2: sum = 15

58
09
710
311
Setup

12 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.

Step 1 / 7
Java
1int B; int[] a, sum, lazy;                       // block b covers a[b*B .. min(n, (b+1)*B) - 1]
2void build(int[] values) {
3    a = values; int n = a.length; B = (int) Math.ceil(Math.sqrt(n));
4    sum = new int[(n + B - 1) / B]; lazy = new int[sum.length];
5    for (int i = 0; i < n; i++) sum[i / B] += a[i];
6}
7void update(int i, int v) {                      // point update: O(1)
8    int cur = a[i] + lazy[i / B];
9    sum[i / B] += v - cur; a[i] = v - lazy[i / B];
10}
11int query(int l, int r) {                        // inclusive
12    int total = 0;
13    for (int i = l; i <= r; ) {
14        if (i % B == 0 && i + B - 1 <= r) { total += sum[i / B]; i += B; }      // a whole block: one step
15        else { total += a[i] + lazy[i / B]; i++; }                              // a partial block: element by element
16    }
17    return total;
18}
19void rangeAdd(int l, int r, int v) {
20    for (int i = l; i <= r; ) {
21        int b = i / B;
22        if (i % B == 0 && i + B - 1 <= r && (b + 1) * B <= a.length) { lazy[b] += v; sum[b] += v * B; i += B; }   // whole block: a tag
23        else { a[i] += v; sum[b] += v; i++; }                                   // partial block: touch the element
24    }
25}

Live state

0 elements touched0 blocks used

n

12

block size B

4

blocks

3

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L3n=12 block size B=4 blocks=312 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.
2L15i=2 value=1 total=1sum[2..9]: index 2 is in a partial block: add the element 1 (total 1).
3L15i=3 value=9 total=10sum[2..9]: index 3 is in a partial block: add the element 9 (total 10).
4L14i=4 block=1 total=29sum[2..9]: block 1 lies fully inside [2, 9]: add its stored sum 19 in one step (total 29).
5L15i=8 value=5 total=34sum[2..9]: index 8 is in a partial block: add the element 5 (total 34).
6L15i=9 value=0 total=34sum[2..9]: index 9 is in a partial block: add the element 0 (total 34).
7L17return=34 elements touched=4 blocks used=1Sum = 34, from 1 whole block and 4 single elements. A plain loop would have read 8.
30.03.4

Lazy block updates

To add v to every element of a range, a plain loop costs O(length). With a lazy tag per block, a block fully inside the range gets lazy[b] += v and sum[b] += v × B in O(1), and only the two partial blocks are updated element by element. A range add then costs O(B + n / B) = O(sqrt n), whatever the length of the range.

Readers must add the tag: the true value of element i is a[i] + lazy[i / B]. Try the preset "Lazy block tags" (+2:9:3 ?0:11): the add leaves a tag on the fully covered block and touches the other elements one by one, and the following query still returns the right total, because block sums were adjusted when the tag was added.

Java
1class LazyBlocks {
2    final int B, n;
3    final int[] a, lazy;
4    final long[] sum;
5    LazyBlocks(int[] values) {
6        a = values.clone();
7        n = a.length;
8        B = (int) Math.ceil(Math.sqrt(n));
9        sum = new long[(n + B - 1) / B];
10        lazy = new int[sum.length];
11        for (int i = 0; i < n; i++) sum[i / B] += a[i];
12    }
13    private int len(int b) { return Math.min(n, (b + 1) * B) - b * B; }
14    void rangeAdd(int l, int r, int v) {
15        for (int i = l; i <= r; ) {
16            int b = i / B;
17            if (i % B == 0 && i + len(b) - 1 <= r) { lazy[b] += v; sum[b] += (long) v * len(b); i += len(b); }   // whole block: a tag
18            else { a[i] += v; sum[b] += v; i++; }                                                              // partial: touch the element
19        }
20    }
21    long query(int l, int r) {
22        long total = 0;
23        for (int i = l; i <= r; ) {
24            int b = i / B;
25            if (i % B == 0 && i + len(b) - 1 <= r) { total += sum[b]; i += len(b); }
26            else { total += a[i] + lazy[b]; i++; }                              // the tag belongs to the element too
27        }
28        return total;
29    }
30}

Square root decomposition: block sums, updates and lazy block tags

Interactive · edit the input

Your input

Try

block 0: sum = 21

40
71
12
93

block 1: sum = 19

34
85
26
67

block 2: sum = 15

58
09
710
311
Setup

12 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.

Step 1 / 7
Java
1int B; int[] a, sum, lazy;                       // block b covers a[b*B .. min(n, (b+1)*B) - 1]
2void build(int[] values) {
3    a = values; int n = a.length; B = (int) Math.ceil(Math.sqrt(n));
4    sum = new int[(n + B - 1) / B]; lazy = new int[sum.length];
5    for (int i = 0; i < n; i++) sum[i / B] += a[i];
6}
7void update(int i, int v) {                      // point update: O(1)
8    int cur = a[i] + lazy[i / B];
9    sum[i / B] += v - cur; a[i] = v - lazy[i / B];
10}
11int query(int l, int r) {                        // inclusive
12    int total = 0;
13    for (int i = l; i <= r; ) {
14        if (i % B == 0 && i + B - 1 <= r) { total += sum[i / B]; i += B; }      // a whole block: one step
15        else { total += a[i] + lazy[i / B]; i++; }                              // a partial block: element by element
16    }
17    return total;
18}
19void rangeAdd(int l, int r, int v) {
20    for (int i = l; i <= r; ) {
21        int b = i / B;
22        if (i % B == 0 && i + B - 1 <= r && (b + 1) * B <= a.length) { lazy[b] += v; sum[b] += v * B; i += B; }   // whole block: a tag
23        else { a[i] += v; sum[b] += v; i++; }                                   // partial block: touch the element
24    }
25}

Live state

0 elements touched0 blocks used

n

12

block size B

4

blocks

3

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L3n=12 block size B=4 blocks=312 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.
2L15i=2 value=1 total=1sum[2..9]: index 2 is in a partial block: add the element 1 (total 1).
3L15i=3 value=9 total=10sum[2..9]: index 3 is in a partial block: add the element 9 (total 10).
4L14i=4 block=1 total=29sum[2..9]: block 1 lies fully inside [2, 9]: add its stored sum 19 in one step (total 29).
5L15i=8 value=5 total=34sum[2..9]: index 8 is in a partial block: add the element 5 (total 34).
6L15i=9 value=0 total=34sum[2..9]: index 9 is in a partial block: add the element 0 (total 34).
7L17return=34 elements touched=4 blocks used=1Sum = 34, from 1 whole block and 4 single elements. A plain loop would have read 8.
30.03.5

Rebuild trade-offs

Another way to trade updates against queries is to rebuild. Keep a prefix-sum array for fast static queries and a small list of pending changes. A query adds the pending changes that fall in the range (at most S of them); when the list reaches S, rebuild the prefix array in O(n) and clear the list. Queries cost O(S), and updates cost O(1) plus an O(n) rebuild every S updates, which is O(n / S) amortised.

Balancing the two gives S ≈ sqrt(n) again. The same idea underlies many offline and batched techniques: do cheap work often, and expensive clean-ups rarely. It also shows when decomposition is the wrong tool: with only a few updates, a plain prefix array plus brute force is simpler, and with a heavy mix a Fenwick or segment tree gives O(log n) for both.

StructureQueryUpdateNotes
Plain arrayO(n)O(1)no preprocessing
Prefix sumsO(1)O(n)static data
Square root blocksO(sqrt n)O(1) point, O(sqrt n) rangesimple, supports many operations
Fenwick / segment treeO(log n)O(log n)the default choice
Batched rebuild (S = sqrt n)O(sqrt n)O(sqrt n) amortisedwhen updates come in bursts
Java
1class BatchedPrefix {
2    private final int n, limit;
3    private long[] prefix;                       // prefix[i] = sum of the first i values at the last rebuild
4    private final int[] a;
5    private final List<int[]> pending = new ArrayList<>();     // {index, delta} since the last rebuild
6    BatchedPrefix(int[] values) {
7        a = values.clone();
8        n = a.length;
9        limit = Math.max(1, (int) Math.sqrt(n));
10        rebuild();
11    }
12    private void rebuild() {
13        prefix = new long[n + 1];
14        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i];
15        pending.clear();
16    }
17    void add(int i, int delta) {
18        a[i] += delta;
19        pending.add(new int[]{i, delta});
20        if (pending.size() >= limit) rebuild();  // the expensive step, once per `limit` updates
21    }
22    long sum(int l, int r) {                     // inclusive
23        long s = prefix[r + 1] - prefix[l];
24        for (int[] p : pending) if (p[0] >= l && p[0] <= r) s += p[1];
25        return s;
26    }
27}

Square root decomposition: block sums, updates and lazy block tags

Interactive · edit the input

Your input

Try

block 0: sum = 21

40
71
12
93

block 1: sum = 19

34
85
26
67

block 2: sum = 15

58
09
710
311
Setup

12 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.

Step 1 / 7
Java
1int B; int[] a, sum, lazy;                       // block b covers a[b*B .. min(n, (b+1)*B) - 1]
2void build(int[] values) {
3    a = values; int n = a.length; B = (int) Math.ceil(Math.sqrt(n));
4    sum = new int[(n + B - 1) / B]; lazy = new int[sum.length];
5    for (int i = 0; i < n; i++) sum[i / B] += a[i];
6}
7void update(int i, int v) {                      // point update: O(1)
8    int cur = a[i] + lazy[i / B];
9    sum[i / B] += v - cur; a[i] = v - lazy[i / B];
10}
11int query(int l, int r) {                        // inclusive
12    int total = 0;
13    for (int i = l; i <= r; ) {
14        if (i % B == 0 && i + B - 1 <= r) { total += sum[i / B]; i += B; }      // a whole block: one step
15        else { total += a[i] + lazy[i / B]; i++; }                              // a partial block: element by element
16    }
17    return total;
18}
19void rangeAdd(int l, int r, int v) {
20    for (int i = l; i <= r; ) {
21        int b = i / B;
22        if (i % B == 0 && i + B - 1 <= r && (b + 1) * B <= a.length) { lazy[b] += v; sum[b] += v * B; i += B; }   // whole block: a tag
23        else { a[i] += v; sum[b] += v; i++; }                                   // partial block: touch the element
24    }
25}

Live state

0 elements touched0 blocks used

n

12

block size B

4

blocks

3

No condition evaluated on this step
Execution trace (dry run table)Show 7 steps
StepLineStateWhat happens
1L3n=12 block size B=4 blocks=312 values are cut into 3 blocks of 4 (B = ceil(sqrt 12)). Each block stores its sum. A query reads whole blocks in one step and walks only the partial blocks at the two ends: at most 2 × B + n / B steps.
2L15i=2 value=1 total=1sum[2..9]: index 2 is in a partial block: add the element 1 (total 1).
3L15i=3 value=9 total=10sum[2..9]: index 3 is in a partial block: add the element 9 (total 10).
4L14i=4 block=1 total=29sum[2..9]: block 1 lies fully inside [2, 9]: add its stored sum 19 in one step (total 29).
5L15i=8 value=5 total=34sum[2..9]: index 8 is in a partial block: add the element 5 (total 34).
6L15i=9 value=0 total=34sum[2..9]: index 9 is in a partial block: add the element 0 (total 34).
7L17return=34 elements touched=4 blocks used=1Sum = 34, from 1 whole block and 4 single elements. A plain loop would have read 8.

Practice ladder

Now try it yourself

Easy

  • Range Sum Query - Mutable

Medium

  • Range Sum Query 2D - Mutable
  • Count of Smaller Numbers After Self

Advanced

  • Range Frequency Queries
  • Dynamic Range Sum Queries (CSES)

Key takeaways

  • Blocks of about sqrt(n) with one summary each: whole blocks in one step, partial blocks element by element.
  • Point updates are O(1); range updates use a lazy tag per block for O(sqrt n).
  • Rebuilding every S updates trades update cost for query cost; sqrt(n) balances them.