Patterns/Part VIII - Cross-Topic Deep Dives/Square Root Decomposition

Pattern Reference

Square Root Decomposition

"Partition array into sqrt blocks. Batch queries, lazy rebuild. Range sum/update, mode query, k-th smallest in range."

Loading...

Deep Dive Tutorial

Split array into blocks of size B = √n. For each block, maintain a summary value (sum, min, max, etc.). Range query [l, r]: process partial left block, full middle blocks (O(n/B)), partial right block. Range update [l, r]: update partial blocks element-wise, full blocks via lazy tag. O(B + n/B) = O(√n) per operation when B = √n.

Sqrt decomposition for range sum query with range add update
class SqrtDecomp {
    constructor(arr) {
        this.n = arr.length;
        this.B = Math.ceil(Math.sqrt(this.n));
        this.arr = [...arr];
        this.blocks = new Array(Math.ceil(this.n / this.B)).fill(0);
        this.lazy = new Array(this.blocks.length).fill(0); // lazy add for full blocks
        for (let i = 0; i < this.n; i++) this.blocks[Math.floor(i / this.B)] += arr[i];
    }

    update(l, r, v) { // add v to arr[l..r]
        const bL = Math.floor(l / this.B), bR = Math.floor(r / this.B);
        if (bL === bR) {
            for (let i = l; i <= r; i++) { this.arr[i] += v; this.blocks[bL] += v; }
            return;
        }
        for (let i = l; i < (bL + 1) * this.B; i++) { this.arr[i] += v; this.blocks[bL] += v; }
        for (let b = bL + 1; b < bR; b++) { this.lazy[b] += v; this.blocks[b] += v * this.B; }
        for (let i = bR * this.B; i <= r; i++) { this.arr[i] += v; this.blocks[bR] += v; }
    }

    query(l, r) { // sum arr[l..r]
        const bL = Math.floor(l / this.B), bR = Math.floor(r / this.B);
        let sum = 0;
        if (bL === bR) {
            for (let i = l; i <= r; i++) sum += this.arr[i] + this.lazy[bL];
            return sum;
        }
        for (let i = l; i < (bL + 1) * this.B; i++) sum += this.arr[i] + this.lazy[bL];
        for (let b = bL + 1; b < bR; b++) sum += this.blocks[b];
        for (let i = bR * this.B; i <= r; i++) sum += this.arr[i] + this.lazy[bR];
        return sum;
    }
}

Worked Problems

1
Range Sum Query — Mutable
Medium
Solve ↗
2
Count of Smaller Numbers After Self (Sqrt approach)
Hard
Solve ↗
3
Painting the Fence (range update query)
Hard
Solve ↗
4
Frequency Queries
Medium
Solve ↗
√
Sqrt decomposition tradeoffs:
- Simpler than segment tree: no recursion, no lazy propagation complexity
- Slower: O(√n) vs O(log n) per operation
- Flexible: can handle any associative operation without careful implementation

Choose sqrt decomp when:
- Problem has mixed update/query that's hard to segment-tree
- n ≤ 10^5 (√n ≈ 316, fits in time limit)
- Offline queries: Mo's algorithm (specialized sqrt decomp)

Block size optimization: B = √n minimizes O(B + n/B). For different query/update ratios, can tune B. For q queries and u updates: optimal B = √(n·u/q).
← All Patterns