线段树之入门篇

线段树(interval tree) 是把区间逐次二分得到的一树状结构。它反映了包含归并排序在内的非常多分治算法的问题求解方式。

 

上图是一棵典型的线段树。它对区间[1,10]进行切割。直到单个点。这棵树的特点
是：
1. 每一层都是区间[a, b]的一个划分。记 L = b - a

2. 一共同拥有log2L层
3. 给定一个点p。从根到叶子p上的全部区间都包括点p。且其它区间都不包括点p。
4. 给定一个区间[l; r]，能够把它分解为不超过2log2 L条不相交线段的并。

当中第四点并非非常显然。图8.1显示了[2, 8]的分解方式，深灰色结点为分解后的
区间，浅灰色结点是递归分解过程中经过的结点。

为了叙述方便，以下称树中的结点
所相应的区间为树中区间。

 

 

　　从第3点和第4点能够得出结论：改动一个点仅仅用改动log2 L个树中区间信息。而统计一个区间仅仅须要累加2log2 L个树中区间的信息，且訪问的总结点数是O(log L)的。

两个操作都非常easy实现。

　　动态统计问题I 有一个包括n个元素的整数数组A，每次能够改动一个元素，也能够询问某一个区间[l; r]内全部元素的和。怎样设计算法，使得改动和询问操作的时间复杂度尽量低？
　　方法一 直接做， 则改动操作是O(1)的， 但询问须要进行累加， 时间复杂度为O(r ? l)，最坏情况为O(n)。
　　方法二 建立一棵线段树。每一个树中区间记录该区间的元素和，则由刚才的结论，改动元素时仅仅须要改动log2 L个树中区间的元素和。而统计时仅仅须要累加2log2 L个树中区间的元素和，两个操作都是O(log n)的，例如法一好非常多。

　　动态统计问题II 有一个包括n个元素的整数数组A。每次能够同一时候给一个区间[l; r]内的数同一时候添加一个数d（d能够为负），也能够询问某一个数Ai的值。怎样设计算法。使得改动和询问操作的时间复杂度尽量低？

　　怎样高速改动一个区间？改动一个树中区间[a; b]将影响到以[a; b]为根的整棵子树和它的全部祖先。所以假设沿用刚才的线段树定义，是不可能高速实现区间改动操作的。
　　解决方法是借用数据结构中经常使用的\懒操作"的思想。仅仅记录有哪些操作须要运行。而不去真正运行这些操作。换句话说。在须要给树中区间[l; r]的元素同一时候增
加d时，我们仅仅记录\以前有一条指令add(l, r, d)"就能够了。我们把记录的这个值称为树中区间的add值。则叶结点的元素值为它全部祖先的add值之和。依据前面的结论，每一条随意区间的改动指令能够分解成2log2 L个树中区间的改动指令，且改动操作具有叠加性。因此改动操作的时间复杂度为O(log n)。查询操作仅仅
须要累加叶子的全部祖先，它也是O(log n)的。

　　动态统计问题III 有一个包括n个元素的整数数组A。每次能够同一时候给一个区间[l; r]内的数同一时候添加一个数d（d能够为负），也能够询问一个区间[l; r]内全部元素的和。

怎样设计算法，使得改动和询问操作的时间复杂度尽量低？

　　显然前两个问题都是此问题的特殊情况，因此这个问题比前两个问题难度更大。注意到上一个问题线段树仅仅能提供叶结点的真正元素和。由于对于不论什么一个树中区间[l; r]来说，影响它的指令所改动的区间不仅包含它的全部祖先，也包含它的全部后代。

所以[l; r]内的全部元素和应该等于[l; r]的全部祖先的add值加上[l; r]全部后代的add值。

　　但后代有非常多。直接累加的时间开销过大。这里须要再一次利用线段的树的区间相加性质，记录一个附加值sum_of_add。表示以[l; r]为根的子树上全部树中区间的add值之和。

　　改动操作把区间分解为树中区间，改动它们的add值。而且要顺便改动它们父亲的sum_off_add值。

因为区间分解过程訪问的总结点是O(log L)的，因此改动操作是O(log n)的。

　　查询操作把区间分解为树中区间。并统计它们全部祖先的add值之和。再与这些树中区间本身的sum_off_add相加就可以。

 

文章出自《算法艺术与信息学竞赛》 ---- 作者：刘汝佳