A segment tree gets range-minimum query and
point update both down to O(log n) by building an actual tree over the array. Sqrt
decomposition asks for the same two operations and settles for O(√n) instead — worse,
but the whole structure is one flat array chopped into blocks of about √n elements
each, with no recursion, no odd/even bit-parity walk, and no padding up to the next power of two.
Split the n-element array into blocks of size b, precompute each block's
own minimum once, and a query answers by scanning at most two partial blocks
element-by-element plus reading a run of whole blocks straight out of the precomputed
table, O(1) each. Scanning a partial block costs up to b, and there are
at most n / b whole blocks to read — those two costs trade off against each other, and
they're equal exactly when b = √n, which is where the name comes from.
The array below has 8 values, indexed 0 through 7, split into blocks of size
b = 3 (the standard choice, ⌈√8⌉ = 3): block 0 covers indices 0-2, block
1 covers 3-5, and block 2 — shorter than the rest, since 8 doesn't divide evenly by 3 — covers just
6-7. The row below the values shows each block's precomputed minimum. Pick an index and a new
value and press Set to update, or pick a range and press Query Min,
then step through to see exactly which elements get scanned one at a time and which whole blocks
get read directly from the precomputed row.
On the default array [5, 2, 8, 1, 9, 3, 7, 4]: block 0 owns indices 0-2
([5, 2, 8], min 2), block 1 owns indices 3-5 ([1, 9, 3], min 1), and
block 2 owns indices 6-7 ([7, 4], min 4) — only two elements, because a block's real
size is always min(b, n - blockStart), not a fixed b. Querying
min over [1, 5] walks index by index but jumps whenever it can:
index 1 doesn't start a whole block that fits inside [1, 5] (block 0 actually starts
at index 0), so it's scanned directly (value 2); same for index 2 (value 8, running result
min(2, 8) = 2); but index 3 does start block 1, and block 1's own range
[3, 5] fits entirely inside the query, so the walk takes block 1's precomputed minimum
directly — min(2, 1) = 1 — and jumps straight to index 6, past the whole block in one
step instead of three. Index 6 is past the query's own end (5), so the walk stops. Final answer:
1, checked directly against a plain scan of values[1..5] after every
query in the demo above.
Updating works the other way: change one element, and only the one block that
owns it can possibly have a new minimum, so recompute just that block from scratch. Setting index 3
to 6 changes block 1's underlying values to [6, 9, 3], so block 1's minimum moves from
1 to 3 — but block 0 and block 2 are untouched, both in their stored values and in their
precomputed minimums, since index 3 doesn't live in either of them. That's the real shape of a
sqrt-decomposition update: not "touch one cell," the way a Fenwick or segment tree leaf update
works, but "rescan one whole block of about √n elements" — cheap because a block is
small, not because the touched cell is handled in isolation.
One flat array of values, one smaller array of per-block minimums, and two loops — no tree, no recursion:
class SqrtDecomposition {
constructor(values, blockSize) {
this.values = values.slice();
this.n = values.length;
this.bs = blockSize;
this.numBlocks = Math.ceil(this.n / this.bs);
this.blockMin = new Array(this.numBlocks);
for (let b = 0; b < this.numBlocks; b++) this.recomputeBlock(b);
}
blockRange(b) { // half-open [start, end); last block may be shorter than bs
const start = b * this.bs;
const end = Math.min(this.n, start + this.bs);
return [start, end];
}
recomputeBlock(b) {
const [start, end] = this.blockRange(b);
let m = Infinity;
for (let i = start; i < end; i++) m = Math.min(m, this.values[i]);
this.blockMin[b] = m;
}
update(i, val) {
this.values[i] = val;
this.recomputeBlock(Math.floor(i / this.bs)); // only this one block can have changed
}
queryMin(l, r) { // inclusive range [l, r]
let res = Infinity;
let i = l;
while (i <= r) {
const b = Math.floor(i / this.bs);
const [start, end] = this.blockRange(b);
if (start === i && end - 1 <= r) {
res = Math.min(res, this.blockMin[b]); // whole block fits — O(1) from the table
i = end;
} else {
res = Math.min(res, this.values[i]); // partial block — scan one element
i++;
}
}
return res;
}
}Verified against a naive O(n) scan over 20,000 randomized trials (random array
sizes 1-30, random block sizes, a mix of random updates and random-range queries interleaved) with
zero mismatches, plus the specific default-demo numbers above traced by hand first.
The update cost genuinely depends on the operation, unlike Fenwick or segment tree.
Both of those touch a fixed O(log n) nodes on every update no matter what operation
they're combining. Sqrt decomposition's update cost is different for sum than for min, and the
reason is the same invertibility split Fenwick
Tree is built around: for sum, changing one element by some delta changes the
owning block's total by that exact same delta — blockSum[b] += (newVal - oldVal),
genuinely O(1), no rescan needed. For min (what this page's demo
implements), there's no inverse operation that undoes "this element used to be part of the min" —
if the old value happened to be the block's minimum, the only way to find the new minimum is to
recheck every element in the block, O(b). Reusing this page's own update code for a
sum-decomposition and expecting the same O(1) shortcut to just work would silently
leave the delta-update optimization on the table, not break correctness — the full block rescan
above is always correct, for any operation, min or sum alike, just needlessly slow for the
invertible case.
The last block is short — don't assume every block has exactly b
elements. With n = 8 and b = 3, block 2 only owns 2 elements.
blockRange above clamps end to this.n for exactly this
reason; an implementation that instead always adds a fixed b to a block's start would
read past the end of the array on the final block whenever b doesn't divide
n evenly — which is the common case, not the exception.
Time: O(√n) for both update and queryMin
when b ≈ √n. A query scans at most two partial blocks (up to 2b elements)
and reads at most n / b whole blocks at O(1) each; those two terms,
b and n / b, are minimized together exactly when they're equal, at
b = √n, giving O(√n) + O(√n) = O(√n) — a smaller or larger block size
still works correctly, just trades one term for the other rather than shrinking the total. An
update rescans one whole block, O(b) = O(√n). Building from an existing array is
O(n), one pass computing each block's minimum. Space: O(n)
for the values plus O(n / b) = O(√n) for the block-minimum table — smaller, not
larger, than a segment tree's own overhead.
Asymptotically this loses to Segment Tree and
Fenwick Tree's O(log n) on both
operations — for a million elements, √n is about 1,000 against log₂ n's
20. What it buys instead is a flat array and two straight loops, no tree at all, which makes it a
natural base to extend with a per-block operation more elaborate than "recompute the minimum" —
a whole class of "batch queries by which block they touch" techniques builds directly on this
same block-boundary idea.
This site's guide, Choosing a Range Query Structure, compares this entry against the other five Array-Backed Trees structures that answer the same range-query question side by side.