Square Root Decomposition

Split the array into blocks of size $\approx \sqrt{n}$. Queries touch $O(\sqrt{n})$ whole blocks plus $O(\sqrt{n})$ individual elements, giving $O(\sqrt{n})$ per operation. Slower than a segment tree asymptotically, but it handles operations a segment tree cannot.

Basic range sum

int B;                                   // block size ~ sqrt(n)
vector<long long> a, blockSum;
 
void build(int n) {
    B = max(1, (int)sqrt(n));
    blockSum.assign((n + B - 1) / B, 0);
    for (int i = 0; i < n; i++) blockSum[i / B] += a[i];
}
 
void update(int i, long long v) { blockSum[i / B] += v - a[i]; a[i] = v; }
 
long long query(int l, int r) {
    long long res = 0;
    while (l <= r && l % B) res += a[l++];               // partial left block
    while (l + B - 1 <= r) { res += blockSum[l / B]; l += B; }   // whole blocks
    while (l <= r) res += a[l++];                        // partial right block
    return res;
}

Choosing the block size

$\sqrt{n}$ balances “number of blocks” against “elements per block”. But when updates and queries have different costs, tune it:

$\text{cost}=q_u\cdot \frac{n}{B}+q_q\cdot B⟹B^{\ast }=\sqrt{\frac{q_{u}n}{q_q}}.$

For $10^5$ updates and $10^5$ queries on $n=10^5$, $B=\sqrt{n}$ is right. If updates are rare, use larger blocks.

Why bother, given segment trees exist

Sqrt decomposition wins in three situations:

1. The operation has no efficient merge. A segment tree needs an associative combine. Sqrt decomposition only needs “rebuild a block in $O(B)$”, which is a far weaker requirement.

2. You need per-block auxiliary structures. Keeping each block sorted allows queries a segment tree cannot answer cheaply:

// count elements > x in [l, r]
long long count = 0;
// partial blocks: scan directly
// whole blocks: binary search in the sorted copy
count += sorted[b].end() - upper_bound(sorted[b].begin(), sorted[b].end(), x);

$O(\sqrt{n}\log n)$ per query, and it supports “range add” by keeping a per-block offset.

3. The problem is genuinely offline — see Mo’s algorithm, which is sqrt decomposition applied to the query order rather than the array.

The variants

Variant	Idea	Complexity
Blocks over the array	the standard	$O(\sqrt{n})$
Blocks + sorted copies	order-statistics queries	$O(\sqrt{n}\log n)$
Blocks + lazy per-block tag	range assign / add	$O(\sqrt{n})$
Mo’s algorithm	sort the queries by block	$O((n+q)\sqrt{n})$
Mo on trees	Mo over the Euler tour	$O(n\sqrt{n})$
Sqrt rebuilding	rebuild the structure every $\sqrt{q}$ operations	$O(\sqrt{q})$ amortized
Sqrt on values	split the value range, not the indices	problem-specific
Buffered updates	collect $\sqrt{n}$ updates, then rebuild	$O(\sqrt{n})$

Sqrt rebuilding

A general escape hatch: keep a fast static structure plus a small buffer of recent updates. Answer a query as “static answer, corrected by the $O(\sqrt{q})$ buffered updates”, and rebuild the static structure every $\sqrt{q}$ updates. This turns many “impossible to update” structures into updatable ones at a ​ cost — it works for convex hulls, sorted lists, and precomputed tables alike.

Sqrt decomposition on trees

Split the tree into $O(\sqrt{n})$ connected blocks of size $O(\sqrt{n})$, or by depth into $\sqrt{n}$ layers. Less common than HLD or centroid decomposition, but occasionally the only thing that fits an unusual query.

When $\sqrt{n}$ is fast enough

With $n=q=10^5$, $O((n+q)\sqrt{n})\approx 6\cdot 10^7$ — comfortable. At $n=10^6$ it is $10^9$ and too slow. The rule of thumb: sqrt techniques are for $n\le 2\cdot 10^5$.

See also: Mo’s Algorithm · Segment Tree · Range Query Techniques