本文共 2754 字,大约阅读时间需要 9 分钟。
1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End
Case 1:63359
#include#include #include #include #include #include using namespace std; const int M=50005;#define lson l,m,rt<<1 //lson表示左子树 #define rson m+1,r,rt<<1|1 //rson表示右子树 int sum[M<<2];//扩大到4倍 void pushplus(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1];//求和 左子树加上右子树 }void build(int l,int r,int rt)//rt表示节点 { if(l==r)//当左右节点为一个数时 输入这个数 叶子 { scanf("%d",&sum[rt]); return; } int m=(l+r)>>1; build(lson); build(rson); pushplus(rt);//求该节点的和 }void update(int p,int add,int l,int r,int rt){ if(l==r) { sum[rt]+=add; return ; } int m=(l+r)>>1; if(p<=m) { update(p,add,lson); } else update(p,add,rson); pushplus(rt);//更新节点的sum值 }int query(int L,int R,int l,int r,int rt){ if(L<=l&&r<=R)//找到在L与R之间的所有区间部分 把每一部分求和加起来 l与r是L与R的子区间 { return sum[rt]; } int m=(l+r)>>1; int ans=0; if(L<=m)//分成多个部分 如果左区间存在交集 加上左区间那部分的sum值 { ans+=query(L,R,lson); } if(R>m) { ans+=query(L,R,rson); } return ans;}int main(){ int T,n,a,b; scanf("%d",&T); for(int i=1;i<=T;i++) { printf("Case %d:\n",i); scanf("%d",&n); build(1,n,1);//树从第一个节点开始 char op[10]; while(scanf("%s",op)&&op[0]!='E') { scanf("%d %d",&a,&b); if(op[0]=='Q') printf("%d\n",query(a,b,1,n,1)); else if(op[0]=='S')//一边人数增加 update(a,-b,1,n,1); else update(a,b,1,n,1);//输入add时人数增加 } } return 0;}/*1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10END*/
转载地址:http://bafci.baihongyu.com/