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