over 2 years ago

近来疏于数据结构已久..

这里来列一列一些基础的数据结构题搞法。


线段树

线段树是非常常见的一个数据结构,变化也是最多的。

有句话说得好,最难的数据结构题一定是线段树题。

一些线段树的奇技淫巧:

李超树

这其实上不是一种数据结构.. 只是一种思想。

传统的线段树做法在标记进行下放和信息上传的时候往往只会用到一个节点和它左右孩子的信息,而李超树就是在对线段树信息进行修改和上传的时候,对子树进行递归修改/查询。

相关例题:
SDOI2016 游戏
BlueMary开公司

历史最值询问

这类问题的传统做法是用懒标记,每个节点额外记录一个标记pre, 表示从上次下传到现在为止add标记所到达过的最大值。

这样下传的时候就可以根据pre和add来更新历史最大值了。

这个做法可以扩展到所有包含与最值查询方向相同的最值操作。例如要查询的是区间历史最大值,那么这个做法可以支持的操作有加减操作,区间对一个数取max,以及其他可以用这两个操作替代的操作(如区间赋值)

因为可以把标记看成一个二元组(x, y) 代表先对数加上x再对y取max, 这个标记等效于一个分段函数,第一段是一条与x轴平行的线,第二段是一个斜率为1的直线。 而历史最大值的标记在更新的时候,相当于把两个标记放到坐标系当中,然后取出上方的部分。

形如:

发现这个分段函数的形式和原来相同,因此这个历史最大值是可以用标记来维护的。

相关例题:
CPU监控
V

区间最值操作

这个就是赛格蒙特彼茨啦。它能解决一类区间最值操作(区间取min取max), 主要思想是将一个区间内的元素分成最小值/最大值的信息和其他元素的信息来维护,同时额外维护区间次大/次小值。这样每次对区间取最值的操作就可以分解为一些区间的最值的加减操作。对于区间历史最值的询问,可以用引入辅助数组的方法来将历史最值询问转化为区间和的询问。

相关例题:
元旦老人与数列


可持久化数据结构

可以访问历史版本的数据结构

OI中的用途主要有:

  1. 出题人执意可持久化
  2. 高维查询中降维 (有时是一些在线算法的组成部分)

要想通过可持久化来降维,信息必须可减(如数量)。

可持久化线段树(主席树)

这是可持久化数据结构中应用最为广泛也是变化最多的东西。

本身是一棵线段树,因此可以打标记,上传下传.. (主席树下传的时候要把孩子都复制一份后再下传)

比较经典的问题有区间K小值。

相关例题:

GERALD07
谈笑风生

可持久化平衡树

可持久化平衡树的实现一般来说有AVL和treap两种,可持久化AVL的空间常数过大.. 一般来说都是写treap的。

一般要实现可持久化平衡树的题目都是出题人执意可持久化的偏题

相关例题:
CTSC2015 shallot
WC2016 鏖战表达式

可持久化数组/并查集...

这种东西用主席树都是可以实现的。


树分治

1.基于链的分治算法

这个主要就是用轻重链树链剖分的方法,把整个树划分成若干条重链,其中每个点都属于且仅属于一条重链,且每个点到根的路径最多经过条重链。

这个算法主要维护的东西是链剖序, 在一条重链上相邻的两个点一定在链剖序上相邻。

可以利用维护序列的数据结构,方便地维护一段重链上的信息,这样就把树链上的问题转化为了序列问题。

树上任意一条路径都可以被划分成条重链,因此一次树链的操作都可以分解为次重链操作。

链剖序可以自然地与dfs序复合,这样就可以同时维护链上的信息和子树中的信息了。

相关例题:
NOI2015软件包管理器
SDOI2011 染色

2.基于点的分治算法

点分治是用来处理树上任意路径问题的。

核心思想是:每次找一个点,计算出所有经过这个点的路径的答案,然后递归到子树中继续求解。

每次找重心进行分治可以保证分治的总层数为

点分治这个框架还是比较强的,可以嵌套进去很多东西。

除此之外,因为点分治本身是一个高度为的分治结构,因此可以维护这个分治树结构来回答一些动态修改的问题。

相关例题:
Normal
ZJOI2015 幻想乡战略游戏


动态树

动态树顾名思义就是动态维护一棵树,比如支持
– 加边
– 删边
– 换根
– 链操作
– 子树操作

处理动态树问题的东西一般来说有LCT, ETT, top tree等。

top tree我不会, 就不说了

LCT

算法的基本思路是动态维护树剖,每一条重链用一棵splay维护。

假如不看虚边的话,这些重链是很多个splay 加上虚边它们就是原树。

核心操作是access,作用是将一个点到根的路径设为重链,也就把它们弄到了一棵splay里面。access操作的核心操作是虚实切换(非常重要!!)。

LCT除了做一些链操作的题目之外,还能维护只有加边的MST.. 以及类似最小极差路径之类的衍生问题。

LCT也是一个比较厉害的工具,可以将它看做一个动态的链剖序,也可以在上面套各种各样的东西。

LCT是可以简单维护子树信息的, 如果信息可减,那么只要在access轻重边切换的时候更新信息即可,如果信息不可减,那么需要维护一个额外的数据结构(堆/set)来进行维护。

相关例题:
决战
NOI2014 魔法森林

ETT

ETT其实就是用一个支持区间操作的平衡树(treap/splay) 动态维护一棵树的dfs序,这样就能方便地进行子树操作了。

top tree

其实top tree是一个LCT上套splay的结构.. 可以看做一个动态的链剖序+dfs序, 可以同时支持子树操作和链操作。

相关例题:
sone1

EXT: 维护树上同色联通块信息

此类问题有一个通用做法是LCM。 主要思想是对每种颜色建一个森林,如果一个点的颜色和这个森林代表的颜色相同就在这个森林中向父亲节点连边。这样每个同色联通块就是一棵树(除掉根以外), 根据题目要求用LCT / ETT进行维护即可。

QTREE6
QTREE7


虚树

看上去比较简单但是应用性非常强的东西。

构造比较简单。

实现方式大致上就是先补充dfs序相邻的缺失的lca

然后再用一个栈来实现虚树的连边。

然后就可以在虚树上dp了。

对于一类问题,我们可以用dp求出虚树上每个点的信息,然后把询问点定位到它在虚树上最近的那个点然后查询。

给定一个虚树和一个点u,如何求出u连在虚树上哪条边上?

考虑建虚树的过程,把u插入虚树的dfs序中,对它相邻的两个位置求lca,其中深度较大的那个lca就一定是u的第一个在虚树上的祖先,再进行一次二分就可以知道u到底是接在虚树的哪条边上了。

相关例题:
HNOI2014 世界树
Kingdoms and its cities


整体二分

整体二分是一种对答案进行分治的离线算法。核心思想是类似快速排序的划分操作。

许多问题往往要预处理一些操作才能快速回答一些询问,整体二分就是处理这类问题的方法。

能用整体二分处理的问题要满足条件:

1.询问的答案具有可二分性
2.修改对判定答案的贡献互相独立,修改之间互不影响

好多树套树的题目都可以用整体二分来做。

相关例题:
ZJOI2013 K大数查询
矩阵乘法


按时间分治

CDQ分治是处理数据结构问题的经典离线算法。主要可以处理一些修改独立,询问离线的问题。

分治主要的用途是将询问降维,例如经典的数点问题。

主要想法是对操作序列进行分治,每次将前一半的修改操作对后一半中询问操作的贡献计算出来,然后递归左右两部分分别进行计算。

这种做法原生是不能支持删除操作的,除了时间倒流这个方法之外,xyz在论文中提到的一种用线段树的思想来实现删除操作的做法十分好。

这个做法的想法就是:一个操作所影响的时间肯定是一段区间(从被添加到被删除), 把整个操作序列看成一个线段树的结构,每个修改操作所影响的就是线段树上的一些节点,那么对于每个节点,将这个节点上的修改操作的贡献加到这个区间中所有询问上就好了。

相关例题:
陌上花开 (三维数点)
POI2011 Meteors


二进制分组

二进制分组是一种应对强制在线题目的方法。

它是一种对修改操作分块的方法。 二进制分组能处理的问题也要满足修改之间互相独立。

主要思想就是对于一些难以插入元素的结构(例如虚树、半平面交等) ,不能很好地将修改操作应用到数据结构上,那么就每隔一段时间进行重构。这个重构的时间就根据询问数目按照二进制分组进行(维护大小为1、2、4、8、16、32的数据结构, 如果出现了两个大小为x的结构,就把它们合并成一个大小为2x的块)

二进制分组可以用线段树结构进行维护,叶子节点就是大小为1的块,每次合并两个块的过程就可以看做线段树上左右孩子的合并。虽然这样做的空间复杂度增加了一个log, 但是可以支持区间查询。

二进制分组如果要删除的话,只能支持在O(1)个位置进行删除(例如在尾部删除或在头部删除)。以在序列尾部删除为例,具体做法和插入类似,就是如果删除了一个节点,那么就在它线段树节点到根路径上每个节点都打上一个懒标记,查询的时候如果遇到懒标记就递归到孩子节点去查询。每次合并一个块的时候,如果发现它左边的一个和它大小相同的块有懒标记的话,就重建这个块,这样就能保证线段树每层最多只有一个被打上懒标记的块,这样就能删除了。

相关例题:
思考熊

← HNOI2016 爆零记 NOI前的71天 →
 
comments powered by Disqus