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.

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

1 Answer 1


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]$,




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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.