## ยง 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:

```
for(int i = 0; i < n; ++i) { mins[i][0] = 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[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:
```
int query_mins(int l, int r) {
int len = r-l;
if (len < 0) { return INFTY; }
int j = log2(len);
return min(mins[l][j], mins[l+-(1<<j)][j]);
}
```