Senior LevelData Structures & Algorithms
What is Square Root Decomposition and when is it used?
ā Interview Prompt: Explain sqrt decomposition for O(āN) range queries and updates, block processing, and trade-offs vs Segment Trees.
Sqrt Decomposition divides an array of $N$ elements into $\sqrt{N}$ blocks of size $\sqrt{N}$.
Preprocessing: $O(N)$
Compute aggregate (sum, min, max) for each block.
Range Query: $O(\sqrt{N})$
ā¢
For partial blocks on the left/right: iterate elements individually.
ā¢
For complete blocks in the middle: use precomputed block aggregate.
Point Update: $O(1)$
Update element + update its block aggregate.
When to Use:
ā¢
When Segment Tree is too complex to implement during contests.
ā¢
Problems where $O(\sqrt{N})$ is sufficient (queries $Q \leq 10^5$, $N \leq 10^5$).
ā¢
Mo's Algorithm is a sqrt decomposition on queries.
Code Implementation Example
typescript
class SqrtDecomposition {
private blocks: number[];
private blockSize: number;
constructor(private arr: number[]) {
this.blockSize = Math.ceil(Math.sqrt(arr.length));
this.blocks = new Array(Math.ceil(arr.length / this.blockSize)).fill(0);
for (let i = 0; i < arr.length; i++)
this.blocks[Math.floor(i / this.blockSize)] += arr[i];
}
update(i: number, val: number): void {
this.blocks[Math.floor(i / this.blockSize)] += val - this.arr[i];
this.arr[i] = val;
}
query(l: number, r: number): number { // range sum [l, r]
let sum = 0, bs = this.blockSize;
let startBlock = Math.floor(l / bs), endBlock = Math.floor(r / bs);
if (startBlock === endBlock) {
for (let i = l; i <= r; i++) sum += this.arr[i];
} else {
for (let i = l; i < (startBlock + 1) * bs; i++) sum += this.arr[i];
for (let b = startBlock + 1; b < endBlock; b++) sum += this.blocks[b];
for (let i = endBlock * bs; i <= r; i++) sum += this.arr[i];
}
return sum;
}
}š”Sqrt Decomposition ā O(āN) range sum queries and O(1) point updates.
šÆ Interview Key Takeaway
Sqrt Decomposition achieves O(āN) queries/updates. It is simpler than Segment Trees (no tree structure) and is the basis for Mo's Algorithm and block-based optimisations.
#DSA#Sqrt Decomposition#Range Queries#Block Processing#Senior
Back to all Data Structures & Algorithms Questionsā