数据结构详解——普通线段树


Warning


由于本博客作者实在是太弱啦,本篇文章可能存在大量的错误,漏洞,不规范,不合法之处。若您发现本文章所存在的任何问题,请您尽快在评论区指出,十分感谢!

另外,本文随意转载,但请注明出处。

问题


我们常常会遇到这样的问题:
给定一个长为 n 的序列 A,有 m 次操作。

  • add q pA[q] 增加 p
  • ask l r 询问从 lr 的区间和

n,m≤5*105

思考


 我们考虑解决方案,显然,用一个一维数组暴力查询的时间复杂度是 O(nm) 的,不能接受。

如果用一个二维数组预处理出从 l 到 r 的区间和,可以做到时间复杂度为 O(1) 的查询,然而这样空间复杂度是 O(n2) 的,不能接受,而且对于修改操作也是很困难的。

所以我们考虑一种类似分治的思想,假设我们需要从 1 到 1088 的区间和 S(l,r),且我们手里已经有了 S(1,1024),那么这个问题就相当于需要获得 S(1,1024)+S(1025,1088)。这样就可以快速的得到结果。

依照上面的思路,假设给出的序列长度 n 为 2048,我们就可以将整个序列划分为 [1,1024],[1025,2045],然后进一步的划分为 [1,512],[513,1024],[1025,1536],[1537,2048]。这样以此类推,我们将整个序列划分成了 2n 个区间。

这就是线段树。

普通线段树


线段树是就是具有如上结构的树,它具体长这个样子:( 图源见水印 )

很显然,除去叶子节点外,每个节点都有两个儿子,若父节点代表的区间是 [l,r],那么左儿子节点代表的区间即为 [l,mid],右儿子代表的区间即为 [mid+1,r]。

它具有良好的性质,如果我们为这些节点标号,令根为节点 1,它的左儿子为 2,右儿子为 3,以此类推。很显然的,对于一个节点 x,它的左儿子节点即为 x*2(即 x<<1),右儿子为 x*2+1(x<<1|1),我们通过位运算优化常数。

然后我们通过代码来建立这棵树,为了解决给出的问题,只需要一个 sum 数组就够了,不需要记录额外的信息。

具体代码为:

就是这么简单粗暴,但要注意的是,我们需要开出 4 倍的空间,2 倍空间是显然的,但是为什么要开 4 倍空间呢?这个问题在下面给出的链接中会有详细的解答,在此不赘述。(未完成)

了解了这棵树的结构,我们就可以尝试着去解决给出的问题了。

解决


我们回顾一下给出的问题:

给定一个长为 n 的序列 A,有 m 次操作。

  • add q pA[q] 增加 p
  • ask l r 询问从 lr 的区间和

n,m≤5*105

对于 add 操作 (建树的过程等价于对一个原本为 0 的节点进行 add),我们找到所有包含修改节点 q 的区间 (共 log n 个,证明是显然的),给这些区间的和都加上 p。我们可以用一个递归来完成该操作,首先递归找到 q 的对应节点,修改它,在回溯的过程中通过子节点更新父亲节点。对于更新父亲节点,我们有一个 pushup 操作。

pushup 代码如下:

pushup 操作是很容易理解的,父亲区间的区间和即为两个子区间的区间和的和。(迷之绕嘴 qwq)

习惯地 (我的习惯), add 操作用 update 函数实现,在 update 中,我们需要记录如下信息:当前节点 x,当前区间左右端点 l,r,修改区间 (点)q,修改值 val.

update 代码如下:

ask 操作我们用 query 函数实现,需要记录的信息有:当前节点 x,当前区间左右端点 l,r,查询区间左右端点 L,R. 另外,通过全局变量 ans 记录本次询问的答案

query代码如下:

两个操作是高度相似的,皆以递归为核心构建。

下面给出完整的代码:

这样,一棵普通的线段树就写出来啦!它支持单点修改和区间查询 (区间和,区间最值等),然而,普通线段树并不能解决如下问题:

新的问题


给定一个长为 n 的序列 A,有 m 次操作。

  • add l r p 给从 A[l] 到 A[r] 增加 p
  • ask l r 询问从 lr 的区间和

n,m≤105

这个问题包含了区间修改,普通线段树只能做到 O(nm) 的丑陋复杂度,然而,在下一讲中的文艺线段树就可以完美解决这个问题啦!(未完待续)

例题


由于这个知识点实在是太弱了,我并不能找到合适的习题 QwQ,由此可见博主有多么的弱。

2017/04/24 补:一道区间最值题  可以用来练习普通线段树

鸣谢


本文的前半部分有部分改编自某神犇博客,然而这位神犇签署了 CC0 协议,出于其本人的意愿,在此并不表明出处。


一个蒟蒻oier的博客 |稍有常识的人都能看出,公告里已经说啦注册功能尚未恢复,不要再试啦~想要账号可以在任意一篇文章下评论留下联系方式或者私聊博主qq获取!~