Sqrt Tree

Given an array a[0..n) and an associative operation ∘

(x ∘ y) ∘ z = x ∘ (y ∘ z)

(+, min, max, gcd, AND, OR, XOR, …), answer range folds

q(l, r) = a[l] ∘ a[l+1] ∘ ⋯ ∘ a[r]

A sqrt tree does this in O(1) per query after O(n log log n) preprocess and memory — including ops that are not idempotent (unlike the two-overlap sparse-table RMQ trick).

This lesson follows CP-Algorithms — Sqrt Tree.

Related: Sparse Table.

One level: sqrt decomposition

Split into ≈ √n blocks of size ≈ √n. In each block store:

• prefixOp — folds that start at the block start
• suffixOp — folds that end at the block end

Plus between[i][j] (i ≤ j) — fold of full blocks i…j (size O((√n)²) = O(n)).

All of that builds in O(n) for one layer.

Example (∘ = +, a = {1..9}): blocks {1,2,3}, {4,5,6}, {7,8,9}.

Block	prefixOp	suffixOp
0	{1,3,6}	{6,5,3}
1	{4,9,15}	{15,11,6}
2	{7,15,24}	{24,17,9}

between = [[6, 21, 45],
           [0, 15, 39],
           [0,  0, 24]]

A query that spans blocks splits into three pieces:

suffixOp (partial first block)  ∘  between[…]  ∘  prefixOp (partial last block)

Queries inside one block are not covered yet.

Make a tree

Build the same structure recursively inside each block until length is 1 or 2 (answer in O(1)).

• Node for length k has ≈ √k children.
• Height: log √k = (log k)/2 → O(log log n) layers.
• Each index appears once per layer → build/memory O(n log log n).

Naively walk down until the query no longer lies in a single child → O(log log n) per query.

O(1) queries

Pad n to a power of two; force equal power-of-two block sizes on each layer.

Indices in one block of size 2^k differ only in the lowest k bits. So l and r lie in the same block iff

(l xor r) < 2^k

Precompute highest set bits / layer maps (clz, onLayer). For q(l,r) read the highest bit of l xor r, jump to a suitable layer, then combine suffix ∘ between ∘ prefix in O(1).

Updates

Operation	Naive	Optimized
Point assign	Rebuild between on root → O(n)	Replace root between by an unindexed sqrt-tree index over block answers → point update O(√n), queries still O(1)
Range assign	—	Lazy tags: (1) massUpdate O(√n log log n), query O(1); or (2) massUpdate O(√n), query O(log log n)

Indexed tree: only the root has index; deeper nodes keep between.

🧪 One-layer sqrt decomp (sum) + in-block scan

Full O(1) SqrtTree sketch

Implement op, pad layers with log2Up, maintain pref / suf / between (or root index), map onLayer[clz[l xor r]], then:

// ans = suf[layer][l]
// ∘ between / index on full middle blocks
// ∘ pref[layer][r]
SqrtTreeItem query(int l, int r);
void update(int x, SqrtTreeItem item); // O(√n) with index

Complete listing: CP-Algorithms Sqrt Tree.

Check: sqrt tree

Quiz

Sqrt tree

1 / 5

Sqrt trees need the operation to be…

Pick an answer to see if you are right.

Practice drills

Activity: Block id

Input: i B (0-based index, block size). Print i // B.

Practice problems

From CP-Algorithms:

• CodeChef — SEGPROD

Cheat sheet

Piece	Role
prefixOp / suffixOp	Intra-block ends
between / index	Full block ranges
Recursion	Handle in-block queries
Height	O(log log n)
Build	O(n log log n)
Query	O(1) with bit layer pick
Point update	O(√n) if indexed
vs sparse table	Works for non-idempotent ∘