## § Sparse table

• Given an array as :: Semilattice a => [a], find semilattice join of any range [lft..rt] in O(1) time, given O(n log n) preprocessing.
• Core idea: store results of queries [lft..l+2^k). So the code:
// mins [l, l+1) = arr[l]
for(int i = 0; i < n; ++i) { mins[i] = arr[l]; }
for(int len = 1; len < NBITS; ++len) {
for(int i = 0; i < n; ++i) {
const int midix = i + 1 << (len-1);
if (midix >= n) { break; }
// mins [l..l+N) = min mins[l..l+N/2) mins[l+N/2..l+N]
mins[i][l] = min(mins[i][len-1], mins[i + midix][len-1]);
}
}

• Now given a query, the "naive" method is to consider the range [lft, l+len). We break len down into its powers of 2, and then query the indexes based on its binary representation. Eg. a query from [3, 3+7) is broken down into 7 = 4 + 2 + 1, so we query [3, 3+4) which is [3, 7), then [3+4, 3+4+2) which is [7, 9), and finally [3+4+2, 3+4+2+1) which is [9, 10). But this is O(log n) time. We want O(1) time.
    [--------------)
1 2 3 4 5 6 7 8 9 10
|       |   |  |
[-------)   |  |
[---)  |
[--)

• The key is to notice that so far, we've only used associatvity of the lattice operation, not idempotence! We can exploit idempotence by not caring about overlaps .
• to find min in [3, 9), we combine [3, 3+4) with [9-4, 9), which is [3, 7) combined with [6, 9) which overlaps at 6.
    [-----------)
1 2 3 4 5 6 7 8 9
|     | |   |
[-----+-)   |
[-----)

The actual expression is:
// [l, r)
int query_mins(int l, int r) {
int len = r-l;
if (len < 0) { return INFTY; }
int j = log2(len); // round down.
// min  [l, l+halflen), [l+halflen, r)
return min(mins[l][j], mins[l+-(1<<j)][j]);
}