Disjoint Sparse Table

$O(1)$ range queries for any associative operation on a static array — not just idempotent ones. $O(n\log n)$ build and memory.

The problem it fixes

A plain sparse table answers a query with two overlapping blocks, which double-counts unless the operation is idempotent. Sums, products and XOR are therefore out.

The disjoint sparse table instead covers every query with exactly two adjacent, non-overlapping blocks.

The construction

At level $k$, split the array into blocks of length $2^{k+1}$. Within each block, compute:

• suffix aggregates from the block’s midpoint leftward,
• prefix aggregates from the midpoint rightward.

$\mathrm{table}[k][i]=\{\begin{array}{ll}\mathrm{op}(a_i,\mathrm{table}[k][i+1])& i<\text{mid}\\ \mathrm{op}(\mathrm{table}[k][i-1],a_i)& i\ge \text{mid}\end{array}$

To answer $[l,r]$: find the highest bit where $l$ and $r$ differ, $k=\lfloor {\log }_2(l\oplus r)\rfloor$. At that level, $l$ and $r$ lie in the same block but on opposite sides of its midpoint, so

$\mathrm{query}(l,r)=\mathrm{op}(\mathrm{table}[k][l],\mathrm{table}[k][r]).$

int table_[LOG][MAXN], lg[MAXN];
 
void build(vector<int>& a) {
    int n = a.size();
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;
    for (int k = 0; (1 << k) < n; k++) {
        int half = 1 << k, len = half << 1;
        for (int mid = half; mid < n + half; mid += len) {
            table_[k][mid - 1] = a[mid - 1];
            for (int i = mid - 2; i >= mid - half && i >= 0; i--)
                table_[k][i] = op(a[i], table_[k][i + 1]);           // suffix
            if (mid < n) table_[k][mid] = a[mid];
            for (int i = mid + 1; i < min(n, mid + half); i++)
                table_[k][i] = op(table_[k][i - 1], a[i]);           // prefix
        }
    }
}
 
int query(int l, int r) {                    // inclusive, l < r
    if (l == r) return a[l];
    int k = lg[l ^ r];
    return op(table_[k][l], table_[k][r]);
}

Handle $l=r$ separately — the XOR trick needs two distinct indices.

Why the XOR trick works

$k=\lfloor {\log }_2(l\oplus r)\rfloor$ is the highest bit where $l$ and $r$ differ. That means they agree on all higher bits, so they fall inside the same length-$2^{k+1}$ block, and they differ at bit $k$, so they lie on opposite sides of that block’s midpoint. Exactly the configuration the table was built for.

Comparison

Structure	Build	Query	Operation	Memory
Prefix sum	$O(n)$	$O(1)$	invertible only	$O(n)$
Sparse table	$O(n\log n)$	$O(1)$	idempotent only	$O(n\log n)$
Disjoint sparse table	$O(n\log n)$	$O(1)$	any associative	$O(n\log n)$
Segment tree	$O(n)$	$O(\log n)$	any associative	$O(n)$

The niche is narrow but real: static array, non-idempotent operation, and enough queries that $O(\log n)$ per query hurts.

When it earns its place

• Range product mod $m$ where $m$ is not prime (so prefix products with inverses fail)
• Range matrix product — associative but expensive, so avoiding the $\log$ factor matters
• Range “merge” of a custom monoid — maximum subarray sum over a range, for example
• $10^7$ queries on a static array where a segment tree’s $\log n$ would dominate

The alternative worth knowing

If updates are never needed and the operation is associative, you can also answer queries offline by sorting them and sweeping — often simpler. And a segment tree at $O(\log n)$ per query is fast enough for almost every contest constraint. Reach for a disjoint sparse table only when profiling says the log factor is the bottleneck.

See also: Sparse Table · Segment Tree · Range Query Techniques