xi. Sqrt Decomposition

Split something (the array, the values, the time line, the set of objects) into  ​-sized pieces so that two different costs balance. It’s slower than a tree, but it only needs “rebuild a block in $O(B)$” rather than an associative merge, so it handles operations nothing else can. Rule of thumb: fine for $n,q\le 2\cdot 10^5$.

Blocks over the array

int B; vector<ll> a, blk;                              // blk[b] = aggregate of block b
void build() { B = max(1, (int)sqrt(sz(a))); blk.assign((sz(a) + B - 1) / B, 0); for (int i = 0; i < sz(a); i++) blk[i / B] += a[i]; }
void update(int i, ll v) { blk[i / B] += v - a[i]; a[i] = v; }
ll query(int l, int r) {                               // [l, r)
    ll s = 0;
    while (l < r && l % B) s += a[l++];
    while (l + B <= r) s += blk[l / B], l += B;
    while (l < r) s += a[l++];
    return s;
}

Per-block extras make it powerful:

• lazy tag per block (add/assign applied to whole blocks, pushed when a partial block is touched);
• sorted copy per block: count $\le x$ in $O(\sqrt{n}\log n)$, with range add as a per-block offset; rebuilding a partially updated block costs $O(B\log B)$ (or $O(B)$ by merging);
• frequency table per block prefix ($cnt[b][v]$ = occurrences of $v$ in blocks $\mathrm{0..}b$, $O(n\sqrt{n})$ memory) for “count of $v$ in a range” in $O(\sqrt{n})$ when values are small;
• convex hull per block for “add to range, query max of $a_i\cdot c_i$” (rebuild the hull on partial updates; whole-block adds shift a query pointer).

Proof: optimal block size

If an operation costs $\frac{n}{B}$ for whole blocks plus $B$ for partial ones, the sum $\frac{n}{B}+B$ is minimised at $B=\sqrt{n}$ (AM-GM: $\frac{n}{B}+B\ge 2\sqrt{n}$, with equality iff $B=\sqrt{n}$). With $q_1$ operations of cost $A/B$ and $q_2$ of cost $C\cdot B$, the total $q_{1}A/B+q_{2}CB$ is minimised at $B^{\ast }=\sqrt{q_{1}A/(q_{2}C)}$, giving $2\sqrt{q_1{q}_{2}AC}$. Tuning $B$ when the two sides differ is often a 2-3x speedup — rather than trust the formula’s constants exactly, measure: try $B\in \{\sqrt{n}/4,\sqrt{n}/2,\sqrt{n},2\sqrt{n},4\sqrt{n}\}$ and keep the fastest.

$O(\sqrt{n})$ per operation at $n=q=10^5$ is about $3\cdot 10^7$ — comfortable; at $n=10^6$ it’s $10^9$ and usually too slow, which is the concrete version of the "$n,q\le 2\cdot 10^5$" rule of thumb above.

Sqrt rebuilding (buffered updates)

Keep a fast static structure plus a buffer of recent updates. Answer each query from the static structure and correct it by scanning the buffer. Rebuild every $K$ updates. Total: $O(\frac{q}{K}\cdot \text{build}+q\cdot K)$, minimised at $K=\sqrt{\text{build}}$. This makes sorted arrays, convex hulls, Aho-Corasick automata, sparse tables and precomputed DP tables “updatable”.

Heavy/light by a threshold

Objects	Heavy ($>B$)	Light ($\le B$)
values by frequency	at most $n/B$ of them: precompute an answer per heavy value	brute force over their occurrences
vertices by degree	at most $2m/B$: maintain an aggregate at each heavy vertex	iterate over their neighbours
patterns by length	at most $L/B$ distinct long ones: process each separately	short ones: group by length or trie of depth $B$
query ranges by length	answer via precomputation	brute force
moduli in “add to every $i\equiv r(\mathrm{mod}m)$”	$m>B$: touch the $n/m$ positions directly	$m\le B$: keep $\text{add}[m][r]$ and add it at query time

Triangle counting in $O(m\sqrt{m})$: orient each edge from the lower $(\mathrm{deg},\text{id})$ endpoint to the higher one, then for each vertex mark its out-neighbours and scan their out-neighbours.

for (auto [u, v] : edges) (pair(deg[u], u) < pair(deg[v], v) ? g[u] : g[v]).push_back(u ^ v ^ (pair(deg[u], u) < pair(deg[v], v) ? u : v));
for (int u = 0; u < n; u++) {
    for (int v : g[u]) mark[v] = u + 1;
    for (int v : g[u]) for (int w : g[v]) cnt += mark[w] == u + 1;
}

(The first line just appends the higher endpoint to the lower endpoint’s list.)

Proof: out-degrees are $O(\sqrt{m})$ and the total is $O(m\sqrt{m})$

If $u\to v$ then $\mathrm{deg}v\ge \mathrm{deg}u$. Suppose $u$ has out-degree $d$. All $d$ out-neighbours have degree $\ge \mathrm{deg}u\ge d$, so they account for at least $d^2$ edge endpoints, hence $d^2\le 2m$ and $d\le \sqrt{2m}$. The double loop costs ${\sum }_{u\to v}\text{outdeg}(v)\le m\sqrt{2m}$. Each triangle is counted once: orient it acyclically (the orientation is by a total order), and it is found exactly from its lowest vertex.

Distinct weights bound: if positive integer weights sum to $W$, there are at most $\sqrt{2W}$ distinct values (since $1+2+\cdots +k\le W$ forces $k\le \sqrt{2W}$). So subset sum with total $W$ becomes $O(W\sqrt{W})$, or $O(W\sqrt{W}/64)$ with bitsets after binary splitting of multiplicities.

Range mode (online, static array)

Precompute the mode of every block interval $[i,j]$ in $O(n\sqrt{n})$. For a query, start from the middle blocks’ mode $(v,c)$ and try to beat $c$ using elements of the two partial blocks, checking via each value’s sorted position list whether its $(c+1)$-th occurrence from here is still in range.

// pos[v]: sorted positions of v; idx[i]: rank of i inside pos[a[i]]
// left partial block: for i from l upward:   while (idx[i] + c < sz(pos[a[i]]) && pos[a[i]][idx[i] + c] < r) best = a[i], c++;
// right partial block: for i from r-1 down:  while (idx[i] - c >= 0 && pos[a[i]][idx[i] - c] >= l) best = a[i], c++;

Proof: $O(\sqrt{n})$ per query

The middle blocks’ mode is a valid starting candidate, and the true mode either is it or occurs in a partial block. For a value occurring in the left partial block, scanning from its leftmost in-range occurrence and testing the $(c+1)$-th occurrence counts exactly its frequency in $[l,r)$ once it exceeds $c$; occurrences only in the right partial block are handled symmetrically from the right. Each loop step either increases $c$ or moves to the next position. $c$ can grow by at most the number of partial-block elements ($\le 2B$) beyond the middle mode, and there are at most $2B$ positions, so the total is $O(B)=O(\sqrt{n})$.

Sqrt tree

$O(1)$ queries for any associative operation — including non-idempotent ones a sparse table can’t handle, like sum, product mod $p$, matrix product or affine-map composition — with $O(\sqrt{n})$ point updates and $O(n\log \log n)$ memory. Layers of blocks of size $2^{\lceil k/2\rceil }$ store prefix and suffix aggregates within blocks, plus “between” tables of block-interval aggregates. A query $[l,r]$ picks the layer where $l$ and $r$ lie in the same block but different sub-blocks (found from the highest differing bit, like the disjoint sparse table), and combines suffix + between + prefix. It’s rarely needed: a disjoint sparse table is simpler if there are no updates, and a segment tree is simpler if $O(\log n)$ is fine.

Sqrt on time and on trees

• Operation batching: process operations in groups of $K$; inside a group treat the structure as static plus a brute-force pass over the group’s updates; apply the group at its end. This is the “rebuilding” idea indexed by time.
• Tree blocks: cluster the tree into $O(\sqrt{n})$ connected blocks of size $O(\sqrt{n})$ (DFS with a stack, cut when a subtree accumulates $\ge B$ vertices). Mo on trees is usually easier (Mo’s Algorithm).
• Sqrt on depths / on values: split by a threshold depth, or treat values $\le \sqrt{V}$ and $>\sqrt{V}$ differently (for example “for each small modulus keep a table; for big moduli there are few multiples”).