算法竞赛实用数据结构(未完待续)
面向新手= =~.
---
layout: post
categories: [Algorithms]
tags: [算法竞赛, 数据结构, 区间, 字符串]
---
想起那天听到线段树、树状数组、AC自动机...时,夕阳下脸上被映红的苦笑,那是我逝去的青春......
###并查集
并查集这个名字看起来很拽的样子,其实它很简单,顾名思义,它实现的是集合中的合并和查找功能。
- 合并元素a和元素b各自所在的集合。
- 查询元素a和元素b是否属于同一组。
并查集是用树来实现的,每个集合都会用其中一个元素作为根结点来代表这个集合,我们称之为组长,两个集合合并的时候会将树深度小的集合的根结点向树深度大的集合的根结点连边,成为深度大的树的根结点的儿子,就好像大组在吞并小组。那么查询两个元素是否是同一个组,只要分别从这两个元素的父亲开始向上遍历直到到达根结点为止,得到两个元素所在集合的根节点编号,如果相同则是同一个集合,如果不同则是不同集合,就好像问各自组的组长是谁。如图所示:
这些还不是并查集的全部,想象一下两个组合并以后,小组的组长归并到大组后肯定也是个小头目,这样多次的进行吞并后,大组变得越来越壮大于此同时层级也越来越多,组长下面有多个小组长小组长下面又有多个小队长,放在代码实现里看就是一个树的深度越来越大形成了一个很多层的树,在最坏的情况下n个成员可能形成一个n层的树,就从树退化成了一个链表,这是当你询问最底层的小弟你们组老大是谁的时候,他可是懵懂无知的小痞子啊,根本没法接触到上层,所以他只能问自己的老大,老大再问老大的老大,这样层层向上遍历,等到遍历到组长是谁的时候,已经花费很长时间了,所以你决定学习中国古代秦始皇的中央集权制,取消了分层管理的制度,把每个组的所有成员都交给组长一手管理,在代码实现里来看就是把树的所有结点都作为根节点的儿子,这样的话以后问小弟你们组长是谁的时候小弟一下子就答出来了,真是高效的黑帮管理制度,然而选择在何时进行权力的收拢呢,在吞并小组的时候不太合适,刚刚吞并,军心不稳,此时收拢权力也是费力不讨好的,你想出了一个好办法就是每次在查询某个小弟的大哥是谁的时候,以自己不耐烦等待为理由要求组长把该小弟向上询问的所有小队长小组长包括他自己都归到组长手下来管,这样下次再问时就快捷的多了。在代码实现中也是这样,每次查询的时候会把元素向上遍历时经过的所有结点包括自己都直接连到根上,下次再查询这些结点就很快了。这个过程学名叫**路径压缩**。
并查集我准备就讲到这里,本文只是描述一个直觉上的印象,希望大家结合代码再深一步的去理解,这里给出一些练习题目:
- [食物链](http://poj.org/problem?id=1182)
- [X-Plosives](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3601)
- [Corporative Network](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4075)
###优先队列
优先队列的概念很好理解,简单来说,它是保证每次出队的元素是队列中最大(小)元素的队列,在STL里面有现成的实现 `priority_queue` ,STL的使用我就不必讲了,本文主要侧重于各种使用数据结构的概念及原理。
如果让你来实现这样一个功能,你要怎样实现,有一个想法是先把队列元素排个序就可以了,然而还要考虑作为一个队列是需要很多次入队操作的,如果基于有序数组的实现,每次入队都要重新排列整个队列,复杂度是O(n)。
有没有更快的方式呢,如果你数据结构没忘光是不是会想起**二叉查找树**呢(后面我会专门讲到),名字好难听,都是二叉一族的...,二叉查找树也叫有序查找树,它可以在插入的时候保证数据的有序性,且插入的期望时间复杂度是O(log n),二叉查找树除叶子结点外的每一个结点的值,都大于它的左子结点,小于它的右子结点,所以最左面的叶子结点就是整棵树的最小结点,在优先队列的应用中每次只要找到这个结点并删除它就可以完成出队操作,期望时间复杂度也是O(log n)。
二叉查找树其实并不是最好的选择,因为它有可能退化成线性链表,此时的插入删除复杂度为O(n),如果使用平衡树,比如AVL树或是红黑树倒是可以解决这个问题,但是实现起来又过于复杂,有木有一个高效简洁的实现方案呢?
**二叉堆(binary heap)**,它是解决这个问题的巧妙方案,二叉堆也是树,是一种**完全二叉树**,也就是说除最后一层外,其他层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点。我们看一下二叉堆的概念和实现。
二叉堆的主要属性是,父亲的值永远大(小)于儿子,具体是大还是小,要看你应用场景是需要最大堆还是最小堆了。就如同二叉查找树一样,保证这个属性的关键在于插入和删除时候对结点的处理,我找几个图来讲这两个过程:
以上两图是在最小堆中插入14的过程,由于是完全二叉树,所以插入一个元素后,堆的最下层最右侧一定会多出一个空位,先尝试把14填到该空位中,发现14比父节点31要小,不符合最小堆的特性,于是我们将31移到下面空位,空出自己的位置作为新空位,依次类推,14尝试填到新的空位依旧比它的父节点21要小,于是再次把21移到下面空位,留出新的空位,此时14放到空位处恰好满足最小堆的特性,插入任务达成。说白了就是小人物不断攀爬把前辈一个个踩到脚底下从而走上人生巅峰的过程,说好听点叫做:**percolate up**。
以上两图是在最小堆中删除根节点也就是最小项13的过程,由于是完全二叉树,删除一个元素后,堆最下层最右侧的元素31必定要拿开放到其他位置,堆中删除元素的过程实际上就是给31这哥们找个地方安置的过程,首先要把根节点的13给踢开留下一个空位,我们试着把31放进去发现31比13的左膀右臂14和16都要大,所以不可行,那么选择数值较小的14移到上面的空位去,留下自己的位置作为新的空位,依次类推,把31放进新空位依旧不可行,于是把14的子节点中数值较小的21移上去,留下新空位,此时31放到这里恰到好处,于是删除根节点任务达成。这个过程叫做:**percolate down**。
二叉堆的特性讲完了,看来已经完美支持优先队列的功能了,入队操作就是二叉堆的插入,出队操作就是二叉堆的删除根节点。看起来似乎并不复杂,那么如何实现呢?之前我多次强调二叉堆是完全二叉树,根据完全二叉树的特性,它可以用数组来实现,给每个结点顺次编号,每一个结点左儿子的编号等于自己编号*2N,右儿子的编号等于自己编号*2N+1。如图所示:
上图数组中的元素对应着堆中的结点。
这里留几道与优先队列相关的题目:
- [Expedition](http://poj.org/problem?id=2431)
- [Fence Repair](http://poj.org/problem?id=3253)
- [Argus](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3644)
- [K Smallest Sums](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3148)
###Sparse Table
我们先来提出一个问题,范围最小值问题(Range Minimum Query)简称RMQ : *给出n个元素的数组 A1,A2,A3,...,An, 设计一个数据结构, 支持查询操作Query(L,R): 计算子序列A[L],A[L+1],...,A[R]的最小值.*
这看起来是个非常简单的问题, 最朴素的方法就是遍历子序列找到最小值就, 但是想象下数据量非常大比如上亿的情况, O(n)的查询时间是不可忍的, Sparse Table就是解决该问题的有力武器, 它有O(nLogn)的预处理时间,而查询的复杂度仅为O(1).
看一下具体的做法, 首先预处理要达到的效果是, 得到原数组从一个位置开始长度为1,2,4,8,...的区间内的最小值并存到一个表中, 这个过程中, 长度为2^i的区间最小值只需要通过比较2个长度为2^(i-1)的区间最小值即可得到, 也就是说后面的计算直接用到前面已经存在表格里面的计算结果, 这是简单的动态规划, 我画了一张图示来表现这个过程:
简单说下图的意思, 先对原数组每一个位置取长度为1的区间,每个区间取最小值存起来也就是range=1那一行, 然后对原数组每个位置取长度为2的区间, 每个区间取最小值存起来也就是range=2那一行,然后对原数组每个位置取长度为4的区间, 每个区间取最小值存起来, 也就是range=4那一行,这时你会发现我只要利用range=2那一行中的值就可以得到range=4那一行, 不需要对原数组进行重新计算,就这样依次类推得到一个二维数组, 也就是我们预处理的结果, 在实际编码中一般还是存储最小值的下标, 这里简单起见直接存最小值了.
好啦有了这个数组我们就可以进行O(1)的查询了, 怎么做呢, 比如要查询[L, R]区间的最小值, 我们现在已经有了所有2^i长度区间的最小值, 那么我们就从表格中找到从L开始不超出[L, R]的最长的一个2^i区间, 得到它的最小值a, 然后在从R开始向前找到一个同样长度的区间得到最小值b, 于是[L, R]区间的最小值就是min(a, b). 如图所示:
这两幅图, 前者是求[1, 7]区间的最小值, 结果为7, 后者是求整个数组也就是[0, 9]的最小值, 结果为1.
留一道相关题目:
[Frequent values](http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2176)
###平方分割
###线段树
###树状数组
###线段树深入
###二叉查找树
1. Treap
2. 伸展树
###Trie
###KMP 算法
###Aho-Corasick 自动机
###后缀数组
###最长公共前缀(LCP)
原文见我的blog: God-Mode
---
layout: post
categories: [Algorithms]
tags: [算法竞赛, 数据结构, 区间, 字符串]
---
想起那天听到线段树、树状数组、AC自动机...时,夕阳下脸上被映红的苦笑,那是我逝去的青春......
###并查集
并查集这个名字看起来很拽的样子,其实它很简单,顾名思义,它实现的是集合中的合并和查找功能。
- 合并元素a和元素b各自所在的集合。
- 查询元素a和元素b是否属于同一组。
并查集是用树来实现的,每个集合都会用其中一个元素作为根结点来代表这个集合,我们称之为组长,两个集合合并的时候会将树深度小的集合的根结点向树深度大的集合的根结点连边,成为深度大的树的根结点的儿子,就好像大组在吞并小组。那么查询两个元素是否是同一个组,只要分别从这两个元素的父亲开始向上遍历直到到达根结点为止,得到两个元素所在集合的根节点编号,如果相同则是同一个集合,如果不同则是不同集合,就好像问各自组的组长是谁。如图所示:
这些还不是并查集的全部,想象一下两个组合并以后,小组的组长归并到大组后肯定也是个小头目,这样多次的进行吞并后,大组变得越来越壮大于此同时层级也越来越多,组长下面有多个小组长小组长下面又有多个小队长,放在代码实现里看就是一个树的深度越来越大形成了一个很多层的树,在最坏的情况下n个成员可能形成一个n层的树,就从树退化成了一个链表,这是当你询问最底层的小弟你们组老大是谁的时候,他可是懵懂无知的小痞子啊,根本没法接触到上层,所以他只能问自己的老大,老大再问老大的老大,这样层层向上遍历,等到遍历到组长是谁的时候,已经花费很长时间了,所以你决定学习中国古代秦始皇的中央集权制,取消了分层管理的制度,把每个组的所有成员都交给组长一手管理,在代码实现里来看就是把树的所有结点都作为根节点的儿子,这样的话以后问小弟你们组长是谁的时候小弟一下子就答出来了,真是高效的黑帮管理制度,然而选择在何时进行权力的收拢呢,在吞并小组的时候不太合适,刚刚吞并,军心不稳,此时收拢权力也是费力不讨好的,你想出了一个好办法就是每次在查询某个小弟的大哥是谁的时候,以自己不耐烦等待为理由要求组长把该小弟向上询问的所有小队长小组长包括他自己都归到组长手下来管,这样下次再问时就快捷的多了。在代码实现中也是这样,每次查询的时候会把元素向上遍历时经过的所有结点包括自己都直接连到根上,下次再查询这些结点就很快了。这个过程学名叫**路径压缩**。
并查集我准备就讲到这里,本文只是描述一个直觉上的印象,希望大家结合代码再深一步的去理解,这里给出一些练习题目:
- [食物链](http://poj.org/problem?id=1182)
- [X-Plosives](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3601)
- [Corporative Network](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4075)
###优先队列
优先队列的概念很好理解,简单来说,它是保证每次出队的元素是队列中最大(小)元素的队列,在STL里面有现成的实现 `priority_queue` ,STL的使用我就不必讲了,本文主要侧重于各种使用数据结构的概念及原理。
如果让你来实现这样一个功能,你要怎样实现,有一个想法是先把队列元素排个序就可以了,然而还要考虑作为一个队列是需要很多次入队操作的,如果基于有序数组的实现,每次入队都要重新排列整个队列,复杂度是O(n)。
有没有更快的方式呢,如果你数据结构没忘光是不是会想起**二叉查找树**呢(后面我会专门讲到),名字好难听,都是二叉一族的...,二叉查找树也叫有序查找树,它可以在插入的时候保证数据的有序性,且插入的期望时间复杂度是O(log n),二叉查找树除叶子结点外的每一个结点的值,都大于它的左子结点,小于它的右子结点,所以最左面的叶子结点就是整棵树的最小结点,在优先队列的应用中每次只要找到这个结点并删除它就可以完成出队操作,期望时间复杂度也是O(log n)。
二叉查找树其实并不是最好的选择,因为它有可能退化成线性链表,此时的插入删除复杂度为O(n),如果使用平衡树,比如AVL树或是红黑树倒是可以解决这个问题,但是实现起来又过于复杂,有木有一个高效简洁的实现方案呢?
**二叉堆(binary heap)**,它是解决这个问题的巧妙方案,二叉堆也是树,是一种**完全二叉树**,也就是说除最后一层外,其他层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点。我们看一下二叉堆的概念和实现。
二叉堆的主要属性是,父亲的值永远大(小)于儿子,具体是大还是小,要看你应用场景是需要最大堆还是最小堆了。就如同二叉查找树一样,保证这个属性的关键在于插入和删除时候对结点的处理,我找几个图来讲这两个过程:
以上两图是在最小堆中插入14的过程,由于是完全二叉树,所以插入一个元素后,堆的最下层最右侧一定会多出一个空位,先尝试把14填到该空位中,发现14比父节点31要小,不符合最小堆的特性,于是我们将31移到下面空位,空出自己的位置作为新空位,依次类推,14尝试填到新的空位依旧比它的父节点21要小,于是再次把21移到下面空位,留出新的空位,此时14放到空位处恰好满足最小堆的特性,插入任务达成。说白了就是小人物不断攀爬把前辈一个个踩到脚底下从而走上人生巅峰的过程,说好听点叫做:**percolate up**。
以上两图是在最小堆中删除根节点也就是最小项13的过程,由于是完全二叉树,删除一个元素后,堆最下层最右侧的元素31必定要拿开放到其他位置,堆中删除元素的过程实际上就是给31这哥们找个地方安置的过程,首先要把根节点的13给踢开留下一个空位,我们试着把31放进去发现31比13的左膀右臂14和16都要大,所以不可行,那么选择数值较小的14移到上面的空位去,留下自己的位置作为新的空位,依次类推,把31放进新空位依旧不可行,于是把14的子节点中数值较小的21移上去,留下新空位,此时31放到这里恰到好处,于是删除根节点任务达成。这个过程叫做:**percolate down**。
二叉堆的特性讲完了,看来已经完美支持优先队列的功能了,入队操作就是二叉堆的插入,出队操作就是二叉堆的删除根节点。看起来似乎并不复杂,那么如何实现呢?之前我多次强调二叉堆是完全二叉树,根据完全二叉树的特性,它可以用数组来实现,给每个结点顺次编号,每一个结点左儿子的编号等于自己编号*2N,右儿子的编号等于自己编号*2N+1。如图所示:
上图数组中的元素对应着堆中的结点。
这里留几道与优先队列相关的题目:
- [Expedition](http://poj.org/problem?id=2431)
- [Fence Repair](http://poj.org/problem?id=3253)
- [Argus](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3644)
- [K Smallest Sums](http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=229&page=show_problem&problem=3148)
###Sparse Table
我们先来提出一个问题,范围最小值问题(Range Minimum Query)简称RMQ : *给出n个元素的数组 A1,A2,A3,...,An, 设计一个数据结构, 支持查询操作Query(L,R): 计算子序列A[L],A[L+1],...,A[R]的最小值.*
这看起来是个非常简单的问题, 最朴素的方法就是遍历子序列找到最小值就, 但是想象下数据量非常大比如上亿的情况, O(n)的查询时间是不可忍的, Sparse Table就是解决该问题的有力武器, 它有O(nLogn)的预处理时间,而查询的复杂度仅为O(1).
看一下具体的做法, 首先预处理要达到的效果是, 得到原数组从一个位置开始长度为1,2,4,8,...的区间内的最小值并存到一个表中, 这个过程中, 长度为2^i的区间最小值只需要通过比较2个长度为2^(i-1)的区间最小值即可得到, 也就是说后面的计算直接用到前面已经存在表格里面的计算结果, 这是简单的动态规划, 我画了一张图示来表现这个过程:
简单说下图的意思, 先对原数组每一个位置取长度为1的区间,每个区间取最小值存起来也就是range=1那一行, 然后对原数组每个位置取长度为2的区间, 每个区间取最小值存起来也就是range=2那一行,然后对原数组每个位置取长度为4的区间, 每个区间取最小值存起来, 也就是range=4那一行,这时你会发现我只要利用range=2那一行中的值就可以得到range=4那一行, 不需要对原数组进行重新计算,就这样依次类推得到一个二维数组, 也就是我们预处理的结果, 在实际编码中一般还是存储最小值的下标, 这里简单起见直接存最小值了.
好啦有了这个数组我们就可以进行O(1)的查询了, 怎么做呢, 比如要查询[L, R]区间的最小值, 我们现在已经有了所有2^i长度区间的最小值, 那么我们就从表格中找到从L开始不超出[L, R]的最长的一个2^i区间, 得到它的最小值a, 然后在从R开始向前找到一个同样长度的区间得到最小值b, 于是[L, R]区间的最小值就是min(a, b). 如图所示:
这两幅图, 前者是求[1, 7]区间的最小值, 结果为7, 后者是求整个数组也就是[0, 9]的最小值, 结果为1.
留一道相关题目:
[Frequent values](http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2176)
###平方分割
###线段树
###树状数组
###线段树深入
###二叉查找树
1. Treap
2. 伸展树
###Trie
###KMP 算法
###Aho-Corasick 自动机
###后缀数组
###最长公共前缀(LCP)
原文见我的blog: God-Mode
能续么.....待了两年了......blog都404了....
> 我来回应