高级数据结构选讲杭州第二中学李建手机：13386510512QQ：43075478一、一个学生从零到NOI金牌需要经历哪些阶段？二、在这些阶段中我们需要做好哪方面的工作？语言基础+gdb(调试工具)数组、模拟、递归简单的动态规划和搜索简单的图论简单的高级数据结构字符串图论高级数据结构数学动态规划人类智慧NOIP阶段NOI阶段一、一个学生从零到NOI金牌需要经历哪些阶段？二、在这些阶段中我们需要做好哪方面的工作？在NOIP阶段，我们需要将学生领入信息学这个陌生的世界，需要我们手把手教学生写程序，因此要求老师能够自己能够编写代码，能够帮助学生查错，幸运的是，该阶段要求的算法理解及编写复杂度并不高！到了NOI阶段，算法的广度和深度直接是呈“指数爆炸”的，并且经常会有新潮的算法冒出来，此时再让我们所有老师熟练运用相关算法就显得太勉为其难（当然千古神犇老师除外），所以这个阶段我们需要锻炼学生的自主学习能力，但是让学生自主学习并不是老师就彻底沦为一个机房管理员，我们需要让学生有组织有模块有系统的高效自学。而让学生自主学习基本包含确定专题、寻找讲稿、理解算法、代码实现、学以致用。在这些过程中，我们需要思考我们有哪些环节可以参与进去！确定专题：保证学生不走弯路，循序渐进的学习！（PS：连线段树都不会就去学主席树，那就糟糕了！）寻找讲稿：某度上讲稿参差不齐，学生经常看了很久，不理解是正常的，理解了的发现讲稿是错的事情也常有发生，所以我们老师需要帮学生筛选讲稿，让学生不至于浪费时间！理解算法：筛选讲稿的时候已经要求我们老师去理解这个算法，我们不一定必须将代码实现出来，但是必须要理解其核心过程，在学生学习的时候也可以做相关讲解，加快学生的学习进程。代码实现：这个只能学生亲自上场搏杀了！学以致用：在学生学习一个算法后，最后帮学生找3-5道例题，加以巩固。本次交流的主要内容恰巧前段时间刚组织学生学习了高级数据结构专题，我就将我学习的一些算法和大家一起交流分享一下！一、堆用途：在线求最值存储：插入：O(logn)删除（仅能删除最值）：O(logn)询问：O(1)11223344556677889910101111121213131414一、堆向下调整（以小根堆为例）：1313223344556677889910101111121222131333445566778899101011111212二、并查集二、并查集-路径压缩（避免链状退化）三、分块思想包含n个元素的整数数组A，每次可以C(i,j):修改一个元素A[i]=jQ(i,j):询问A[i]+A[i+1]+…+A[j]的值如何设计算法，使得修改和询问操作的时间复杂度尽量低？显然存在修改O(1)，查询O(n)的算法。从算法瓶颈处开始思考，否则仅仅是常数优化，无法降低时间复杂度三、分块思想每次重新计算，一些未被修改区间也经常被重复求和，于是我们可以将A[1..n]均分成sqrt(n)块，每块内部的元素为sqrt(n)个。修改操作时只需要修改A[i]及A[i]所在的块。询问操作时是需要枚举i和j所在的块内部，及其之间的块。时间复杂度在O(sqrt(n))级别。四、树状数组在分块思想的基础上，我们进一步思考是否有比sqrt(n)更优秀的分组方法。logn？？？基于2进制的分组方式！2进制变10进制是怎么做的？！C[i]=A[i-2k+1]+…+A[i]k为i在二进制下末尾0的个数，令LOWBIT(i)=2k通俗版本：C[52->110100]=A[110100]+A[110011]+A[110010]+A[110001]4=LOWBIT(52)=52and(52xor(52-1))四、树状数组Sum[52->110100]=C[110100]+C[110000]+C[100000]修改操作：我们只需要思考A[110100]的修改会带来哪些C[]的改变，参考询问的过程我们能够轻易的发现O(logn)级别的解决方案。至此，我们获得了基于二进制且查询和修改都是O(logn)的算法A[110100]+A[110011]+A[110010]+A[110001]110000=110100–LOWBIT(110100)完美！五、线段树六、字母树（Trie树）通过树结构来节省公共前缀的开销。六、字母树（Trie树）应用：字符串排序：在字母树上先序遍历公共前缀计算：公共祖先字符串检索：在字母树上跑一遍即可七、Treap[传统旋转式]Treap=Tree（二叉搜索树）+Heap（期望平衡）七、Treap[传统旋转式]我们按照满足二叉搜索树的性质进行插入，因此我们需要一种不改变二叉搜索树性质的情况下对Treap进行调整，使其满足的堆的...
