RMQ

#include <iostream>
#include <cmath>

using namespace std;

const int LOGN = 20;
const int MAXN = 100000;

int table[LOGN][MAXN];
int A[MAXN];

void preprocess(int n){
    for(int i = 0; i < n; ++i) table[0][i] = A[i];
    for(int i = 1; i <= LOGN; ++i){
        for(int j = 0; j < n; ++j){
            if(j + (1 << i) - 1 >= n) break;
            // table[0][1] => min(A[1..1])
            // table[1][1] => min(A[1..2])
            // table[2][1] => min(A[1..4])
            // table[i][j] => min(A[j..j+2^i-1])
            // table[i][j] => min(A[j..j+2^(i-1)-1], A[j+2^(i-1)..j+2^i-1)
            table[i][j] = min(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
        }
    }
}

int query(int a, int b){
    // min(A[a..a+2^x-1], A[b-2^x+1..b])
    // a+2^x-1 <= b
    // 2^x <= b - a + 1
    // x log 2 <= log(b - a + 1)
    int x = int(log2(b - a + 1));
    return min(table[x][a], table[x][b - (1 << x) + 1]);
}

int main(){
    A[0] = 1;
    A[1] = 2;
    A[2] = 3;
    preprocess(3);
    cout << query(0, 0) << endl;
    cout << query(1, 1) << endl;
    cout << query(2, 2) << endl;
    cout << query(0, 1) << endl;
    cout << query(1, 2) << endl;
    cout << query(0, 2) << endl;
    return 0;
}