Sqrt Tree — Mathematical Foundations and Complexity Theory¶

Let (M, ⊕) be a semigroup: M a set, ⊕ : M × M → M an ASSOCIATIVE binary operation,
i.e. for all a, b, c ∈ M:  (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c).
(No identity element and no idempotence are assumed.)

Let A = (A[0], A[1], ..., A[n-1]) ∈ M^n be a fixed array.

For 0 ≤ l ≤ r < n define the range product:
    Q(l, r) = A[l] ⊕ A[l+1] ⊕ ... ⊕ A[r].
By associativity this is well-defined independent of parenthesization.

A SQRT TREE over A is a recursively defined family of layers {T_t}.
Layer 0 owns the segment [0, n-1]. A layer node owning segment [lo, hi] of
length len = hi - lo + 1:
  - chooses block size  s = 2^{⌈b/2⌉}  where b = ⌈log2 len⌉  (so s ≈ √len),
  - partitions [lo, hi] into B = ⌈len / s⌉ blocks  G_0, G_1, ..., G_{B-1},
  - stores, for each position i in block G_g with block range [g_lo, g_hi]:
        pref[i] = A[g_lo] ⊕ ... ⊕ A[i]        (prefix within the block)
        suf[i]  = A[i] ⊕ ... ⊕ A[g_hi]        (suffix within the block)
  - stores a BETWEEN table:
        bet[a][c] = (⊕ over all elements of blocks G_a, G_{a+1}, ..., G_c),  a ≤ c,
  - and recursively builds a layer-(t+1) node for each block G_g, until len ≤ 2
    (the base case, handled by direct scan).

Invariant I: at every layer node, pref, suf, and bet equal the products above,
computed under ⊕ (well-defined by associativity).

Claim. For any query (l, r) with l < r, let t* be the smallest layer index such
that, in the node of layer t* owning a segment containing [l, r], positions l and
r fall in DIFFERENT blocks G_p (containing l) and G_q (containing r), p < q. Then

    Q(l, r) = suf[l]  ⊕  ( ⊕ over blocks G_{p+1}..G_{q-1} )  ⊕  pref[r]
            = suf[l]  ⊕  bet[p+1][q-1]  ⊕  pref[r]           (when q > p+1)
            = suf[l]  ⊕  pref[r]                              (when q = p+1).

Proof. Let block G_p span [p_lo, p_hi] and block G_q span [q_lo, q_hi]. Since l ∈ G_p
and r ∈ G_q with p < q, we have p_lo ≤ l ≤ p_hi < q_lo ≤ r ≤ q_hi. The index set
[l, r] partitions into three CONSECUTIVE, DISJOINT runs:

    R1 = [l, p_hi]            (suffix of block p)
    R2 = [p_hi+1, q_lo-1]     (exactly the whole blocks G_{p+1} ... G_{q-1})
    R3 = [q_lo, r]            (prefix of block q)

These satisfy R1 ⊎ R2 ⊎ R3 = [l, r] (disjoint union, in increasing order). By the
generalized associativity law (a product of a sequence is independent of how it is
parenthesized, as long as order is preserved):

    Q(l, r) = (⊕ over R1) ⊕ (⊕ over R2) ⊕ (⊕ over R3).

By definition of the stored tables:
    ⊕ over R1 = A[l] ⊕ ... ⊕ A[p_hi] = suf[l],
    ⊕ over R2 = bet[p+1][q-1]  (empty, omitted, when q = p+1),
    ⊕ over R3 = A[q_lo] ⊕ ... ⊕ A[r] = pref[r].

Substituting gives the claim. ∎

Claim. The number of layers D satisfies D = Θ(log log n).

Proof. Track the bit-length of the segment size. Layer 0 has b_0 = ⌈log2 n⌉.
A layer with bit-length b uses block size s = 2^{⌈b/2⌉}, so each block has
bit-length ⌈b/2⌉. Hence the recurrence for bit-length across layers is

    b_{t+1} = ⌈b_t / 2⌉,    starting from b_0 = ⌈log2 n⌉.

Halving (with ceiling) reaches b = 1 after exactly ⌈log2 b_0⌉ steps:

    D = ⌈log2 b_0⌉ = ⌈log2 ⌈log2 n⌉⌉ = Θ(log log n).

Lower bound: b_{t} ≥ b_0 / 2^t, so to reach b_t = O(1) we need t ≥ log2 b_0 - O(1),
giving D = Ω(log log n). Upper bound from the closed form above. Hence Θ(log log n). ∎

Claim. Build time and space are both O(n log log n).

Proof (per-layer accounting). Fix a layer t. Its nodes partition [0, n-1] into
segments whose total length is exactly n (each array index belongs to exactly one
segment at layer t).

(a) Prefix and suffix. Within each segment, every position receives exactly one
    pref and one suf value, each computed with one ⊕ from an adjacent position.
    Total over the whole layer: ≤ 2n applications of ⊕ and ≤ 2n stored cells.  → O(n).

(b) Between table. A segment of length len has B = ⌈len / s⌉ ≈ √len blocks, so its
    between table has at most B(B+1)/2 = O(B²) = O(len) cells, each filled in O(1)
    by extension  bet[a][c] = bet[a][c-1] ⊕ (block c aggregate).
    Summed over all segments of layer t (whose lengths sum to n):
        Σ_segments O(len_segment) = O(n).   → O(n).

So each layer costs O(n) time and O(n) space. With D = Θ(log log n) layers:

    Build time  = Σ_{t=0}^{D-1} O(n) = O(n · D) = O(n log log n).
    Build space = Σ_{t=0}^{D-1} O(n) = O(n log log n).
∎

Layer 0: b = 4, block size s = 2^⌈4/2⌉ = 4, blocks B = 16/4 = 4, segment len = 16.
  prefix/suffix cells: 16 + 16 = 32.
  between cells: B(B+1)/2 = 4·5/2 = 10.   (NOT 16² = 256 — it is O(B²)=O(len).)
  layer-0 total cells: 32 + 10 = 42.

Layer 1: each of the 4 blocks is a segment of len 4, b = 2, s = 2^⌈2/2⌉ = 2, B = 2.
  per segment: prefix/suffix 4 + 4 = 8; between 2·3/2 = 3 → 11 cells.
  four segments: 4 · 11 = 44 cells.

Layer 2: segments of len 2 → base case (len ≤ 2), no further tables.

Depth D = ⌈log2 b_0⌉ = ⌈log2 4⌉ = 2 layers (0 and 1). ✓ matches Θ(log log n).
Total cells: 42 + 44 = 86 ≈ 5.4 n, consistent with O(n · D) = O(16 · 2) = O(32)
up to the small constant from prefix+suffix+between per layer.

Observation. Under bit-length-b geometry, indices x, y (within a segment of
bit-length b) lie in DIFFERENT blocks iff they differ in some bit position ≥ ⌈b/2⌉,
i.e. iff  msb(x XOR y) ≥ ⌈b/2⌉,  where msb(z) is the index of the most significant
set bit of z.

Construction. For each possible value h = msb(l XOR r) ∈ {0, 1, ..., b_0 - 1},
precompute the layer at which a pair whose top differing bit is h first separates:

    onLayer[h] = the unique layer t such that  ⌈b_t / 2⌉ ≤ h < b_t,
    where b_0 = ⌈log2 n⌉ and b_{t+1} = ⌈b_t / 2⌉.

This is filled by walking the b_t sequence once (O(log n) work), assigning each
bit position h to the layer whose half-range [⌈b_t/2⌉, b_t) contains it.

Claim. A query (l, r) is answered in O(1) time.

Proof. The work is: (i) select the layer t* at which l and r first lie in different
blocks; (ii) read at most three precomputed cells; (iii) apply ⊕ at most twice.
Steps (ii) and (iii) are O(1) by inspection. It remains to show (i) is O(1).

The layer at which (l, r) separates is determined ENTIRELY by the bit-length of
(l XOR r) at the top-level coordinate system, because two indices fall in different
blocks of bit-length-b geometry iff they differ in some bit ≥ ⌈b/2⌉. Concretely,
build a table onLayer[·] mapping the bit-length of the distance/most-significant
differing bit of (l XOR r) to the corresponding layer index. This table has size
O(log n), is precomputed in O(log n) during build, and is read in O(1):

    t* = onLayer[ msb(l XOR r) ]            // O(1) lookup

Given t*, the block indices p = blockOf_{t*}(l), q = blockOf_{t*}(r) are computed by
a shift (O(1)), and the three-piece combine (Section 2) is applied. No descent loop
is executed. Therefore total query time is O(1). ∎

Claim. After build(layer, lo, hi) returns, for the segment [lo, hi] at this layer:
    pref[i] = A[g_lo] ⊕ ... ⊕ A[i]   for every i in its block [g_lo, g_hi],
    suf[i]  = A[i] ⊕ ... ⊕ A[g_hi],
    bet[a][c] = (⊕ over blocks G_a..G_c),
and all child layer nodes satisfy the same (by recursion).

Proof.
PREFIX. For each block, the loop sets pref[g_lo] = A[g_lo], then for j from g_lo+1 to
g_hi sets pref[j] = pref[j-1] ⊕ A[j].
  Invariant P(j): pref[j] = A[g_lo] ⊕ ... ⊕ A[j].
  Base j = g_lo: pref[g_lo] = A[g_lo]. ✓
  Step: assume P(j-1). Then pref[j] = pref[j-1] ⊕ A[j]
       = (A[g_lo] ⊕ ... ⊕ A[j-1]) ⊕ A[j] = A[g_lo] ⊕ ... ⊕ A[j]  (associativity). ✓
  Termination: j increases by 1 each step, bounded by g_hi. Establishes pref for the block.

SUFFIX. Symmetric, scanning right-to-left: suf[g_hi] = A[g_hi], suf[j] = A[j] ⊕ suf[j+1].
  Invariant S(j): suf[j] = A[j] ⊕ ... ⊕ A[g_hi], proven by the mirror induction.

BETWEEN. For fixed a, the loop sets bet[a][a] = (block a aggregate) = suf[block_a_lo],
then bet[a][c] = bet[a][c-1] ⊕ (block c aggregate) for c > a.
  Invariant Bw(c): bet[a][c] = ⊕ over blocks G_a..G_c.
  Base c = a: bet[a][a] = aggregate of G_a (the whole block product, = suf at its left
              edge, already established). ✓
  Step: assume Bw(c-1). bet[a][c] = bet[a][c-1] ⊕ (G_c aggregate)
       = (⊕ blocks G_a..G_{c-1}) ⊕ (⊕ G_c) = ⊕ blocks G_a..G_c  (associativity). ✓

RECURSION. After the tables of this layer are filled, build recurses on each block,
establishing the invariant one layer deeper. The recursion terminates because segment
length strictly decreases (len → ≈ √len) and bottoms out at len ≤ 2. ∎

Claim. A point update A[i] ← v takes O(√n) time.

Proof. Changing A[i] invalidates, at each layer t, only the unique block of layer t
that contains i (and the between entries of its parent segment that include that
block). Let s_t be the block size at layer t, with s_0 = Θ(√n) and s_{t+1} = Θ(√s_t).

(a) Recomputing the affected block's prefix and suffix at layer t costs O(s_t).
(b) Recomputing the between row and column for that block in its parent segment costs
    O(B_t) where B_t = Θ(√len_t) is the block count; at layer 0, B_0 = Θ(√n).

The costs across layers form a decreasing geometric-in-the-exponent series:

    O(s_0) + O(s_1) + ... = O(√n) + O(n^{1/4}) + O(n^{1/8}) + ...  = O(√n),

dominated by the layer-0 term. Adding the between-recomputation, also O(√n) at
layer 0 and smaller below, the total remains O(√n). ∎

Potential / aggregate view. Suppose m point updates fall within the same layer-0
block before the next query. A naive implementation rebuilds that block's structures
m times, each O(√n), for O(m√n) work. A lazy variant defers the rebuild: mark the
block dirty, and rebuild it once (O(√n)) at the next query that touches it.

Aggregate cost of a mixed sequence of u updates and q queries with lazy rebuild:
    total ≤ (u + q) · O(√n)   for the dirty-block rebuilds (each block rebuilt at most
    once per query-epoch), plus q · O(1) for the query combines.
So the amortized cost per operation stays O(√n) for updates and O(1) for queries even
under clustered update bursts — provided rebuilds are coalesced. This is the formal
backing for the senior-level advice to BATCH updates and rebuild once.

Theorem. The Sqrt Tree query (Section 2) is correct for every SEMIGROUP (M, ⊕),
with no assumption of idempotence (∀x: x ⊕ x = x) or of an identity element.

Proof. The query combines the products over R1, R2, R3, which form a DISJOINT
partition of [l, r] in increasing order (Section 2). Generalized associativity
states: for any sequence x_1, ..., x_m ∈ M, the product x_1 ⊕ ... ⊕ x_m is
independent of parenthesization. Splitting the sequence A[l], ..., A[r] at the two
cut points l..p_hi | p_hi+1..q_lo-1 | q_lo..r is one valid parenthesization, so the
combined result equals Q(l, r). No element is repeated (disjointness), so no term
x ⊕ x ever appears that would require idempotence to collapse. ∎

Contrast (sparse table). A sparse-table query on [l, r] combines two windows
W_A = [l, l + 2^k - 1] and W_B = [r - 2^k + 1, r] with k = ⌊log2(r-l+1)⌋. Since
2·2^k ≥ r - l + 1, W_A ∩ W_B ≠ ∅ in general (they OVERLAP). The combine
(⊕ over W_A) ⊕ (⊕ over W_B) counts the overlap region's product TWICE. This equals
Q(l, r) iff ⊕ is idempotent on that product (so the duplicate collapses). Hence
sparse table REQUIRES idempotence; Sqrt Tree does not. ∎

Lemma (Generalized Associativity). Let (M, ⊕) be a semigroup and x_1, ..., x_m ∈ M,
m ≥ 1. Every full parenthesization of the expression x_1 ⊕ x_2 ⊕ ... ⊕ x_m yields the
same element of M. Define this common value as the product P(x_1, ..., x_m).

Proof (induction on m). 
Base m = 1, m = 2: trivial (one parenthesization).
Inductive step: assume the lemma for all sequences shorter than m. Any full
parenthesization of x_1..x_m has an outermost ⊕ splitting it as
P(x_1..x_k) ⊕ P(x_{k+1}..x_m) for some 1 ≤ k < m. By the induction hypothesis each
factor is well-defined regardless of inner parenthesization. It remains to show the
value is independent of the split point k. Take two splits k and k' with k < k'.
Using the (single) associativity axiom repeatedly,
   P(x_1..x_k) ⊕ P(x_{k+1}..x_m)
 = P(x_1..x_k) ⊕ ( P(x_{k+1}..x_{k'}) ⊕ P(x_{k'+1}..x_m) )
 = ( P(x_1..x_k) ⊕ P(x_{k+1}..x_{k'}) ) ⊕ P(x_{k'+1}..x_m)
 = P(x_1..x_{k'}) ⊕ P(x_{k'+1}..x_m),
where the middle step is one application of associativity and the outer P-merges use
the induction hypothesis. Hence all split points give equal values. ∎

Parameters (external-memory / ideal-cache model): M = cache size (words),
B = block (cache line) size in words, n = array length.

Query I/O cost. A query reads: the onLayer table (1 line, cached after warmup),
suf[t*][l], pref[t*][r], and one between cell. These are ≤ 3 distinct addresses in
≤ 3 cache lines. Hence query cost is O(1) cache misses — independent of n.
Compared to a segment tree, whose root-to-leaf descent touches Θ(log n) nodes on
Θ(log n) distinct (poorly localized) cache lines, Sqrt Tree's O(1) line count is a
genuine memory-hierarchy advantage at scale.

Build I/O cost. Each layer streams its segments linearly to fill prefix (forward) and
suffix (backward) and the between table (forward over block aggregates). Linear scans
incur O(layer_size / B) misses, so a layer costs O(n / B) and the whole build costs
O((n / B) · log log n) cache misses — near-optimal streaming behavior.

Layout note. Storing each layer's prefix, suffix, and (flattened) between in
contiguous arrays makes the build sequential and the query's three reads land in few
lines. A slice-of-slices ("pointer-to-pointer") layout degrades both — hence the
senior-level recommendation to flatten the between table.

Some implementations skip the onLayer table and instead descend layer-by-layer until
l and r separate. We bound this variant to show it is still O(log log n) worst case,
and O(1) for the common case.

Claim. The descent visits at most D = Θ(log log n) layers.
Proof. Each descent step moves from a layer to one of its child layers (only when l, r
share a block). There are D layers total, so the descent length is ≤ D = Θ(log log n). ∎

Refinement. The descent only continues while l and r are in the SAME block. The number
of consecutive same-block layers equals the number of leading shared high bits of
(l, r) within the bit-length geometry, which for "typical" queries is small (often 0,
i.e. they separate at layer 0). So the descent is O(1) in the common case and
O(log log n) worst case. The onLayer table (Section 6) removes even this small worst
case, yielding a guaranteed O(1). Either way, the per-query work is at most
O(log log n) ⊕-operations — already strictly better than a segment tree's Θ(log n).

Context. For STATIC range-semigroup queries, the relevant theoretical landscape is:

  - Yao (1982) and later work show that in the semigroup arithmetic model, n
    preprocessed values supporting O(1) range queries require Ω(n α(n)) cells in the
    worst case for some operations (α = inverse Ackermann), and that truly O(1)
    query with O(n) space is impossible for general semigroups in this model.
  - Sqrt Tree's Θ(n log log n) space with Θ(1) query is therefore NOT space-optimal
    (the theoretical frontier is closer to O(n α(n)) via more intricate structures),
    but it is a simple, practical point on the trade-off curve that beats sparse
    table's Θ(n log n) and achieves Θ(1) query.
  - For IDEMPOTENT operations, Θ(n)-space Θ(1)-query RMQ exists (Fischer–Heun 2007),
    strictly better than both sparse table and Sqrt Tree — but it does NOT extend to
    non-idempotent semigroups, which is exactly Sqrt Tree's domain.

Takeaway. Sqrt Tree is not the theoretical optimum for either axis, but it is the
standard, implementable structure delivering Θ(1) queries for NON-IDEMPOTENT
semigroups with sub-(n log n) space — a niche the optimal idempotent structures and
the sparse table do not cover.

For the DYNAMIC version (supporting both queries and updates), cell-probe lower bounds
(Pătraşcu–Demaine and successors) show that for prefix-sum / range-sum over a group,
any structure must satisfy  t_query · t_update = Ω(log n)  in the cell-probe model.
Sqrt Tree's (t_query, t_update) = (O(1), O(√n)) gives a product O(√n), which is far
from this Ω(log n) frontier — meaning Sqrt Tree is NOT on the optimal dynamic
trade-off curve. A balanced segment tree at (O(log n), O(log n)) has product
O(log² n), closer to optimal for balanced workloads. This is the formal reason Sqrt
Tree is a STATIC-leaning structure: it deliberately trades a slow O(√n) update for a
fast O(1) query, which only pays off when queries dominate updates by a factor ≫ √n.