Sqrt Decomposition on Queries

Balance two costs by choosing a threshold around ​. The array-splitting version is on Square Root Decomposition; this page covers the other sqrt tricks — the ones that split operations, values or time rather than indices.

1. Sqrt rebuilding — the general escape hatch

Keep a fast static structure plus a small buffer of recent updates.

query  = static_answer + correction_from_buffer     O(fast + |buffer|)
update = append to the buffer                        O(1)
every sqrt(q) updates: rebuild the static structure  O(build)

Amortized $O\left(\frac{\text{build}}{\sqrt{q}}+\sqrt{q}\right)$ per operation. This makes any static structure updatable:

Static structure	Becomes
Sorted array	insertable “sorted list”
Convex hull	dynamic hull
Precomputed table	updatable table
Sparse table	supports point updates
Aho-Corasick automaton	supports pattern insertion

The Aho-Corasick case is a nice one: rebuilding the automaton every $\sqrt{q}$ insertions, and brute-forcing the buffered patterns, gives an “add patterns online” multi-pattern matcher.

2. Heavy/light splitting by frequency

Split objects by a threshold $B\approx \sqrt{n}$ and handle each class differently.

Setting	Heavy	Light
Values with count $>B$	at most $n/B$ of them — precompute per heavy value	few occurrences — brute force
Vertices with degree $>B$	at most $2m/B$ of them	iterate their neighbours directly
Patterns with length $>B$	at most $\text{total}/B$ of them	group by length
Queries with range $>B$	few of them	brute force

Triangle counting is the classic: orient each edge from lower to higher degree; every vertex then has out-degree $O(\sqrt{m})$, so enumerating pairs of out-neighbours is $O(m^{1.5})$.

// count triangles in O(m^1.5)
for (auto [u, v] : edges)
    if (make_pair(deg[u], u) < make_pair(deg[v], v)) g[u].push_back(v);
    else g[v].push_back(u);
for (int u = 0; u < n; u++) {
    for (int v : g[u]) mark[v] = 1;
    for (int v : g[u]) for (int w : g[v]) if (mark[w]) triangles++;
    for (int v : g[u]) mark[v] = 0;
}

3. Sqrt on values

When the values are bounded by $V$, split at $\sqrt{V}$:

• small values — maintain a frequency array;
• large values — there are at most $n/\sqrt{V}$ distinct ones with high multiplicity; handle them individually.

Used for “count subsets summing to $S$” and knapsack variants where the number of distinct item weights is $O(\sqrt{\sum w})$ — a genuinely useful observation, since $n$ distinct positive weights summing to $W$ force $n=O(\sqrt{W})$.

4. Sqrt on time (operation batching)

Process queries in blocks of $\sqrt{q}$:

• within a block, treat the structure as static and answer with brute force over the block’s updates;
• at the end of each block, apply all its updates in bulk.

This is the shape of Mo’s algorithm and of many “rebuild periodically” solutions.

Choosing the threshold

$\text{cost}=\frac{A}{B}+C\cdot B⟹B^{\ast }=\sqrt{A/C}.$

$\sqrt{n}$ is the right answer only when the two sides have equal constants. When updates are much rarer than queries (or vice versa), tune $B$ — a 2-3× speedup is typical, and it is often the difference between TLE and AC.

Measure rather than guess: try $B\in \{\sqrt{n}/4,\sqrt{n}/2,\sqrt{n},2\sqrt{n},4\sqrt{n}\}$.

When sqrt techniques are right

$O(\sqrt{n})$ per operation with $n=q=10^5$ is about $3\cdot 10^7$ — comfortable. At $n=10^6$ it is $10^9$ and too slow.

Rule of thumb: sqrt methods are for $n\le 2\cdot 10^5$. Their value is that they work when nothing else does — for operations that no tree structure can merge, and for problems whose structure resists $\log$-factor solutions.

See also: Square Root Decomposition · Mo’s Algorithm · Offline Query Processing