线段树 缺乏、安全感 2021-10-24 03:52 458阅读 0赞 目录 * 数据结构--线段树 * 一、定义 * 二、性质 * 三、基本操作 * 0.结构体 * 1.建树 * 2.单点查询 * 3.单点修改 * 4.区间修改 * 5.区间查询 * 6.总 * 四、题目 * 单点修改、区间查询模板 * 区间修改、区间查询模板 * 区间修改、单点查询 * 五、鸣谢 * 学姐的Blog * 百度百科 -------------------- # 数据结构--线段树 # ## 一、定义 ## > 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点$\[a,b\]$,它的左儿子表示的区间为$\[a,(a+b)/2\]$,右儿子表示的区间为$\[(a+b)/2+1,b\]$。因此线段树是平衡二叉树,最后的叶子节点数目为$N$,即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为$O(logN)$。而未优化的空间复杂度为$4N$ 你们可能会问什么是[区间树][Link 1],我也不知道。 ![1056834-20170105203630800-980605038.jpg][] $如上图就是一颗\[1,8\]的线段树。$ ## 二、性质 ## $每个节点的左孩子区间范围为\[l,mid\],右孩子为\[mid+1,r\]。$ $对于节点k,左孩子为k \* 2,右孩子为k \* 2 + 1,和二叉树一样$ ## 三、基本操作 ## $线段树的基础操作主要有5个:建树、单点查询、单点修改、区间查询、区间修改。$ ### 0.结构体 ### 可以使用结构体也可以使用数组,看个人喜好。 struct node{ int l,r,w;//l,r分别表示区间左右端点,w表示区间和 }tree[MAXN*4+1];//注意线段树要开四倍空间。 ### 1.建树 ### void build(int l,int r,int now){ tree[now].l=l,tree[now].r=r;//记下now这个节点所表示的区间。 if(l==r){//now节点为叶子结点。 scanf("%d",tree[now].w);//读入叶子结点的值。 return;//不用进行下面的了。 } int mid=(l+r)>>1;//>>1相当于/2 build(l,mid,now<<1);//<<1相当于*2 build(mid+1,r,now<<1|1);//<<1|1相当于*2+1 tree[now].w=tree[now<<1].w+tree[now<<1|1].w;//更新区间和 } ### 2.单点查询 ### 询问第$x$个点的值。 void ask_single(int x,int now){ if(tree[now].l==tree[now].r){//叶子结点,即最终答案。 ans=tree[now].w; return; } int mid=(tree[now].l+tree[now].r)>>1;//计算区间的中点。 if(x<=mid){ ask_single(x,now<<1);//查找该点的左孩子 }else{ ask_single(x,now<<1|1);//查找该点的有孩子 } } ### 3.单点修改 ### 给第$x$个点加上$y$。(和单点查询差不多qwq) void updata_single(int x,int y,int now){ if(tree[now].l==tree[now].r){ tree[now].w+=y; return; } int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid){ updata_single(x,y,now<<1); }else{ updata_single(x,y,now<<1|1); } tree[now].w=tree[now<<1].w+tree[now<<1|1].w;//单点修改后要更新区间和 } ![1056834-20170105214338878-2092313389.jpg][] 修改的过程像上图一样递归修改,当修改完单点后再去更新上面的区间和。 ### 4.区间修改 ### 建议先看下面的区间查询。 将$\[x,y\]$区间每一个数加上$x$。 区间里都是点,进行$y-x+1$次单点修改。(太慢了,应该不会有人用吧。) void update_range(int x,int y,int c){ for(int i=x;i<=y;++i){ update_single(i,c,1); } } 上面这个做法数据不水的话就$TLE$了(在[线段树1][1]中只能拿$70$分)。 将某区间每一个数加上$x$,这个是可以加优化的。 修改需要辣么多时间,不修改不就可以了吗? 差不多,是在没用到的时候不修改。 就像是过年各种亲戚给你压岁钱,然后都到了你家长手里,$\\color\{red\}\{你用的时候再给你\}$。(然后这钱可能永远也到不了你手里了,qwq)。 实现方法: 1.用一个标记记录下这个增量。 2.当要修改的区间完全包含当前区间就给当前区间的标记加上这个增量,不再向下递归。 当需要查询子节点时怎么办? 用到一个下放操作。 1.当前节点的标记累加到子节点的标记中。 2.修改子节点状态。 3.该节点标记清$0$。 结构体: struct node{ int w,l,r,lazy;//lazy就是这个标记。 }tree[MAXN*4+1]; 下放操作: inline void pushdown(int now){ if(tree[now].lazy){ tree[now<<1].lazy+=tree[now].lazy; tree[now<<1|1].lazy+=tree[now].lazy;//将lazy标记向下传. tree[now<<1].w+=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].lazy; tree[now<<1|1].w+=(tree[now<<1|1].r-tree[now<<1|1].l+1)*tree[now].lazy;//更新区间和 tree[now].lazy=0;//清零 } } 区间修改: void update_range(int x,int y,int c,int now){ if(tree[now].l>=x&&tree[now].r<=y){//当前区间包含于要修改的区间. tree[now].w+=(tree[now].r-tree[now].l+1)*c; tree[now].lazy+=c; return; } if(tree[now].lazy) pushdown(now);//下传 int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) update_range(x,y,c,now<<1); if(y>mid) update_range(x,y,c,now<<1|1); tree[now].w=tree[now<<1].w+tree[now<<1|1].w;//这几行和区间查询差不多 } 因为加入了lazy标记所以其他的操作也有改变。 单点查询: int ask_single(int x,int now){ if(tree[now].l==tree[now].r){ return tree[now].w; } if(tree[now].lazy) pushdown(now);//要改的地方只有一个下传 int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) ask_single(x,now<<1); else ask_single(x,now<<1|1); } 区间查询: void ask_range(int x,int y,int now){ if(tree[now].l>=x&&tree[now].r<=y){ ans+=tree[now].w; return; } if(tree[now].lazy) pushdown(now);//要改的地方只有一个下传 int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) ask_range(x,y,now<<1); if(y>mid) ask_range(x,y,now<<1|1); } 单点修改 void update_single(int x,int c,int now){// if(tree[now].l==tree[now].r){ tree[now].w+=c; return; } if(tree[now].lazy) pushdown(now);//要改的地方只有一个下传 int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) update_single(x,c,now<<1); else update_single(x,c,now<<1|1); tree[now].w=tree[now<<1].w+tree[now<<1|1].w; } ### 5.区间查询 ### 求出$\[x,y\]$区间每一个数的和。 在查询的过程中存在以下几种情况: ![1056834-20171203210412804-1934571165.png][] ![1056834-20171203210856882-1912849394.png][] void ask_range(int x,int y,int now){ if(tree[now].l>=x&&tree[now].r<=y){//[l,r]是[x,y]的子集 ans+=tree[now].w; return;//不结束的话进行下面的会重复计算。 } int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid){//要查询的区间在当前区间的左边 ask_range(x,y,now<<1); } if(y>mid){//要查询的区间在当前区间的右边 ask_range(x,y,now<<1|1); } } ### 6.总 ### #include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #define MAXN 500001 using namespace std; struct node{ int l,r,w; int lazy; }tree[MAXN<<2]; int ans; inline int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return f?-x:x; } void build(int l,int r,int now){ tree[now].l=l,tree[now].r=r; tree[now].lazy=0; if(tree[now].l==tree[now].r){ tree[now].w=read(); return; } int mid=(tree[now].l+tree[now].r)>>1; build(l,mid,now<<1),build(mid+1,r,now<<1|1); tree[now].w=tree[now<<1].w+tree[now<<1|1].w; } inline void pushdown(int now){ tree[now<<1].lazy+=tree[now].lazy; tree[now<<1|1].lazy+=tree[now].lazy; tree[now<<1].w+=tree[now].lazy*(tree[now<<1].r-tree[now<<1].l+1); tree[now<<1|1].w+=tree[now].lazy*(tree[now<<1|1].r-tree[now<<1|1].l+1); tree[now].lazy=0; } void update_single(int x,int k,int now){//单点修改 if(tree[now].l==tree[now].r){ //tree[now].w=k;将x这个位置的数改为k //tree[now].w+=k;将x这个位置的数加上k return; } if(tree[now].lazy!=0) pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) update_single(x,k,now<<1); else update_single(x,k,now<<1|1); tree[now].w=tree[now<<1].w+tree[now<<1|1].w; } int ask_single(int x,int now){//单点查询 if(tree[now].l==tree[now].r) return tree[now].w; if(tree[now].lazy!=0) pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) return ask_single(x,now<<1); else return ask_single(x,now<<1|1); } void update_range(int x,int y,int k,int now){//区间修改 if(tree[now].l>=x&&tree[now].r<=y){ tree[now].w+=(tree[now].r-tree[now].l+1)*k; tree[now].lazy+=k; return; } if(tree[now].lazy!=0) pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) update_range(x,y,k,now<<1); if(y>mid) update_range(x,y,k,now<<1|1); tree[now].w=tree[now<<1].w+tree[now<<1|1].w; } void ask_range(int x,int y,int now){ if(tree[now].l>=x&&tree[now].r<=y){ ans+=tree[now].w; return; } if(tree[now].lazy!=0) pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(x<=mid) ask_range(x,y,now<<1); if(y>mid) ask_range(x,y,now<<1|1); } int main(){ return 0; } ## 四、题目 ## ### 单点修改、区间查询模板 ### [Codevs 1080][] [洛谷P3374][P3374] ### 区间修改、区间查询模板 ### [洛谷P3372][1] [Codevs1082][] ### 区间修改、单点查询 ### [洛谷P3368][P3368] [Codevs1081][] ## 五、鸣谢 ## ### [学姐的Blog][Blog] ### ### [百度百科][Link 2] ### 转载于:https://www.cnblogs.com/poi-bolg-poi/p/11055093.html [Link 1]: https://baike.baidu.com/item/%E5%8C%BA%E9%97%B4%E6%A0%91 [1056834-20170105203630800-980605038.jpg]: /images/20211023/d7510dfe8d5b47c9b71030440e9fd560.png [1056834-20170105214338878-2092313389.jpg]: /images/20211023/e4f4d88a500d4a0ebda9e72568dd8663.png [1]: https://www.luogu.org/problemnew/show/P3372 [1056834-20171203210412804-1934571165.png]: /images/20211023/f969ae9f2b774fdf83c545030cead4c7.png [1056834-20171203210856882-1912849394.png]: /images/20211023/5ccdf539d6c941609af714886e4d2795.png [Codevs 1080]: http://codevs.cn/problem/1080/ [P3374]: https://www.luogu.org/problemnew/show/P3374 [Codevs1082]: http://codevs.cn/problem/1082/ [P3368]: https://www.luogu.org/problemnew/show/P3368 [Codevs1081]: http://codevs.cn/problem/1081/ [Blog]: https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html [Link 2]: https://baike.baidu.com
相关 线段树 线段树:创建时实际做的是后序遍历 > 1. 线段树不是完全二叉树 > 2. 线段树是平衡二叉树 > 3. 堆也是平衡二叉树,故完全二叉树是平衡二叉树,平衡二叉树不一 朱雀/ 2023年07月10日 12:39/ 0 赞/ 24 阅读
相关 线段树 [http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html][http_www.cnblogs.com_s 迈不过友情╰/ 2022年09月20日 09:13/ 0 赞/ 291 阅读
相关 线段树 1、概述 线段树,也叫区间树,是一个完全二叉树,它在各个节点保存一条线段(即“子数组”),因而常用于解决数列维护问题,它基本能保证每个操作的复杂度为O(lgN)。 2、线段 分手后的思念是犯贱/ 2022年08月10日 10:53/ 0 赞/ 251 阅读
相关 线段树 Ⅱ 单点修改(内容有升级) \[hdu2795\] ([http://acm.hdu.edu.cn/showproblem.php?pid=2795][http_acm.hdu 朴灿烈づ我的快乐病毒、/ 2022年08月03日 13:45/ 0 赞/ 311 阅读
相关 线段树 线段树:一棵完全二叉树,每个节点代表一个区间。 关于单点更新: \[hdu1166 \] ([http://acm.hdu.edu.cn/showproblem.php?p ﹏ヽ暗。殇╰゛Y/ 2022年08月03日 13:45/ 0 赞/ 304 阅读
相关 线段树 线段树入门: 转载博客:[点击打开链接][Link 1] 前几天开始接触线段树,其一些基本的操作还是很容易理解的,但是区间更新我着实理解了好一会(因该是本人太菜),今天有时 Myth丶恋晨/ 2022年05月29日 22:16/ 0 赞/ 350 阅读
相关 线段树 一 概述 线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(l 川长思鸟来/ 2022年05月17日 05:53/ 0 赞/ 333 阅读
相关 线段树 线段树(单点修改) 1 include <bits/stdc++.h> 2 using namespace std; 3 4 stru 亦凉/ 2021年12月03日 07:17/ 0 赞/ 408 阅读
相关 线段树 转载 [https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html][https_www.cnblogs.com_TheRo 心已赠人/ 2021年07月16日 15:21/ 0 赞/ 540 阅读
还没有评论,来说两句吧...