Sparse Table

Sparse tables allow us to answer an answer any minimum/maximum query in time after time preprocessing method.

The main idea behind Sparse Tables is to precompute all answers for range queries with power of two length.

I think I finally start to get it! I will use the function as template, but you can easily apply it to and , and even SUM (but you need to be careful with the query logic since you cannot overlap).

Building the Table   will store the answer starting at and of length , thus the range  (we can also write .

To build the table, we use DP and construct (of length ) from the two smaller arrays of size (which we have already computed):

So how big should the sparse table be? st[MAXN][K+1]

• MAXN N+1 ?
• For arrays with reasonable length ( elements),  is a good value, since Trick to remember, K+1 = 26 letters in the alphabet

Answering Queries Range query can be answered by splitting the range into ranges with power of two lengths, looking up the precomputed answers, and combining them to receive a complete answer.

For Range minimum/maximum/gcd/lcm query, you can just do this step once, splitting it into two ranges, because overlapping ranges do not affect the answer (IMPORTANT: this is NOT the case for sum queries).

So we can compute the minimum of the range  with:

This requires that we are able to compute  fast. You can accomplish that by precomputing all logarithms.