敌兵布阵 线段树

C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。  中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.  Input 第一行一个整数T，表示有T组数据。  每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。  接下来每行有一条命令，命令有4种形式：  (1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）  (2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;  (3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;  (4)End 表示结束，这条命令在每组数据最后出现;  每组数据最多有40000条命令  Output 对第i组数据,首先输出“Case i:”和回车,  对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。  Sample Input 1 10 1 2 3 4 5 6 7 8 9 10 Query 1 3 Add 3 6 Query 2 7 Sub 10 2 Add 6 3 Query 3 10 End Sample Output Case 1: 6 33

59

我就没见过比这道题还狗的题，在OJ上交得看运气，运气好AC，运气不好TLE，真狗啊。

这是我花了接近一天的时间搞明白的线段树，但为什么要用线段树我还是没有搞明白，以后再去研究吧。

线段树自从他出生就和二分法离不开。这里我又学习了C++的cin的一个小用法，就是在接受字符串时，cin遇到

空格就停止，要记住。线段树主要有以下几个操作，建立线段树，更新线段树，搜索线段树。至于网上说的那些

在区间求最值，求区间和啊什么的，那都是在建立线段树的时侯要注意的操作。我发现啊，在这三个操作里边，

都是从ROOT开始操作，这个很好理解的。在区间求和这个函数里，递归结束条件需要注意，自己可以模拟一下加深

理解，算了，写也写不明白，代码一看全都明了。

#include<iostream> #include<stdlib.h> #include<string.h> #include<stdlib.h> using namespace std; struct node { int a; int b; int sum; }t[140000]; int r[50010],SUM=0; void make(int x,int y,int num) { if(x==y) { t[num].a=t[num].b=x; t[num].sum=r[x]; return ; } t[num].a=x; t[num].b=y; int mid=(x+y)/2; make(x,mid,num*2); make(mid+1,y,num*2+1); t[num].sum=t[num*2].sum+t[num*2+1].sum; } void query(int x,int y,int num) { if(x<=t[num].a && y>=t[num].b) { SUM+=t[num].sum; return ; } int mid=(t[num].a+t[num].b)/2; if(y<=mid) //说明搜索区间在左子树 { query(x,y,num*2); } else if(x>mid) { query(x,y,num*2+1); } else { query(x,y,num*2); query(x,y,num*2+1); } } void add(int x,int decrease,int num) //decrease代表增加的值，num默认从1开始 { t[num].sum+=decrease; if(x==t[num].a && x==t[num].b) return ; int mid=(t[num].a+t[num].b)/2; if(x<=mid) { add(x,decrease,num*2); } else { add(x,decrease,num*2+1); } } void sub(int x,int increase,int num) { t[num].sum-=increase; if(x==t[num].a && x==t[num].b) return ; int mid=(t[num].a + t[num].b)/2; if(x<=mid) { sub(x,increase,num*2); } else { sub(x,increase,num*2+1); } } int main() { int T,i,j,re=1; cin>>T; char ch[6]; while(T--) { printf("Case %d:\n",re++); int n; cin>>n; for(i=1;i<=n;i++) cin>>r[i]; make(1,n,1); while(cin>>ch) { if(strcmp(ch,"End")==0) break; if(strcmp(ch,"Query")==0) { SUM=0; int a,b; cin>>a>>b; query(a,b,1); cout<<SUM<<endl; } else if(strcmp(ch,"Add")==0) { int a,b; cin>>a>>b; add(a,b,1); } else { int a,b; cin>>a>>b; sub(a,b,1); } } } return 0; }