Square Root Decomposition: O(sqrt n) Range Queries Without Segment Trees

Algorithm/Topic Statement#

Square root decomposition, often called sqrt decomposition or block decomposition, partitions an array of length n into roughly the square root of n contiguous blocks, each of size around the square root of n. For each block you precompute an aggregate such as a sum, a minimum, a maximum, or a frequency map. When a query asks about a range from index L to R, you use full block aggregates for blocks entirely inside the range and walk element by element only through the at most two partial blocks at the boundaries. The total cost per query and per point update is order square root of n, dramatically faster than the naive order n scan but easier to implement than a segment tree or Fenwick tree.

Why This Topic Matters#

Sqrt decomposition is the data structure equivalent of a Swiss Army knife. It is not the fastest, but it handles every range-query operation you can think of with twenty lines of code. Interviewers love asking range-query questions because they test whether candidates can move past the brute force template and reason about precomputation tradeoffs. Sqrt decomposition is also the gateway technique to Mo's algorithm, which solves entire batches of offline range queries in order n plus q times square root of n. If you compete on Codeforces or attempt the harder LeetCode contests, you will hit problems where segment trees feel like overkill but brute force times out, and that is exactly the sweet spot where block decomposition shines. Beyond contests, the underlying idea, namely splitting work into square root sized chunks, appears in cache-aware algorithms, database indexing, and external memory data structures.

The Core Insight (math intuition + proof sketch)#

Why does the magic number square root of n give the optimal balance? Imagine you choose a block size B. A range query touches at most n divided by B full blocks plus two partial blocks of size B, giving a total cost proportional to n divided by B plus B. Calculus or simple AM-GM tells you the sum is minimized when n divided by B equals B, so B equals the square root of n. The minimum query cost becomes 2 times the square root of n. Updates take constant time when you maintain block aggregates, because you just adjust one cell and one block summary.

The proof that this is correct rests on associativity of the aggregation operation. Sums, minima, maxima, gcd, xor, and matrix products all decompose cleanly because combining three pieces, the left partial, the middle full blocks, and the right partial, gives the same answer as scanning element by element. For non-associative operations like averages or top-k frequencies, you may need richer per-block structures, such as sorted arrays or hash maps, but the framework still applies. Mo's algorithm pushes the idea further by sorting queries so that the global pointer movement totals only order n times the square root of n across all queries.

Visual Dry Run / Worked Example#

Take the array 1, 3, 5, 2, 7, 4, 6, 8 of length 8. The square root of 8 rounded up is 3, so each block has 3 elements. Block zero is 1, 3, 5 with sum 9. Block one is 2, 7, 4 with sum 13. Block two is 6, 8 with sum 14. Now answer the range sum from index 1 to 6.

Index 1 sits inside block zero, index 6 sits inside block two. The left partial sums positions 1 and 2 of the original array, which are 3 and 5, totaling 8. The middle block, block one, contributes its full aggregate 13. The right partial sums positions 6 of the original array, which is 6, totaling 6. Add 8 plus 13 plus 6 to get 27. Verify by scanning 3, 5, 2, 7, 4, 6 directly, which sums to 27.

For an update, say we set index 4 to value 10 instead of 7. Block one's aggregate adjusts by 10 minus 7 equals 3, becoming 16. The cell value updates to 10. Future queries see the change in constant time.

Solution / Implementation#

Python (range sum and range min with point updates)#

import math
 
class SqrtDecomp:
    def __init__(self, arr):
        self.n = len(arr)
        self.arr = arr[:]
        self.B = int(math.sqrt(self.n)) + 1
        nb = (self.n + self.B - 1) // self.B
        self.blocks = [0] * nb
        for i, v in enumerate(arr):
            self.blocks[i // self.B] += v
 
    def update(self, i, val):
        self.blocks[i // self.B] += val - self.arr[i]
        self.arr[i] = val
 
    def query(self, l, r):
        total = 0
        bl, br = l // self.B, r // self.B
        if bl == br:
            return sum(self.arr[l:r+1])
        total += sum(self.arr[l:(bl+1)*self.B])
        for b in range(bl+1, br):
            total += self.blocks[b]
        total += sum(self.arr[br*self.B:r+1])
        return total

JavaScript#

class SqrtDecomp {
  constructor(arr) {
    this.n = arr.length;
    this.arr = [...arr];
    this.B = Math.floor(Math.sqrt(this.n)) + 1;
    const nb = Math.ceil(this.n / this.B);
    this.blocks = new Array(nb).fill(0);
    for (let i = 0; i < this.n; i++) this.blocks[Math.floor(i / this.B)] += arr[i];
  }
  update(i, val) {
    this.blocks[Math.floor(i / this.B)] += val - this.arr[i];
    this.arr[i] = val;
  }
  query(l, r) {
    let total = 0;
    const bl = Math.floor(l / this.B), br = Math.floor(r / this.B);
    if (bl === br) {
      for (let i = l; i <= r; i++) total += this.arr[i];
      return total;
    }
    for (let i = l; i < (bl + 1) * this.B; i++) total += this.arr[i];
    for (let b = bl + 1; b < br; b++) total += this.blocks[b];
    for (let i = br * this.B; i <= r; i++) total += this.arr[i];
    return total;
  }
}

Time per query and update is order square root of n. Space is order n for the array plus order square root of n for the block aggregates. Mo's algorithm raises the offline batch cost to order n plus q times the square root of n.

Common Mistakes#

The most frequent off-by-one bug is using exclusive versus inclusive right endpoints inconsistently across query and helper functions. Pick one convention and document it with a comment on the class. Another classic mistake is recomputing the block sum from scratch on every update; you only need to add the delta. Block size also matters. If you hard-code 1000 for an array of size 10 to the 5th, your queries blow up to 100 blocks plus 1000 elements, missing the sweet spot. Always tie the block size to the actual length. Finally, when implementing range minimum with updates, do not forget that decreasing a value can be handled in constant time but increasing it may require rescanning the block to find the new min, which adds an extra square root of n factor in the worst case.

Interview Tips#

If your interviewer asks you to support range sum with updates and you panic remembering segment trees, default to sqrt decomposition. It is faster to write, easier to debug, and good enough for arrays up to a few hundred thousand elements. Mention the asymptotic, defend your block size choice, and walk through one query out loud. If the interviewer follows up with offline queries, pivot to Mo's algorithm and explain how sorting queries by the block of the left endpoint and the right endpoint creates a total movement bound. Demonstrating breadth across this family signals strong competitive programming maturity.

Follow-up Questions#

Could you generalize the structure to support range update and point query, or even range update and range query, using a lazy block approach? How would you adapt sqrt decomposition for two-dimensional arrays where queries are rectangles? Can you describe how Mo's algorithm changes when each element appears at most some constant times, and why that helps when answering distinct-value queries? What advantages does sqrt decomposition have over segment trees in cache-constrained or external memory settings?

Key Takeaways#

• Square root decomposition splits an array into blocks of size around the square root of n and precomputes an aggregate per block.
• Range queries cost order square root of n by combining at most two partial blocks with the full blocks in between.
• Point updates cost order one when the aggregate operation is invertible like a sum, or order square root of n if you must rescan a block.
• Mo's algorithm extends the technique to batches of offline queries with total cost order n plus q times square root of n.
• The framework supports any associative aggregation, making it the most flexible range-query structure for interviews.
• Choose block size dynamically based on n, document inclusive versus exclusive ranges, and avoid recomputing aggregates from scratch.