AcWing
1270. 数列区间最大值
树状数组：
树状数组(二叉索引树)–Binary_Indexed_Tree
建树和递推查询，求区间的最大值。
建树，$O(nlogn)$：
void build() { // 初始化树状数组
for (int i = 1; i <= n; ++ i) {
tr[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
tr[i] = max(tr[i], tr[i - j]);
}
}
递推查询，$O(mlogn)$，$m$为查询次数：
int query(int l, int r) { // 区间查询，相当于l为边界，r为初始指针
int maxe = a[l];
while (l <= r) {
maxe = max(maxe, a[r]);
r --;
for (; l <= r - lowbit(r); r -= lowbit(r)) // 如果能比较成段的区间，保证r左移之后仍满足l<=r
maxe = max(maxe, tr[r]);
}
return maxe;
}
代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100010;
int a[N], tr[N];
int lowbit(int x){return x & -x;}
void build(){
for(int i = 1; i <= n; i ++){
tr[i] = a[i];
for(int j = 1; j < lowbit(i); j <<= 1) tr[i] = max(tr[i], tr[i - j]);
}
}
int query(int l, int r){
int maxe = a[l];
while(l <= r){
maxe = max(maxe, a[r]);
r--;
for(; l <= r - lowbit(r); r -= lowbit(r)) maxe = max(maxe, tr[r]);
}
return maxe;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
build();
while(m --){
int x, y;
cin >> x >> y;
cout << query(x, y) << "\n";
}
return 0;
}
线段树写法(不涉及区间修改，不需要用到lazy标记)：
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 100010;
int a[N], sum[N * 4];
void push(int u){
sum[u] = max(sum[2*u], sum[2*u + 1]);
}
void build(int l, int r, int u){
if(l == r){
sum[u] = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, 2*u);
build(mid + 1, r, 2*u + 1);
push(u);
}
int query(int L, int R, int l, int r, int u){
int res = a[L];
if(L <= l && r <= R) return sum[u];
int mid = l + r >> 1;
if(L <= mid) res = max(query(L, R, l, mid, 2*u), res);
if(R > mid) res = max(query(L, R, mid + 1, r, 2*u + 1), res);
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
build(1, n, 1);
while(m --){
int x, y;
cin >> x >> y;
cout << query(x, y, 1, n, 1) << "\n";
}
return 0;
}