神秘树状数组
2025-08-09 10:23:06
发布于：浙江
23阅读
0回复
0点赞
静态区间查询最值（别问我为啥不带修，问就是还没学会
建树， 查询，常数极小，约为 ST 表一半。
#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
int tr1[(1 << 19) + 1], tr2[(1 << 19) + 1];
int a[500005];
int n, m;
void build(){
for(int i = 1; i <= n; i++){
tr1[i] = min(tr1[i], a[i]);
int idx = i + (i & (-i));
tr1[idx] = min(tr1[idx], tr1[i]);
}
for(int i = n; i; i--){
tr2[i] = min(tr2[i], a[i]);
int idx = i - (i & (-i));
tr2[idx] = min(tr2[idx], tr2[i]);
}
}
int query(int l, int r){
int ans = 0x3f3f3f3f;
int idx = 0;
for(int i = l; i + (i & (-i)) <= r; i += (i & (-i))){
ans = min(ans, tr2[i]);
idx = i;
} for(int i = r; i - (i & (-i)) >= l; i -= (i & (-i))){
ans = min(ans, tr1[i]);
}
ans = min(ans, a[idx]);
return ans;
}
int main(){
memset(tr1, 63, sizeof(tr1));
memset(tr2, 63, sizeof(tr2));
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 l, r;
cin >> l >> r;
cout << query(l, r) << '\n';
}
return 0;
}
有帮助，赞一个