今際の国の呵呵君: [Data Structure]Segment Tree

今際の国の呵呵君: [Data Structure]Segment Tree

线段树是一种用来解决区间查询和更新的数据结构。对于[m ,n]的区间我们可以把区间递归地二分直到区间的长度变为1。比如储存任意区间和的线段树可以表示为(image from here)：

可以看出，segment tree的每个节点要不有两个子节点要不没有子节点，所以segment tree是一个full binary tree，同时也是一个balance binary tree。对于有n个叶节点的binary tree，有n - 1个非叶节点，所以空间复杂度是O(n), 我们实现的时候用array因为更加方便，但是值得注意的是，开2*n的空间是不够的，因为和heap不同，segment tree不是一个complete binary tree所以其中有一些slot我们是用不上的，一般开3*n差不多够用。这里我们以求区间和为例，建树的时候我们只需bottom up不断用子节点的值更新当前节点即可，时间复杂度O(n)，代码如下，先不用在意mark，我们之后会讲：

Read full article from 今際の国の呵呵君: [Data Structure]Segment Tree