# Range queries with O(N log N) build and O(1) query

I read somewhere that you can compute range queries in O(1) with O(N log N) preprocessing for any associative operation (but not necessarily invertible or idempotent). How do you do this?

I know this is possible for range min and range sum. But both of these are special because min is idempotent and sum is invertible.

• Range query is at least $\Omega(K)$ where $K$ is the number of keys found.
– user16034
Commented Feb 9, 2023 at 11:41

Sparse Tables

For each index i of array, we store minimum of blocks of 2 powers till block index's doesn't exceed array length.

Any non-negative number can be uniquely represented as a sum of decreasing powers of two. This is just a variant of the binary representation of a number.

E.g. $$13 = (1101)_2 = 8 + 4 + 1$$.

E.g. $$[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$$,

https://discuss.codechef.com/t/tutorial-disjoint-sparse-table/17404

https://cp-algorithms.com/data_structures/sparse-table.html

https://github.com/e-maxx-eng/e-maxx-eng/blob/master/src/data_structures/sparse-table.md

Edit: Updating with codechef's link for handling general associativity, thanks D.W.