cpp sparse table
template<class T> struct SparseTable {
T (*op)(T, T);
vector<int> log2s;
vector<vector<T>> table;
SparseTable (const vector<T>& arr, T (*op)(T, T))
: op(op) {
// Preprocess the log 2s
log2s = vector<int>(log2(arr.size())+2);
for (int i = 2; i<log2s.size(); ++i) {
log2s[i] = log2s[i/2]+1;
}
// Copy input over to the table
table = vector<vector<T>>(arr.size(), vector<T>(log2s.size()));
for (int i = 0; i<arr.size(); ++i) {
table[i][0] = arr[i];
}
for (int power = 1; power < log2s.size(); ++power) {
int prevPower = power - 1;
for (int i = 0; i+(1<<power) <= table.size(); ++i) {
table[i][power] = op(table[i][prevPower], table[i+(1<<prevPower)][prevPower]);
}
}
}
T query (int l, int r) {
int power = log2s[r-l+1];
return op(table[l][power], table[r-(1<<power)+1][power]);
}
};