维护区间最大值ST表
<pre><code class="language-cpp">const int maxn = 3e5+5;
int st[maxn][25];
int n
ll a[maxn];
int lg[300005] = {-1};
void getlog(){
for(int i = 1; i <= 300005; i++) lg[i] = lg[i/2] + 1;
return;
}
void init(){
for(int i = 1; i <= n; i++){
st[i][0] = a[i]; //st表存数组值
}
for(int j = 1; (1 << j) <= n; j++){
for(int i = 1; i + (1 << (j-1)) <= n; i++){
st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1]); //此条语句
}
}
}
int query(int l, int r){
int k = lg[r-l+1];
return max(st[l][k], st[r-(1<<k)+1][k]); //此条语句
}</code></pre>