《算法艺术与信息学竞赛》学习指导(下)

《《算法艺术与信息学竞赛》学习指导(下)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第6章离散结构上的算法本章讨论离散结构上的算法。典型的离散结构，例如序列、树、图和字符串有各自的数学特性，由此产生出各种各样的算法，其中不乏经典之作。6.1序列上的问题本节介绍序列上的算法，包括排序、统计问题、序列上常用的数据结构等。虽然序列的结构比较简单，但本节介绍的很多算法都是非常巧妙的。6.1.1线段树和树状数组有很多动态问题需要用到专门的数据结构。本节介绍其中两种。线段树线段树(intervaltree)是把区间逐次二分得到的一树状结构，它反映了包括归并排序在内的很多分治算法的问题求解方

2、式。图8.1是一棵典型的线段树，它对区间[1,10]进行分割，直到单个点。这棵树的特点是：1.每一层都是区间[a;b]的一个划分，记L=b¡a6.1序列上的问题3012.一共有log2L层3.给定一个点p，从根到叶子p上的所有区间都包含点p，且其他区间都不包含点p。4.给定一个区间[l;r]，可以把它分解为不超过2log2L条不相交线段的并。其中第四点并不是很显然，图8.1显示了[2,8]的分解方式，深灰色结点为分解后的区间，浅灰色结点是递归分解过程中经过的结点。为了叙述方便，下面称树中的结点所

3、对应的区间为树中区间。从第3点和第4点可以得出结论：修改一个点只用修改log2L个树中区间信息，而统计一个区间只需要累加2log2L个树中区间的信息，且访问的总结点数是O(logL)的。两个操作都很容易实现。动态统计问题I有一个包含n个元素的整数数组A，每次可以修改一个元素，也可以询问某一个区间[l;r]内所有元素的和。如何设计算法，使得修改和询问操作的时间复杂度尽量低？方法一直接做，则修改操作是O(1)的，但询问需要进行累加，时间复杂度为O(r¡l)，最坏情况为O(n)。方法二建立一棵线段树，

4、每个树中区间记录该区间的元素和，则由刚才的结论，修改元素时只需要修改log2L个树中区间的元素和，而统计时只需要累加2log2L个树中区间的元素和，两个操作都是O(logn)的，比方法一好很多。动态统计问题II有一个包含n个元素的整数数组A，每次可以同时给一个区间[l;r]内的数同时增加一个数d（d可以为负），也可以询问某一个数Ai的值。如何设计算法，使得修改和询问操作的时间复杂度尽量低？302离散结构上的算法如何快速修改一个区间？修改一个树中区间[a;b]将影响到以[a;b]为根的整棵子树和它

5、的所有祖先，所以如果沿用刚才的线段树定义，是不可能快速实现区间修改操作的。解决方法是借用数据结构中常用的懒操作"的思想，只记录有哪些操作需要执行，而不去真正执行这些操作。换句话说，在需要给树中区间[l;r]的元素同时增加d时，我们只记录曾经有一条指令add(l,r,d)"就可以了。我们把记录的这个值称为树中区间的add值，则叶结点的元素值为它所有祖先的add值之和。根据前面的结论，每一条任意区间的修改指令可以分解成2log2L个树中区间的修改指令，且修改操作具有叠加性，因此修改操作的时间复杂

6、度为O(logn)。查询操作只需要累加叶子的所有祖先，它也是O(logn)的。动态统计问题III有一个包含n个元素的整数数组A，每次可以同时给一个区间[l;r]内的数同时增加一个数d（d可以为负），也可以询问一个区间[l;r]内所有元素的和。如何设计算法，使得修改和询问操作的时间复杂度尽量低？显然前两个问题都是此问题的特殊情况，因此这个问题比前两个问题难度更大。注意到上一个问题线段树只能提供叶结点的真正元素和，因为对于任何一个树中区间[l;r]来说，影响它的指令所修改的区间不仅包括它的所有祖先，

7、也包括它的所有后代。所以[l;r]内的所有元素和应该等于[l;r]的所有祖先的add值加上[l;r]所有后代的add值。但后代有很多，直接累加的时间开销过大。这里需要再一次利用线段的树的区间相加性质，记录一个附加值sumofadd，表示以[l;r]为根的子树上所有树中区间的add值之和。修改操作把区间分解为树中区间，修改它们的add值，并且要顺便修改它们父亲的sumo®add值。由于区间分解过程访问的总结点是O(logL)的，因此修改操作是O(logn)的。查询操作把区间分解为树中区间，并统计它

8、们所有祖先的add值之和，再与这些树中区间本身的sumo®add相加即可。线段树的应用并不限于此，以后我们会看到更多例子。树状数组树状数组是一个很有意思的数据结构，它的应用没有线段树广，但是对于一类特定问题，它的程序非常容易编写。再谈动态统计问题I设数组C[i]=a[i¡2k+1]+[i¡2k+2]+:::+a[i]，其中k为i在二进制形式下末尾0的个数，则和式的起点是把i的最后一位1变成0，再加1。根据定义，6.1序列上的问题303我们有iC[i]的定义式C[i]的递推式1a[1]a[1]2a