线段树1

线段树是一种通过递归方式快速索引处理的方式，但是有大量空间冗余。 先通过一个简单例题说明下： 敌兵布阵 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

这个题是定点改动，即寻找一个定点而且每次只改变一个值，这种比较简单，修改一下模板的搜索条件就好。

#include <iostream> #include <cstdio> #include <cstring> using namespace std; #define maxsize 50010 //可以处理的最大数目，也可以说是最大范围 int tree[maxsize*4],cnt=0;//一般需要四倍空间，这样才能保证有足够的存储量 //修改函数，修改每个范围的值，本题是求区间和，所以是左边总和加上右边总和 void pushup(int pos) { if(pos>=maxsize*4) return ; tree[pos]=tree[2*pos]+tree[2*pos+1]; } //建立线段树 //pos表示当前位置，left表示左边界，right表示右边界 void build(int pos,int left,int right) { //当左边界等于右边界，即当前区间只有一个点，此时为叶子节点，输入叶子的值 //当为叶子，输入结束后直接返回，避免无限递归 if(left==right) { scanf("%d",&tree[pos]); return ; } //求得中点 int mid=(left+right)/2; //分别对左右递归建树 build(2*pos,left,mid); build(2*pos+1,mid+1,right); //更新放在最后，可以在底层叶子建好后，由下而上求得不同区间的和 pushup(pos); } //值的更新，pos表示当前数组下标，addnum表示更改的值，left，right分别是当前点的左右边界，pl是更改位置 void updata(int pos,int addnum,int left,int right,int pl ) { //只有目标点才会取得到左右相等，其他点会在递归过程中舍掉 if(left==right) { tree[pos]+=addnum; return ; } int mid=(left+right)/2; //当目标点在左半部分，对左半部分递归 if(pl<=mid) { updata(2*pos,addnum,left,mid,pl); } //当目标点在右边，对右半部份进行递归 else { updata(2*pos+1,addnum,mid+1,right,pl); } //更改完成后，递归修改 pushup(pos); } //计算区间和 //当前点为pos，left，right同上，pl为计算区间左边界，pr为计算区间右边界 int getsum(int pos,int left,int right,int pl,int pr) { int sum=0; //找到恰好的区间才返回，因为目标区间可以拆分，所以一定可以找到符合函数参数的区间 if(left==pl&&right==pr) { return tree[pos]; } int mid=(left+right)/2; //目标区间全部在左边 if(pl>mid) { sum+=getsum(2*pos+1,mid+1,right,pl,pr); } //目标区间全部在右边 else if(pr<=mid) { sum+=getsum(2*pos,left,mid,pl,pr); } //两边都有 else{ //区间拆分，mid作为新的左右边界 sum+=getsum(2*pos,left,mid,pl,mid); sum+=getsum(2*pos+1,mid+1,right,mid+1,pr); } return sum; } int main() { int t; scanf("%d",&t); while(t--) { memset(tree,0,sizeof(tree)); int n; scanf("%d",&n); build(1,1,n); printf("Case %d:\n",++cnt); char order[10]; while(scanf("%s",order)!=EOF) { if(order[0]=='E') break; if(order[0]=='Q') { int a,b; scanf("%d%d",&a,&b); printf("%d\n",getsum(1,1,n,a,b)); } if(order[0]=='A') { int a,b; scanf("%d%d",&a,&b); updata(1,b,1,n,a); } if(order[0]=='S') { int a,b; scanf("%d%d",&a,&b); updata(1,-b,1,n,a); } } } return 0; }

这种线段树的写法把线段树区间左右边界信息放在函数参数中而不是采用结构体进行存储，可以节省大量空间。 另外，每个节点存储的可以不仅仅是区间和，还可以是区间最大值等信息，例如：

I Hate It 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。 Input 本题目包含多组测试，请处理到文件结束。 在每个测试的第一行，有两个正整数N和M ,分别代表学生的数目和操作的数目。 学生ID编号分别从1编到N。 第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。 接下来有M行。每一行有一个字符 C (只取’Q’或’U’) ，和两个正整数A，B。 当C为’Q’的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。 当C为’U’的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 Output 对于每一次询问操作，在一行里面输出最高成绩。 Sample Input

5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5

Sample Output

5 6 5 9

Hint

Huge input,the C function scanf() will work better than cin void pushup(int pos) { if(pos>4*maxsize) return; //对于每一个点，只要更改更新方式就可以获得不同功能 tree[pos]=max(tree[pos*2],tree[2*pos+1]); }

完整代码如下，因为是模板题，比较简单，更改比较少，所以注释可以参考上一份代码；

#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define maxsize 200010 int tree[maxsize*4]; void pushup(int pos) { if(pos>4*maxsize) return; tree[pos]=max(tree[pos*2],tree[2*pos+1]); } void build(int pos,int left,int right) { if(left==right) { scanf("%d",&tree[pos]); return; } int mid=(left+right)/2; build(2*pos,left,mid); build(2*pos+1,mid+1,right); pushup(pos); } void update(int pos,int left,int right,int changepos,int changenum) { if(left==right) { tree[pos]=changenum; return ; } int mid=(left+right)/2; if(changepos<=mid) { update(2*pos,left,mid,changepos,changenum); } else{ update(2*pos+1,mid+1,right,changepos,changenum); } pushup(pos); } int ask(int pos,int left,int right,int pl,int pr) { if(left==pl&&right==pr) { return tree[pos]; } int mid=(left+right)/2; if(pr<=mid) { return ask(2*pos,left,mid,pl,pr); } else if(pl>mid) { return ask(2*pos+1,mid+1,right,pl,pr); } else{ return max(ask(2*pos,left,mid,pl,mid),ask(2*pos+1,mid+1,right,mid+1,pr)); } } int main() { int num,order; while(scanf("%d%d",&num,&order)!=EOF) { memset(tree,0,sizeof(tree)); build(1,1,num); char str; int a,b; getchar(); while(order--) { scanf("%c%d%d",&str,&a,&b); getchar(); if(str=='U') { update(1,1,num,a,b); } if(str=='Q') { printf("%d\n",ask(1,1,num,a,b)); } } } return 0; }