排兵布阵

线段树的简单题，都没用到辅助数组

我出现的错：

if(a<=mid)ans+=query(a,b,l,mid,rt<<1);
else if(b>mid)ans+=query(a,b,mid+1,r,rt<<1|1);

丢死人了

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int tree[200001];
void push_up(int root){
tree[root]=tree[root<<1]+tree[root<<1|1];
}
/*
void push_down(int root,int _size){

}
*/
void init(int f){
for(int i=0;i<=f;i++)tree[i]=0;
}
void buildtree(int l,int r,int rt){
if(l==r){
scanf("%d",&tree[rt]);
return;
}
int mid=(l+r)>>1;
buildtree(l,mid,rt<<1);
buildtree(mid+1,r,rt<<1|1);
push_up(rt);
}
void add(int a,int b,int l,int r,int rt){
if(l==r){
tree[rt]+=b;
return;
}
int mid=(l+r)>>1;
if(a<=mid)add(a,b,l,mid,rt<<1);
else add(a,b,mid+1,r,rt<<1|1);
push_up(rt);
}
int query(int a,int b,int l,int r,int rt){
if(a<=l&&b>=r){
return tree[rt];
}
int mid=(l+r)>>1,ans=0;
if(a<=mid)ans+=query(a,b,l,mid,rt<<1);
if(b>mid)ans+=query(a,b,mid+1,r,rt<<1|1);
return ans;
}
int main(){
int t,n;
cin >> t;
for(int i=1;i<=t;i++){
cout << "Case " << i << ":\n";
cin >> n;
init(n<<2);
buildtree(1,n,1);
string str;
int a,b;
while(1){
cin >> str;
if(str[0]=='E')break;
cin >> a >> b;
if(str[0]=='Q')cout << query(a,b,1,n,1) << endl;
else if(str[0]=='A')add(a,b,1,n,1);
else if(str[0]=='S')add(a,-b,1,n,1);
}

}
return 0;
}

原文链接:https://www.cnblogs.com/sos3210/p/12341359.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有