线段树
![](/img/%E7%BA%BF%E6%AE%B5%E6%A0%91.png)
AI-摘要
Tianli GPT
AI初始化中...
介绍自己 🙈
生成本文简介 👋
推荐相关文章 📖
前往主页 🏠
前往爱发电购买
线段树
wsq127写在最前
我承认这个封面的线段树
有点过于抽象,但是真的没有别的办法乐。
先引用一个大佬说的一句话:
什么是线段树?
如果你在考提高组前一天还在问这个问题,那么你会与一等奖失之交臂;如果你还在冲击普及组一等奖,那么这篇博客会浪费你人生中宝贵的5~20分钟。
显而易见,线段树是一个 OIer 从萌新过渡到正式 OIer 选手的标志性算法。
然而事实上,对于一个正式的 OIer 选手,线段树更应该是一个工具,所以……
线段树是世界上最好的数据结构!!!(超大声
线段树可以 $O(\log n)$ 的实现区间和,区间乘,区间最值,区间修改等操作,在很多题中都可以以略逊于正解的解法过掉。
核心思想
线段树就是将一个区间的答案分成两个子区间,需要修改的时候从最小的区间一路爬上去,需要查询的时候从上面一路往下找。
对,没了,就这么简单((
实际上线段树的思想是非常好想的,以至于有的人可能在考场上自己想出来不是我,另一个大佬,难点其实是在实现以及右面的懒标记。
正常情况下我们存一棵树可能会用到存图的方法,或者是存每一个点的子节点,然而为了维护一串序列而真的建一个图实在是又臭又长过于屎山,不难想到父子两倍,即父节点为 $n$ 的话,子节点分别是 $2n$ 和 $2n+1$。
如果用这种方法的话不妨思考一下他所需的空间(以下非重点,可以酌情跳过):
首先设这个序列长度为 $n$。
按照正常的逻辑,线段树的最下面是长度为 1 的区间,那么也就是说总共有 $n$ 个叶子节点。
不难发现总共有 $2n-1$ 个节点,然而事实上,我们在建树中,会浪费掉一些空间
实现
建树
(先鸽着,有空再来写((
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果