本文共 2319 字，大约阅读时间需要 7 分钟。
这个题目的题意很明确了，我就不在复述，我就说一下这个题目为什么要用线段数，很明显这个题目是与区间有关的问题，查询区间信息，修改区间的值，我们可以看到这个题目数据量很大，用普通的区间修改方法肯定超时，所以我们选择线段数；
这个是我写的第一个线段数，所以出现了很多问题，问题总结如下：
在查询和修改的时候题目中给的下标是从一开始，而我习惯使用从0开始，所以一开始区间区间下标出现问题。
线段数是给分成两个部分，所以分成的两个区间是相邻的，能够接在一起，所以每次出现（l，m） （m+1，r），在传递参数的时候也要注意传的参数。
3.每次传参的时候传的参数很多，所以要注意传的参数，不能混淆。
4.注意递归结束的时候，不要忘记加return，一次在一个函数里面没有加入return，程序崩溃。
5.在上面也说了方式TLE所以我们使用线段树，这里还有一个问题由于cin cout是流输入输出，比较慢，所以我们使用scanf，这样就比较快了，第一次使用cin，cout的时候就TLE了；
另外还有位运算操作：
1.MAXN<<2：
相当于MAXN向左移位两次，所以相当于是*4；
2.(l+r)>>2:
向右移位相当于是除2；
3.rt<<1|1：
相当于是乘2+1；
下面附上代码：
#include#include #include #include #include using namespace std;int n;const int MAXN=50050;int str[MAXN];int seg[MAXN<<2];void Build(int node,int begin,int end){ if(begin==end) { seg[node]=str[end]; return ; } Build(node*2,begin,begin+(end-begin)/2); Build(node*2+1,begin+(end-begin)/2+1,end); seg[node]=seg[node*2]+seg[node*2+1];}void update(int p,int add,int l,int r,int rt){ if(l==r) { seg[rt]+=add; return ; } int m=(l+r)>>1; if(p<=m) update(p,add,l,m,rt<<1); else update(p,add,m+1,r,rt<<1|1); seg[rt]=seg[rt*2]+seg[rt*2+1];}int quer(int ll,int rr,int l,int r,int rt){ if(ll<=l&&rr>=r) { return seg[rt]; } int m=(l+r)>>1; int ret=0; if(ll<=m) { int temp=quer(ll,rr,l,m,rt<<1); ret+=temp; } if(rr>m) { int temp=quer(ll,rr,m+1,r,rt<<1|1); ret+=temp; } return ret;}int main(){ int T; scanf("%d",&T); for(int kase=1; kase<=T; kase++) { printf("Case %d:\n",kase); scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&str[i]); Build(1,1,n); string s; while(cin>>s) { if(s=="End") break; else if(s=="Add") { int x,y; scanf("%d%d",&x,&y); update(x,y,1,n,1); } else if(s=="Sub") { int x,y; scanf("%d%d",&x,&y); update(x,-y,1,n,1); } else if(s=="Query") { int x,y; scanf("%d%d",&x,&y); int ans=quer(x,y,1,n,1); printf("%d\n",ans); } } } return 0;}
转载地址：http://kygsi.baihongyu.com/