并非通用的 ST表 模板（存档）
2025-03-08 19:28:25
发布于：广东
23阅读
0回复
0点赞
template <int (*func)(int, int)>
struct ST{
vector <vector <int>> a;
vector <int> log;
int maxlog;
ST(){}
ST(vector <int> v, int n, int zero){
log.resize(v.size() + 5);
for(int i = 2; i <= n; i++){
log[i] = log[i / 2] + 1;
}
maxlog = log[n];
a.resize(maxlog + 5, vector <int> (n + 5, zero));
for(int i = 1; i <= n; i++){
a[0][i] = v[i];
}
for(int i = 1; i <= maxlog; i++){
for(int j = 1;; j++){
if(j + (1 << i) - 1 > n) break;
a[i][j] = func(a[i - 1][j], a[i - 1][j + (1 << (i - 1))]);
}
}
}
int query(int l, int r){
int i = log[r - l + 1];
return func(a[i][l], a[i][r - (1 << i) + 1]);
}
};
这里空空如也
有帮助，赞一个