§ 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][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 [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]);
}