《线段树》讲稿.docVIP

《线段树》讲稿 else modify(v的右儿子,i,newvalue) end if v区间的最小值 - min(w区间的最小值,x区间的最小值) //更新数据 end function 由于每个节点都至多递归一次， = O(树深度) = O(log n)。 区间查询操作 继续上面的例子，由于RMQ的目的是在区间内查询最小值，现在讨论如何利用刚刚构造出来的线段树高效回答这一提问： 比如刚才图中所示的树，如果询问区间是[0,2]，或者询问的区间是[3,3]，不难直接找到对应的节点回答这一问题。但并不是所有的提问都这么容易回答，比如[0,3]，就没有哪一个节点记录了这个区间的最小值。当然，解决方法也不难找到：把[0,2]和[3,3]两个区间（它们在整数意义上是相连的两个区间）的最小值“合并”起来，也就是求这两个最小值的最小值，就能求出[0,3]范围的最小值。同理，对于其他询问的区间，也都可以找到若干个相连的区间，合并后可以得到询问的区间。 幸运的是，很容易证明对于任何询问，这样的区间的个数不会超过O(log N)个。通常用来寻找这样一个区间的简单办法是，从根节点开始执行以下步骤： function 在节点v查询区间[l,r] if v所表示的区间和[l,r]交集不为空集 if v所表示的区间完全属于[l,r] 选取v else 在节点v的左右儿子分别查询区间[l,r] end if end if end function 首先可见，这样的过程一定选出了尽量少的区间，它们相连后正好涵盖了整个[l,r]，没有重复也没有遗漏。同时，考虑到线段树上每层的节点最多会被选取2个，一共选取的节点数也是O(log n)的。类似地，同一层被访问的节点不会超过4个，因此查询的时间复杂度也是O(log n)。 换个问题，比如说我们的问题是： 对于一个长度为N的数字串S（从S[0]到S[N-1]），定义 / S[(N - 1) / 2] 如果N是奇数 f(S) = { \ f(S[0]..S[N / 2 - 1]) + f(S[N / 2]..S[N - 1]) 如果N是偶数 给定数字串，要求能够回答它的某些子串的f值。 在N是2的整数次幂时，很容易按照题目条件构造出这棵线段树。对于修改某一个数字这样的操作，也是非常容易的。但是问题来了，真当我们想去用这棵线段树来回答题目中的提问，才会发现，我们选出了O(log n)个线段，它们相连，正好涵盖了我们所询问的区间。而且这些线段的f值都是已知的。可惜的是，这些信息对回答询问毫无帮助。 那么，什么情况下，线段树可以发挥它应有的功能，回答我们的区间查询呢？ 当相邻的区间的信息，可以被合并成两个区间的并区间的信息时，就可以回答区间查询。 第一例中，两个相邻区间的最小值中的较小值，就是并区间的最小值。 第二例中，同等长度的数字串的f函数可以合并，但是不同长度就不可以。因此，虽然可以构造出这棵线段树，却不能回答我们所期望回答的区间询问。 区间修改操作 仍然以RMQ问题为例，如果现在的修改操作一次可以修改的范围也是一个区间，比如给一个区间内所有数同时加上或减去某数，如果按照前面的定义，改动的节点数必定会远远超过O(log n)个。 原因是，我们这样的操作并没有很好利用修改操作也是对一个区间进行操作的性质。 既然要想把区间修改操作也控制在O(log n)的时间内，只修改O(log n)个节点的信息就成为必要。直观上，我们可以直接用前面给出的方法把操作区间变成O(log n)个相连的节点所表示的小区间。对每个区间进行一次修改操作，即可覆盖整个操作区间。正如查询操作如果查询的就是一个节点所表示的区间，就不用查找它的儿子节点的信息，区间修改时如果修改了一个节点所表示的区间，也不用去修改它的儿子节点。然而，对于被修改节点的祖先节点，也必须更新它所记录的值，否则查询操作就肯定会出问题（正如修改单个节点的情况一样）。 这些选出的节点的祖先节点直接更新值即可，而选出的节点却显然不能这么简单地处理：每个节点的值必须能由两个儿子节点的值得到，如这幅图中的例子： 这里，节点[0,1]的值应该是4，但是两个儿子的值又分别是3和5。如果查询[0,0]区间的RMQ，算出来的结果会是3，而正确答案显然是4。 问题显然在于，尽管修改了一个节点以后，不用修改它的儿子节点，但是它的儿子节点的信息事实上已经被改变了。这就需要我们在节点里增设一个域：标记。把对节点的修改情况储存在标记里面，这样，当我们自上而下地访问某节点时，就能