[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，我们之后会讲：


更新的时候我们只需binary search找到要更新的节点然后更新路径上的所有节点，时间复杂度O(log(n))，代码如下：

查询的时候我们要考虑三种情况：

1. 查询区间和当前区间没有交集，return 0
2. 查询区间完全包含当前区间，return当前node的值即可
3. 查询区间和当前区间相交或者当前区间完全包含查询区间，递归地查询两个子区间

那么我们有的时候要查询两个子区间，那么查询的时间复杂度还是O(log(n))吗？设想一下两种情况：

1. 查询区间没有通过当前区间的中点，那么我们最终只递归查询了一个子区间
2. 查询区间通过了当前区间的中点，考虑两个子区间c1，c2，我们有以下的结论：
• 查询区间要不覆盖c1的整个右半边和左半边的一部分，要不只覆盖c1右半边的一部分
• 查询区间要不覆盖c2的整个左半边和右半边的一部分，要不只覆盖c2左半边的一部分

对于2的情况，如果查询区间覆盖了整个区间的右半部分或者左半部分L，对于L我们只需要只需要直接return当前节点的值即可，不会产生额外的递归，所以对于2的情况，我们每一层最多查询4个节点，两个继续递归的节点，和两个完全覆盖直接return的节点。所以查询的时间复杂度仍然是O(log(n))。代码如下：

对于区间更新，这是segment tree的精华和优势所在，我们采用lazy propagation来把更新的操作分摊到后续的每一次经过该节点的更新和查询上。具体来讲，每个node我们会加一个lazy用来存从父节点得到的更新信息，但是我们不急于apply到当前节点和所有子节点。对于一个完全被包含于更新区间[s, e]的节点node，一般来讲我们需要递归地更新其所有子节点。但是如果应用了lazy propagation，我们只需要更新node对应的值，然后更新两个子节点对应的lazy的值，当下一次我们的某个查询或者更新经过了某个子节点，我们再更具lazy的值更新对应的节点值并且继续传递到子节点。这样的话，我们只有当要用(查询/更新)这个节点的话我们才去更新它，也就是所谓的lazy propagation。此外，我们的更新信息也不会丢失因为每当applylazy的信息的时候我们都会传递给子节点知道叶节点。区间更新的时间复杂度也是O(log(n))，分析和查询类似，查询的时候我们只多了每一个节点向子节点传播mark的时间，所以仍然是O(log(n))。代码如下：

完整代码如下：

2D扩展

2D Segment Tree可以用来查询2D的range query。值得注意的是，2D Segment Tree并不是QuadTree。2D Segment Tree的每一个节点都是一个1D的Segment Tree，我们以Region Sum为例：

对应的4,5,6,7节点分别对应矩阵第1,2,3,4列的1D Segment Tree。2,3节点分别对应1,2列的和与3,4列的和形成的1D Segment Tree，1号节点就为所有列的和所形成的segment tree。2D的construct，query和update和1D是十分类似的。假设输入矩阵为O(m * n)，以上操作对应时间复杂度分别为O(m * n), O(log(m) * log(n)) 和O(log(m) * log(n))。空间复杂度O(m * n)，代码如下：