上面的不是求和的吧 是求区间最值啊0.0
这是我当时照着写的 希望对你有用
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int num[200009];
int dismax[200009];
int dismin[200009];
int lowbit(int x){ return x&(-x); }
void init1(){
for(int i=1; i<=n; ++i){
if( dismax[i] < num [i])dismax[i]=num[i];
for(int j=i; j<=n; j+=lowbit(j) ){
if( dismax[j] < num[i] ) dismax[j]=num[i];
}
}
}
void init2(int x,int y){
num[x]=y;
for(int i=x; i<=n; i+=lowbit(i)){
if(dismax[i] < y) dismax[i]=y;
for(int j=i; j<=n; j+=lowbit(j) ){
if(dismax[j] < num[x] ) dismax[j]=num[x];
}
}
}
int wen1(int x, int y){
int ans=num[y];
while(1){
if(ans < num[y] ) ans=num[y];
if(x==y) return ans;
for(y-=1;y-x>=lowbit(y); y-=lowbit(y))
if(ans < dismax[y] ) ans=dismax[y];
}
}
int main(){
int m;
while( ~scanf("%d%d",&n,&m) ){
for(int i=1; i<=n; ++i ){
scanf("%d",&num[i]);
dismax[i]=-1;
}
init1();
getchar();
for(int i=0; i<m; ++i ){
int a,b;
char c;
scanf("%c%d%d%*c",&c,&a,&b);
if(c=='Q') cout << wen1(a,b) <<endl;
else if(c=='U'){
init2(a,b);
}
}
}
return 0;
}