Pattern Guide
Sqrt Decomposition
"Divide array into √n blocks. O(√n) per query/update. No preprocessing needed."
Square root decomposition divides an array into blocks of size √n. Queries and updates touch at most O(√n) full blocks plus O(√n) elements at the boundaries. Total O(√n) per operation. Simpler than segment tree for mixed queries and updates. Extended by Mo's algorithm for offline queries. Useful when segment tree is too complex to implement or when offline processing isn't possible.
Problems you can solve with this pattern
4 problems · click any to start solving
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;
}
}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.
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;
}
}- 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).