Disjoint Sparse Tables achieve 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 , divide the array into blocks of size . For each block, compute prefix from the middle to left and suffix from middle to right.
Query: find the level where and are in different halves of the same block. Combine the precomputed prefix/suffix. Construction: . Query: . This structure is more complex but handles sum, product, and other non-idempotent operations in constant time.