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.


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, privacy policy and cookie policy

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