Disjoint Sparse Tables

Disjoint Sparse Tables achieve $O(1)$ range queries for ANY associative operation, not idempotent ones.

The idea: instead of overlapping ranges, use non-overlapping decomposition. Precompute answers for ranges that share a midpoint.

For each level $j$, divide the array into blocks of size $2^j$. For each block, compute prefix from the middle to left and suffix from middle to right.

Query: find the level where $l$ and $r$ are in different halves of the same block. Combine the precomputed prefix/suffix. Construction: $O(n \log n)$. Query: $O(1)$. This structure is more complex but handles sum, product, and other non-idempotent operations in constant time.