模板
template<typename T, T (*op)(T, T), int N = 32>
struct sparse_table {
std::vector<T> st[N + 1], lg;
sparse_table() = default;
sparse_table(size_t size, std::vector<T>& a) : lg(size + 1, 0) {
for (int i = 0; i <= N; i++) {
st[i].resize(size + 1, 0);
}
for (int i = 1; i <= size; i++) {
if (i == 1) lg[i] = 0;
else lg[i] = lg[i >> 1] + 1;
st[0][i] = a[i];
}
for (int i = 1; i <= lg[size]; i++) {
for (int j = 1; j + (1 << (i - 1)) <= size; j++) {
st[i][j] = op(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
}
T query(int l, int r) {
int x = lg[r - l + 1];
return op(st[x][l], st[x][r - (1 << x) + 1]);
}
};
使用
初始化
int op(int a, int b) {
return std::max(a, b);
}
sparse_table<int, op, 22> st(n, a)
模板第一个参数为值类型，第二个参数为函数指针(合并信息的操作函数)，第三个参数必须为常数，是倍增层数的值(有默认值32, 所以第三参数可以省略)。
第一个构造参数是区间大小，第二个构造参数是数列的值。
查询
query(l, r) 查询区间 \([l, r]\)。
