《数据结构总结.pdf》由会员分享，可在线阅读，更多相关《数据结构总结.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构总结数据结构总结罗梓璋罗梓璋在 2016 年的冬令营上，我学习了高级数据结构和离线算法，因为分成了两节课，第一节课我在听第一课堂，所以没有高级数据结构的部分。数据结构题：数据结构题：数据结构题典型的要求是：完成一个操作序列的要求。操作序列分为两类：修改和查询。查询是一定有的，修改有时有有时没有。没有修改的一定有初始值，这时可以用静态的数据结构。如果有修改，则修改和查询是交错的，那么要用动态数据结构。而动态数据结构一般比静态的复杂，而且时间复杂度高。如 RMQ 是静态的求区间最小值的数据结构，查询O(1)，建树 O(nlogn)。而线段树可以动态地查询区间最小值，查询O(logn)，建树
2、 O(nlogn)。除此之外，数据结构题还有一个要素：区间。如果查询和修改没有区间，而是求全体的，那么整个数据结构都可以简化很多。例如求第 k 大，如果询问没有区间，那么排个序就好了，动态的就可以用平衡树维护。但是如果询问有区间，那么就要用主席树或者划分树，动态的要树套树。（单点查询也是没有区间的情况之一。）如果修改没有区间，那么就是单点修改，有区间就是区间修改，在线段树上明显体现出来区间的编程难度高些。区间有可能是二维的、三维的甚至更多。解数据结构题很重要的一点是解决区间问题。两种线段树：两种线段树：线段树是最基本的高级数据结构之一，作为之后的基础。线段树按照建树的方式，其实可以分为两种：区
3、间线段树和权值线段树。区间线段树是最基本的，线段树的下标是“位置”，每一个线段是一个位置区间，例如从第 1 个到第 4 个，第 5 个到第 8 个。权值线段树是另外一种建树的方法，下标是“值”，每一个线段是一个值的区间，例如从 1 到 4，从 5 到 8。举个例子：位置：1 2 3 4 5 6 7 8权值：3 2 1 1 4 3 1 4左边的是区间线段树，红色的字是位置的区间内权值的和。右边的是权值线段树，蓝色的值是权值的区间内出现的次数。这两种线段树的灵活运用是接下来的方法的基础。数据结构嵌套：数据结构嵌套：多了一维区间怎么办？最常见的方法就是数据结构套数据结构。（从没有区间到有区间也算。）
4、例如动态求第 k 大，没有区间的时候用平衡树，有区间的话要用区间线段树套平衡树。又例如求区间的和，只有一维可以用树状数组，二维的话用树状数组套树状数组（也就是二维树状数组）。分工问题：内外层的数据结构，分别要做什么？外层的数据结构把外层区间按照某一维划分为小块，在每一小块上，用内层数据结构去处理。外层数据结构里，装的是内层数据结构的指针。完成操作时，先调用外层数据结构，外层数据结构内部在计算的时候，调用内层数据结构，直到最里层的数据结构按照原本的方式完成工作。空间复杂度的话，根据内层数据结构不同，一般是外层的数据结构的空间乘上O(logn)或者 O(n0.5)之类的，因为内层数据结构的大小远小
5、于外层，所以要合并所有内层数据结构来计算空间复杂度。例如区间线段树套数组，如果把每一个数组都当O(n)的话，明显是不对的，因为不同的区间宽度不同，数组的大小也不同。考虑线段树上每一层，总的宽度都是 n，有 logn 层，所以空间总共是 O(nlogn)而不是 O(n*2n)（线段树 O(2n)，乘上 O(n)）。时间复杂度，是内层复杂度乘上外层复杂度，仍然是因为内层的大小不同，所以要合在一起计算，不过一般估算直接乘起来就可以了。可持久化：可持久化：有指针的数据结构，都可以用可持久化的方法来保存历史版本。也就是每修改一次，本来如果要保存原来的，就要建一个新的，因为有很多是没有修改过的，所以可以用
6、指针连回原来的数据结构相应的位置，不用建新的。这样每次修改的空间等于修改的节点的数量。可持久化有什么用呢？首先如果题目要求回到历史版本，那么直接用可持久化就可以了。另外一个用处是：区间前缀和。有些问题的查询是可以相减的，例如有多少个数比k 小。那么我们建权值线段树，只有第一个点建一棵树，前两个建一棵树，前三个建一棵树，直到所有都建一棵树。（树的大小相同。）因为每次只修改了一个点，所以可以用可持久化节省空间。我们发现：对于相同的权值区间，出现的次数是可以相减的。也就是说，可以用前缀和来求位置区间的比k 小的数的数量。第 R 棵树的某一个线段-第 L-1 棵树的对应的线段，就是L,R区间中的数的数
7、量。这时，我们通过前缀和，就做到了减少一维。（每一棵树都是求所有，不是区间。区间限制变为 0 维了。）离线算法：离线算法：由于动态数据结构的复杂，所以出现了离线算法这个东西。离线算法，就是把所有的操作都先读入进来，再处理，处理的过程中不一定按照读入的顺序。与在线算法相对应，在线算法每读入一个操作，就马上处理。（至少是按照顺序处理。）因为离线算法实在是太好用了，所以很多题目都限制必须使用在线算法，例如读入的数是经过处理的，要先计算出上一个结果才可以知道读入的是什么数。离线算法有很多种，最简单的两种是倒序操作和排序操作。倒序操作就是从后往前做，好处例如把插入变成了删除，如果是维护有序的话就很简单了
8、。排序操作是把操作按照区间排序了，如按左端点排序，这样右边就可以用一个静态的数据结构维护了。离线算法的问题是：修改和查询的交替。对于某一个查询来说，有一部分修改是在它后面的，对它没有影响。（对于排序尤其重要。）解决这个问题，离线算法就很好写了。整体二分：整体二分：常见的二分有两种，二分答案和二分查找。整体二分是二分答案的一种。一般的二分答案，每二分一个答案，就再找一遍。整体二分的特殊性在于：每二分一个答案，就把查询和修改分成两份，一份是与左区间有关，另外一份和右区间有关。也就是：如果某些查询和修改要求二分下一次取left,mid，那么分为一部分，递归处理，剩下的要求二分下一次取(mid,rig
9、ht)，那么将这一部分递归处理。（开闭区间看情况）在二分答案的过程中，将询问和修改也分治了。举例：有一串链表的开头。2 种操作：在A,B之间每一个位置都插入一个C求A,B中的第 K 小的数。现在我们先建一棵空的区间线段树，用来统计个数。二分一个答案 mid。然后按照操作顺序，一个一个操作处理。修改：1、如果 Cmid，那么明显这个修改不会使后面任何一个查询的答案为mid，除非 mid变大，把这个修改归为右边的一类。2、如果 Cmid，那么在线段树上A,B区间+1。（是+1 不是+C，只是统计个数。）当 mid 减小的时候，有可能会失效，所以归为左边的一类。查询：先求线段树上A,B区间中的数的个
10、数 Cnt，很明显这就是比 mid 小（或等于）的数的个数。1、Cnt=K-1，答案应该在lef,mid)中，应该归为左边的一类。注意：因为右边一类中，Cmid 的修改已经不见了，而且它的贡献是不会变的，所以右边一类的 K 要减去 Cnt。这样所有的询问和修改都被归为了两类，一类是 mid 要减小的，左边的一类，另外一类是 mid 要增大的，右边的一类。把这两类分开，注意保持同一类里面的顺序不变。（可以放在数组左边和右边，需要辅助数组。）然后分别递归左边的一类和右边的一类。每一次二分都要把每一个操作遍历一遍，所以是O(nlogn)的。CDQCDQ 分治：分治：这也是一种离线算法，是由一个大神叫
11、陈丹琦的提出来的，用处非常广泛，以至于很多题目必须强制在线来防止用CDQ 分治水过。CDQ 分治的步骤很简洁：（下面的区间指操作序列的区间，如2,4表示第 2 个操作到第 4 个操作。）1、递归处理lef,mid区间内的修改和询问。2、处理lef,mid区间内的修改对mid+1,rig区间内的查询的“影响”。3、递归处理mid+1,rig区间内的修改和询问。因为lef,mid区间内每一个修改都一定在mid+1,rig区间的查询之前，所以可以用静态的数据结构把lef,mid区间的每一个修改都储存起来，mid+1,rig的每一个查询直接静态地查询，然后记录这部分结果。（还有mid+1,rig中修改
12、的没有算。）它的核心是：通过分治把动态的变为静态的。分析上面的过程发现有一些条件要满足：1、可以离线。2、查询的结果可以合并。举个简单的例子，不用线段树做区间和查询。一个数组，两个操作：1、让一个点加上一个数2、查询一个区间的和。先递归前一半的操作，再把前一半操作的修改直接修改在一个数组上，求前缀和，后一半操作中的查询可以用前缀和相减直接得到前一半操作对它的影响，把结果加起来，再递归后一半的操作。改为一个区间都加上一个数，也可以不用线段树。递归还是一样的，只是算影响的时候要用扫描。也就是把每一个修改的左右端点分开，把所有端点排序，用扫描的方法来求前缀和。数据结构的降维：数据结构的降维：编写多维
13、数据结构是很麻烦的，嵌套很容易写错，时间复杂度也高。降维的方法就是上面列举的那些的综合运用，例如用 CDQ 分治把动态的变为静态的，这样就可以直接排序了，把其中一维变为时间信息（处理先后），就少了一维。又例如可持久化的使用，把一维的每一个位置都变成一棵树，再用前缀和去减。这样又少了一维。所以以上的方法从区间维度的角度去看，其实都可以看成在减少维度。其他技巧：其他技巧：未知层数嵌套的编写：如果是同一种数据结构，可以只编一个，多记一个当前层数，如果是不同种，还要多记下一层是什么。时间复杂度O(klogn),k 是层数。（有的不是 logn的另外算。）巧用前缀和：前缀和不一定是 1 维的，还可以是 2 维 3 维甚至更多，这时不是单纯地减法了，而是要用容斥原理（重复奇数次的加，偶数次的减）。题目：题目：好多题目不知道是在哪里的。ZJOI2013KBZOJ2683UVA12532SPOJ qtree 2BZOJ 1036BZOJ 3262CQOI 2015BZOJ 3196POI 2014SPOJ COT 10628课堂上老师给了很多题目，题解基本都只有一句话的。