You need to answer range sum queries on an array, and the array keeps changing. You know a prefix sum array handles static queries in O(1), but falls apart when updates arrive. You have heard of segment trees and Fenwick trees, but the interviewer just asked you for something simpler, or maybe you are in a contest and need a quick, correct solution without debugging pointer-heavy tree code.

Sqrt decomposition is that simpler tool. It splits the array into blocks of size roughly sqrt(n), precomputes an aggregate for each block, and answers range queries in O(sqrt(n)) while supporting point updates in O(1). The idea is so straightforward that you can code it from scratch in five minutes, yet powerful enough to solve a surprising number of competitive programming and interview problems.

Sqrt decomposition occupies a sweet spot in the data structure landscape. It is not the fastest option for range queries (segment trees and Fenwick trees beat it asymptotically), but it has three properties that make it invaluable:

Real-World Applications

The Problem

Consider the simplest version: you have an array of n integers, and you need to support two operations:

With a plain array, updates are O(1) but queries are O(n) because you iterate through every element in the range.

With a prefix sum array, queries are O(1) but updates are O(n) because changing one element requires rebuilding the prefix sums from that point onward.

We want something in the middle. Not as fast as a segment tree's O(log n), but far simpler and still much better than O(n).

The Key Insight

What if we split the array into chunks and precompute the answer for each chunk? Then a range query becomes: handle the partial chunk on the left, add up all the full chunks in the middle, and handle the partial chunk on the right.

The question is: how big should each chunk be?

If the block size is b, then:

We want to minimize b + n/b. By the AM-GM inequality, b + n/b >= 2 * sqrt(n), and equality holds when b = sqrt(n). So the optimal block size is sqrt(n), giving us O(sqrt(n)) per query.

Updates are even simpler. Change the element, then recompute the aggregate for the single block that contains it. That is O(1) for the element change plus O(b) = O(sqrt(n)) for recomputing the block, but if you maintain the aggregate incrementally (subtract old value, add new value), the update is O(1).

Visual Overview

Each block stores the sum of sqrt(n) elements. For n = 9, that is blocks of size 3, giving us 3 blocks.

The Analogy

Think of it like chapters in a book. If someone asks "how many pages are between page 47 and page 182?", you do not count page by page. You count the partial pages left in chapter 3 (where page 47 is), add up the total pages for chapters 4 through 11 (the full chapters in between), and count the pages from the start of chapter 12 up to page 182. The chapters are your blocks, and the page counts per chapter are your precomputed aggregates.

Block Structure

Given an array of size n, we choose a block size b = floor(sqrt(n)). This creates ceil(n / b) blocks. Element at index i belongs to block i / b (integer division).

The last block might be smaller than b elements. For example, if n = 10 and b = 3, the blocks cover indices [0,2], [3,5], [6,8], and [9,9]. The last block has only 1 element. This is perfectly fine, just be careful with the boundaries.

We maintain a separate array blocks[] where blocks[k] stores the precomputed aggregate (sum, min, max, etc.) for block k.

Operation 1: Build (O(n))

Walk through the array once. For each element at index i, add it to blocks[i / b].

This is a single O(n) pass, nothing fancy.

Operation 2: Point Update (O(1))

To update arr[i] to a new value newVal:

Because we adjust the block sum incrementally rather than recomputing it from scratch, this takes O(1) time.

Operation 3: Range Query (O(sqrt(n)))

This is the core operation and the one that requires the most care. Given a range [l, r], we split the work into three parts:

There is one special case: if l and r are in the same block, just iterate from l to r directly.

The left and right partial blocks each contribute at most b elements. The middle has at most n/b full blocks. The total work is O(b + n/b) = O(sqrt(n)).

Range Query: Detailed Flow

Let us be more precise about the boundary calculations.

Let us trace through a concrete example to make everything tangible.

Problem Setup

Step 1: Building the Blocks

Step 2: Range Query [2, 7]

We want arr[2] + arr[3] + arr[4] + arr[5] + arr[6] + arr[7] = 1 + 4 + 9 + 3 + 7 + 6 = 30.

Let us visualize which elements contribute to each part:

Red nodes are partial block elements (iterated individually). Green nodes belong to a full block (we use the precomputed sum). Blue nodes are outside the query range.

Step 3: Point Update - Set arr[4] = 2

Step 4: Range Query [2, 7] After Update

The update took O(1), and the query again took O(sqrt(n)) = O(3) steps through the blocks.

The SqrtDecomposition class stores the original array alongside an array of block sums. The constructor builds those block sums in a single pass over the input, update adjusts the affected block sum in constant time, and query walks any partial blocks element by element while jumping over fully covered blocks using their precomputed sums.

Let us walk through the key decisions in the implementation.

The constructor copies the array and builds block sums in one pass. We compute blockSize = floor(sqrt(n)) with a safety check (max(1, ...)) to avoid division by zero for empty arrays. The number of blocks is ceil(n / blockSize), computed using the integer ceiling trick (n + blockSize - 1) / blockSize. Then a single loop accumulates each element into its block.

The update is O(1) using incremental adjustment. Instead of recomputing the entire block sum, we adjust it by the difference newVal - arr[idx]. This is a common optimization. If you forgot this trick and recomputed the block from scratch by iterating over all its elements, the update would be O(sqrt(n)) instead of O(1). Both are acceptable, but the incremental approach is cleaner.

The query handles three cases. The most important detail is the same-block check. If l and r fall in the same block, there are no full middle blocks, so we just iterate from l to r. Without this check, the left-partial and right-partial loops might overlap or produce incorrect ranges.

Block boundary calculations use integer arithmetic. The end of block k is (k + 1) * blockSize - 1, and the start of block k is k * blockSize. These formulas work correctly even for the last block, which might be shorter than blockSize.

Common Mistakes

1. Forgetting the same-block case. If l and r are in the same block and you skip straight to the three-part logic, the "full middle blocks" loop runs with an empty range (or worse, wraps around). Always check lBlock == rBlock first.

2. Using sqrt() without casting carefully. Floating-point sqrt() can return slightly less than the true value (e.g., sqrt(9) might return 2.9999... on some platforms). In C++ and Java, cast to int after computing sqrt. In Python, use math.isqrt(n) for exact integer square root.

3. Off-by-one on block boundaries. The end of block k is (k + 1) * blockSize - 1, not (k + 1) * blockSize. Forgetting the - 1 means you include one extra element from the next block.

4. Not handling the last block's size. The last block might contain fewer than blockSize elements. This is usually handled automatically because the array boundary n - 1 limits the iteration, but if you compute block boundaries independently (without clamping to n - 1), you can read past the array.

5. Forgetting to update the underlying array. When you adjust the block sum, you must also set arr[idx] = newVal. Forgetting this means the next query that iterates through individual elements in that block will use the stale value.

Why sqrt(n) Is the Optimal Block Size

This is worth understanding mathematically because interviewers sometimes ask about it.

For a block size b, a range query does at most b work for the left partial block, b work for the right partial block, and n/b work for the full middle blocks. The total is O(b + n/b).

We want to choose b to minimize f(b) = b + n/b. Taking the derivative: f'(b) = 1 - n/b^2. Setting f'(b) = 0 gives b^2 = n, so b = sqrt(n).

If you prefer the AM-GM approach: for positive values b and n/b, the arithmetic mean is always at least the geometric mean:

(b + n/b) / 2 >= sqrt(b * n/b) = sqrt(n)

So b + n/b >= 2 * sqrt(n), and equality holds when b = n/b, i.e., b = sqrt(n).

Either way, the minimum of b + n/b is 2 * sqrt(n), achieved at b = sqrt(n).

Time Complexity

Space Complexity

O(n + sqrt(n)) = O(n). We store the original array (n elements) plus the block array (sqrt(n) elements). The block array overhead is negligible.

Comparison with Other Approaches

Variation 1: Range Update with Lazy Blocks

Sometimes you need to add a value delta to every element in a range [l, r], then later query individual elements or range sums. Sqrt decomposition handles this with a lazy value per block.

Each block gets a lazy[] field. When updating a range:

When querying:

This gives O(sqrt(n)) for both range updates and range queries.

Variation 2: Mo's Algorithm

Mo's algorithm is one of the most elegant applications of sqrt decomposition. It answers offline range queries (where you know all queries in advance) by reordering them to minimize the total work.

The key idea: sort queries by (l / blockSize, r). Queries in the same block of l are processed together with r increasing. As you move from one query to the next, you expand or shrink the current window [curL, curR] by at most O(sqrt(n)) on the left and O(n) on the right, but the total movement across all queries is O((n + q) * sqrt(n)).

Mo's algorithm works for any problem where you can efficiently add or remove a single element from the current window. Common applications include:

Variation 3: Sqrt Decomposition on Queries

Instead of decomposing the array, you can decompose the queries. Process queries in batches of sqrt(q) (where q is the total number of queries). Within each batch, apply all updates, answer all queries using a combination of the base structure and pending updates. This technique is useful when the data structure does not support efficient updates directly.

Comparison Table

Choosing between sqrt decomposition, segment tree, Fenwick tree, and sparse table depends on the constraints of your problem. Here is a detailed comparison to help you decide.

Sqrt Decomposition vs Segment Tree

Segment trees give O(log n) per operation, which is asymptotically better than O(sqrt(n)). For n = 10^6, log2(n) is about 20, while sqrt(n) is 1000, a factor of 50 difference. So why would anyone choose sqrt decomposition?

Sqrt Decomposition vs Fenwick Tree

Fenwick trees are simpler than segment trees but still require understanding bit manipulation. They are also limited to invertible operations (the aggregate must have an inverse, like addition has subtraction). You cannot build a Fenwick tree for range minimum queries.

Sqrt decomposition has no such restriction. It works with min, max, GCD, and even more exotic operations like "count of elements greater than k in a range."

Sqrt Decomposition vs Sparse Table

Sparse tables answer range queries in O(1) after O(n log n) preprocessing, but only for idempotent operations (min, max, GCD) and they do not support updates at all. If you need updates, sparse tables are out.

When to Choose Sqrt Decomposition

When NOT to Choose Sqrt Decomposition

Pattern 1: Range Aggregate Queries

Problem type: Given an array with point updates, answer range sum, range min, or range max queries.

How sqrt decomposition helps: Each block stores the precomputed aggregate. Queries combine partial elements with full block aggregates. For min/max, the logic is the same as sum but you take min/max instead of adding.

Pattern 2: Frequency and Threshold Queries

Problem type: Count the number of elements in a range [l, r] that are greater than some threshold, or count distinct values.

How sqrt decomposition helps: Each block maintains a sorted copy of its elements or a frequency map. To answer "count of elements > k in [l, r]", iterate for partial blocks and use binary search within full blocks. This gives O(sqrt(n) * log(sqrt(n))) per query.

Pattern 3: Offline Range Queries (Mo's Algorithm)

Problem type: Answer many range queries offline where the "answer" depends on some property of the subarray (distinct count, mode, frequency histogram).

How sqrt decomposition helps: Mo's algorithm sorts queries by (l/blockSize, r) and sweeps a window across the array. The block-based ordering ensures the total movement of left and right pointers is O((n + q) * sqrt(n)).

Pattern 4: Range Update, Range Query

Problem type: Add a value to all elements in [l, r], then query the sum of [l', r'].

How sqrt decomposition helps: Use the lazy block approach described in the Variations section. Full blocks get lazy markers, partial blocks are updated element by element. Both operations take O(sqrt(n)).

Interview Tips

Key Takeaways

Quick Reference