c语言背包问题_c语言背包问题几种解法_背包问题贪心算法(4)

(7).数据结构之提高篇(包括并查集,树状数组,线段树)

数据结构还有一些相对来说比较高级的应用，这些知识点可能会作为一个知识点单独考查，首先是并查集，并查集的基本思想是在一个集合中选出一个元素作为一个集合代表元素，通过对这些代表元素的操作来实现集合之间的合并操作，在求最小生成树的经典算法Kruscal中也会用到并查集来判断两个元素是否属于同一条边，这在下一部分图论的总结中会提到。并查集也有很多的题目可以做，经典题有食物链，搞的虫子，帮派结伙等，并查集还有一个变型就是从一个集合中删除某一个元素，我们知道，普通的并查集是不包括删除元素的功能的，而删除元素的实现其实也很简单，就是对每个点都建立一个索引，一开始每个点的索引都指向自己，当一个元素被删除掉的时候，先建立一个新的不属于任何集合的新点，在把被删除掉的点索引到那个新点之上即可。第二部分是树状数组，他支持在O(nlogn)的复杂度内算出区间内的元素之和，他的思想很是巧妙，就是树状数组总结：假设c[]为树状数组，a[]为原数组，则两者之间存在这么一个关系，c[i]代表的意义是从a[i]开始往前2^k个元素的和(k为i化成二进制后尾部包含的0的个数)。由位运算的性质可以得到：对于i来说，i&(-i) = 2^k，那么树状数组的基本功能就能明白了。

树状数组也有比较多的题，PKU_1990，PKU_2828，PKU_2155等等。最后我想说一下线段树，线段树是一个非常强大的数据结构，他支持在O(nlogn)的复杂度内对区间范围内的元素进行修改，删除等操作，和并查集，树状数组不同的是，线段树的实现非常灵活，一道题一个样，几乎没有什么定式，当然了，最为基本的思想就是每个节点代表一个区间，他的左右子树分别为左半区间和右半区间，如此这般地递归定义，直到为一个点或者包含一个单位为止。线段树也有几个基本模型和经典例题，首先我想讲的是线段树的一种相对而言比较简单但是非常经典的应用来引入线段树的概念等一系列问题，即染色问题。以PKU_2777为例，题目大意是有一块长度为L厘米的板，每厘米可以看成一个单位区间，颜色的种类由数字表示，一开始每个区间的颜色都是1，而现在要对这种树进行O次操作，操作有两种，第一种是将区间A到B的颜色都染成C颜色，第二种是询问区间A到B之间一共有几种颜色。最简单的想法可能是开个长度为L的数组a[]，而a[i]存的就是第i格的颜色，但是可行吗？我们来看下数据范围，L的范围是十万，O的范围也是十万，那么算法复杂度就是O(LO)，明显会超时，所以我们选择用线段树来帮助我们解决这个问题，其实线段树这个名词并不能很好地阐述它强大的功能，我更喜欢他的学术名词——区间树，同其他的树一样，他可以在O(logL)的时间内对树进行维护操作，这也就意味着他可以在O(logL)的时间内对一段区间进行一系列的操作。

正是线段树这种高效，让他在RMQ问题，以及求矩形合并面积，周长等一系列问题中得到了充分的应用。这里我想讲一下RMQ问题(即求区间内最大or最下值的问题)，众所周知，RMQ问题有一种O(NlogN)的预处理以及O(1)时间求出任意区间内最大or最小值的离线算法（所谓离线，即不能在求的过程中动态地改变或者插入区间的值），即ST(Sparse Table)算法，相比之下，线段树并没有效率上的优势，但ST算法有个局限性，就是不支持操作，而线段树则没有这种限制，由此可知，线段树的强大。c语言背包问题线段树还有一个高级的应用就是对于区间最值信息的维护，相应的经典题有很多，也有一定的难度，PKU_2482，PKU_1151(求n个矩形合并后的面积)，PKU_1177(求n个矩形合并后的边界周长)等等。最值的维护要抓住的基本思想就是递归地维护每一颗子树，利用子树的信息去维护父亲。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-24376-4.html