首页 > 代码库 > 线段树

线段树

2024-07-16 05:09:33   227人阅读

线段树是一个碉炸的数据结构，有多碉炸呢？可以看一下zkw大神的《统计的力量》，里面是讲zkw树的，不用看懂，就了解一下线段树有多碉炸就行。

 看我把它撸过来：

 

然后我们来学一下线段树。

线段树一般是怒存在数组里的，一般a[1]是根节点，然后a[i]的左儿子是a[i<<1] （i<<1是位运算向左移1位，相当于乘2），右儿子是a[i<<1 | 1]，爸是a[i>>1]。

根据这个规律，我们可以用递归来用线段树处理点、区间问题。

线段树一般有几个函数，build初始化线段树，update对线段树进行修改，query对线段树进行查询。然后里面用到PushUp和PushDown，分别是从当前节点的儿子收集信息传给当前节点、把当前节点的信息传下去给儿子，有时只用其中的一个，有时两个都用。

最简单的是单点修改、区间求和。修改的容易，自顶向下递归找到那个要改的点，改一发。区间求和要求单点修改的时候就计算好区间的和，回溯的时候PushUp传递上去。

我的代码都是参照http://www.notonlysuccess.com/index.php/segment-tree-complete/写的，比较好懂，推荐大家看他的碉代码。

例1.敌兵布阵

单点加减，区间求和。

 1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #include<set> 9 #include<stack>10 #include<queue>11 using namespace std;12 #define ll __int6413 #define usint unsigned int14 #define mz(array) memset(array, 0, sizeof(array))15 #define minf(array) memset(array, 0x3f, sizeof(array))16 #define REP(i,n) for(int i=0;i<(n);i++)17 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)18 #define RD(x) scanf("%d",&x)19 #define RD2(x,y) scanf("%d%d",&x,&y)20 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)21 #define WN(x) printf("%d\n",x);22 #define RE  freopen("D.in","r",stdin)23 #define WE  freopen("1.out","w",stdout)24 25 #define lson l,m,rt<<126 #define rson m+1,r,rt<<1|127 const int maxn=51111;28 int a[maxn<<2];29 30 void PushUP(int rt){31     a[rt]=a[rt<<1]+a[rt<<1|1];32 }33 34 void build(int l,int r,int rt){35     if(l==r){36         scanf("%d",&a[rt]);37         return;38     }39     int m=(l+r)>>1;40     build(lson);41     build(rson);42     PushUP(rt);43 }44 45 void update(int p,int add,int l,int r,int rt){46     if(l==r){47         a[rt]+=add;48         return;49     }50     int m=(l+r)>>1;51     if(p<=m)update(p,add,lson);52     else update(p,add,rson);53     PushUP(rt);54 }55 56 int query(int L,int R,int l,int r,int rt){57     if(L<=l&&r<=R){58         return a[rt];59     }60     int m=(l+r)>>1;61     int ret=0;62     if(L<=m)ret+=query(L,R,lson);63     if(R>m)ret+=query(L,R,rson);64     return ret;65 }66 67 int main()68 {69     int cas=1,T;70     char s[10];71     int x,y,i,n;72     scanf("%d",&T);73     while(T--)74     {75         scanf("%d",&n);76         build(1,n,1);77         printf("Case %d:\n",cas++);78         while(scanf("%s",s)!=EOF){79             if(s[0]==‘E‘)break;80             scanf("%d%d",&x,&y);81             if(s[0]==‘A‘) update(x,y,1,n,1);///x地增加y人82             else if(s[0]==‘S‘)update(x,-y,1,n,1);///x地减少y人83             else if(s[0]==‘Q‘)printf("%d\n",query(x,y,1,n,1));///x~y总人数84         }85     }86     return 0;87 }
View Code


例2.

 

（未完待续）


联系
我们