Sqrt Tree

Static range query for ANY associative op in O(1): split into √n blocks, precompute prefix / suffix / between, combine at most three disjoint pieces. Works for non-idempotent ops (sum, product, xor) that a sparse table cannot.

Query: O(1) Build: O(n log log n) Space: O(n log log n) Update: O(√n) Associative op (idempotence NOT required)

op:

Query range:

slow fast

input arr building suffix (piece 1) between (piece 2) prefix (piece 3) block boundary

Input array (split into √n blocks)

prefix[i] = op(blockStart .. i) | per block, left to right

suffix[i] = op(i .. blockEnd) | per block, right to left

between[bi][bj] = op over whole blocks bi..bj

Current step

Load an array, pick an op, then click "Animate Build". A spanning query then combines at most three precomputed pieces in O(1).

block size0

blocks0

layers (log log n)0

build ops0

last query-

query combines0

Operation	Sqrt Tree	Sparse Table	Segment Tree	Flat Sqrt
Query	O(1)	O(1)	O(log n)	O(√n)
Build	O(n log log n)	O(n log n)	O(n)	O(n)
Space	O(n log log n)	O(n log n)	O(n)	O(n)
Update	O(√n)	rebuild	O(log n)	O(√n)
Non-idempotent (sum/product/xor)	yes	no	yes	yes

A spanning query op(arr[l..r]) = suffix of l's block ⊕ between middle blocks ⊕ prefix of r's block. The three pieces are disjoint, so there is no double-counting — only associativity is required (not idempotence). A within-block query recurses into that block's own Sqrt Tree (log log n layers deep).