Sparse Table

template< class Data, Data (*oper)(Data, Data) >
class SparseTable {
    Data **table; // [power][begin]
    int *powers;
public:
    SparseTable(Data *array, int len) {
        powers = new int [len + 1];
        int pow = 0;
        for (int i = 1; i <= len; i++) {
            if ((1 << (pow + 1)) <= i)
                pow++;
            powers[i] = pow;
        }

        table = new Data *[++pow];
        table[0] = array;
        for (int cur_pow = 1; cur_pow < pow; cur_pow++) {
            int max_begin = len - (1 << cur_pow) + 1;
            table[cur_pow] = new Data [max_begin];
            for (int i = 0; i < max_begin; i++)
                table[cur_pow][i] = oper(table[cur_pow - 1][i],
                        table[cur_pow - 1][i + (1 << (cur_pow - 1))]);
        }
    }

    Data get(int l, int r) {
        int pow = powers[r - l + 1];
        return oper(table[pow][l], table[pow][r - (1 << pow) + 1]);
    }
};