线段树详解

前：笔者觉得线段树很重要，听说我基友___X3___要写一篇关于线段树的博客，我就也写了一篇。持续更新。 -----------------------咕咕的分界线------------------------------------------------ 更新日志： update 11.21/2020 :写成。 -----------------------咕咕的分界线------------------------------------------------ ### Part 1 线段树是一种基于**分治**思想的**二叉树**结构，较通用，适于解决**区间**问题。 线段树的**每个节点代表一个区间**，根节点唯一，表示 $1-n$。 每个叶节点表示一个长度为1的元区间 $[x,x]$。 对于每个节点（内部） $[l,r]$,它的左节点是 $[l,mid]$，右子节点是 $[mid+1,r]$。 $$mid=(l+r)/2=(l+r)>>1$$ （$mid$ 向下取整） -----------------------咕咕的分界线------------------------------------------------ 性质：线段树除去最后一层，一定是一棵完全二叉树，所以，在理想情况下，$n$ 个节点的线段树有 $$n+n/2+n/4+...+2+1=2n-1$$ 个节点。 因此，数组长度要开到**不小于4倍**。 ~~我暴力开过100倍，不会MLE...~~ -----------------------咕咕的分界线------------------------------------------------ 图片链接：（图老是挂，于是决定使用链接。） 注意，线段树的编号与堆的编号类似，相当于 $dfs$ 序。 [线段树图片](https://image.baidu.com/search/index?tn=baiduimage&ct=201326592&lm=-1&cl=2&ie=gb18030&word=%CF%DF%B6%CE%CA%F7%CD%BC%C6%AC&fr=ala&ala=1&alatpl=adress&pos=0&hs=2&xthttps=111111) ------------所以，第一部分圆满结束--------------------------------- ### Part 2,标记延迟 这就是大名鼎鼎~~臭名远扬~~的 $lazytag$。 先说一下标记延迟的作用：将一次区间修改的时间复杂度从 $O(n)$ 优化到 $O(log n)$。 本文 $log$ 默认为2。 如果在修改指令中，要修改节点 $p$ 代表的区间 $[l,r]$。正常的修改方法就是访问以它为根节点的子树并修改。复杂度是 $O(n)$，其中 $n$ 为此子树节点数。 但是，我们没有用到这个区间作为候选答案。所以，更新 $p$ 的整棵子树是浪费时间的徒劳行为。 怎么解决呢？？？ 加入 $lazytag$，懒标记。 ps:关于标记，还有一种叫做“标记永久化”的技巧。就是不下传标记，而是累计递归时产生的标记影响。这种做法局限性大，仅在二维线段树和可持久化线段树中有所应用。所以不介绍了。 懒标记的具体实现就是在回溯时向节点 $p$ 增加一个标记，表示“**该节点在过去被修改了，但是它的子节点尚未被更新**”。 后续操作中，如果要从 $p$ 往下递归，我们就再检查一下 $p$ 是否有标记。有，就根据标记更新 $p$ 的两个儿子,并往下增加标记，然后消除 $p$ 的标记。 这种优化叫做延迟标记，是一个高效率的线段树应该具有的优化。 ### Part 3 ，Code 上代码。 线段树初始化： ```cpp struct segtree{ int l,r,lazy,add; }t[max_size<<1+max_size<<1]; ``` 有空更新一份用 $class$ 写的。 从子节点往父亲更新标记： ```cpp void pushup(int id) { t[id].add=t[id<<1].add+t[id<<1|1].add; } ``` 下传标记： ```cpp void pushdown(int id,int l,int r){ t[id<<1].lazy+=t[id].lazy; t[id<<1|1].lazy+=t[id].lazy; int mid=(l+r)>>1; t[id<<1].add+=t[id].lazy*(mid-l+1); t[id<<1|1].add+=t[id].lazy*(r-mid); t[id].lazy=0; } ``` 线段树递归建立： ```cpp void build_segtree(int id,int l,int r){ //节点id表示区间 [l,r] t[p].l=l,t[p].r=r; if(l==r){ //叶节点 t[p].add=a[l]; return; } int mid=(l+r)>>1; build_segtree(id<<1,l,mid); build_segtree(id<<1|1,mid+1,r); //等同于build_segtree(id*2+1,mid+1,r); pushup(id); //标记延迟优化时间 } ``` 上传操作和下传操作是维护线段树的基本操作，基本上每一种操作都要用到。 还有，每个人的线段树写的都不一样，我的写法适中。所以，关于线段树，尽量不要背模板，要随机应变。 有一种比较经典的 $spread$ 函数，其实就是 $pushdown$ 函数。 单点修改和区间修改中很重要的一点： 判断是否向下递归，需判断覆盖性，**如果当前区间 $[l,r]$ 被完全覆盖，就可以直接返回了**。就是一种整块的处理，有没有分块的感觉？ 单点修改，将区间 $[x,y]$ 的每一个值加上 $v$： ```cpp int add_(int id,int l,int r,int x,int y,int v){ if(x<=l&&r<=y){ t[id].lazy+=v; t[id].add+=v*(r-l+1); return;//叶节点修改 } pushdown(id,l,r); int mid=(l+r)>>1; if(x<=mid)add_(id<<1,l,mid,x,y); if(y>mid)add_(id<<1|1,mid+1,r,x,y); pushup(id); } ``` 区间修改,求出区间 $[x,y]$ 的每一个值的和： ```cpp int query(int id,int l,int r,int x,int y){ if(x<=l&&r<=y){ return t[id].add; } pushdown(id,l,r); int ans=0,mid=(l+r)>>1; if(x<=mid)ans+=query(id<<1,l,mid,x,y); if(y>mid)ans+=query(id<<1|1,mid+1,r,x,y); return ans; } ``` 有了这些操作，就可以实现大部分的线段树题目了。 -----------------------咕咕的分界线------------------------------------------------ ### Part 4 例题及题解 1.最经典的[线段树1](https://www.luogu.com.cn/problem/P3372)，只要把上面代码组合一下就可以过了。此处不贴。 2.[守墓人](https://www.luogu.com.cn/problem/P2357)，把上面的代码组合修改就可以过了。我是用分块AC的，代码[传送门](https://www.luogu.com.cn/paste/5v9tz4r9)。 3.题目是一道简单的省选，[最大数](https://www.luogu.com.cn/problem/P1198)，代码传送门[我的博客（题解）](https://blog.csdn.net/SB_zero_mark/article/details/109702902)。 4.[线段树2](https://www.luogu.com.cn/problem/P3373)，这道题难就难在区间乘。为了时间和精度，我们使用两个 $lazytag$,乘法优先更新，就可以跑过了。 证明：乘法优先的话，不会改变加法的 $lazytag$ 的值，使得精度等一系列更优。证毕。 5.最难的一题：[线段树3](https://www.luogu.com.cn/problem/P6242)，由于有历史情况，所以我们要维护4种标记，然后跑过。代码和 灵梦 的非常像，但没有抄袭，我是对着TA的打了一遍，那时，我刚学线段树。代码：[传送门](https://www.luogu.com.cn/paste/ezkyvdzc)。 -----------------------咕咕的分界线------------------------------------------------ 结： 我希望这篇文章对读者有所帮助。若有建议，可直接在评论区提出。转载私聊。相对来说，这篇文章很详细，因为我自己学这个的时候，别的文章大都有些欠缺，~~就像那位基友的~~，导致我不好理解。最近有空，就写篇~~真正的好文章~~详解吧！！！ 如果觉得这篇文章对您有帮助，可以点个赞吗？？？谢谢阅读。