简单数据结构

数据结构简单的可分为线性结构（主要是线性表）和非线性结构（主要是树和图）。

线性数据结构

线性结构是一个有序数据元素的集合。

常用的线性结构

线性表，栈，队列，双队列，串(一维数组)。

非线性数据结构

关于广义表、数组(高维)，是一种非线性的数据结构。

常见的非线性结构

二维数组，多维数组，广义表，树(二叉树等)，图。

 

序列维护（线段树&平衡树）

树

树是一种数据结构，它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

 

线段树

线段树的用处就是，对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是O(log²(n))。

线段树的原理就是将[1,n]分解成若干特定的子区间(数量不超过4*n),然后，将每个区间[L,R]都分解为少量特定的子区间，通过对这些少量子区间的修改或者统计，来实现快速对[L,R]的修改或者统计。

用线段树统计的东西，必须符合区间加法，否则，不可能通过分成的子区间来得到[L,R]的统计结果。

 

相关题目

做法

考虑我们维护了什么，有哪些是我们没有维护的（一般是一个左边、一个右边、一个跨过中线的东西）。

平衡树

平衡树(BT) 全称“平衡二叉搜索树”，指的是，任意节点的子树的高度差都小于等于1。常见的符合平衡树的有，B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。平衡树可以完成集合的一系列操作, 时间复杂度和空间复杂度相对于“2-3树”要低，在完成集合的一系列操作中始终保持平衡，为大型数据库的组织、索引提供了一条新的途径。

设“2-3 树”的每个结点存放一组与应用问题有关的数据, 且有一个关键字 (>0的整数) 作为标识。关键字的存放规则如下:对于结点X, 设左、中、右子树均不空, 则左子树任一结点的关键字小于中子树中任一结点的关键字;中子树中任一结点的关键字小于结点X的关键字;而X的关键字又小于右子树中任一结点的关键字, 称这样的“2-3树”为平衡树。

常见的类型

splay

treap

AVL Tree

Red Black Tree

Scape Goat Tree

Weight Balanced Leafy Tree（特殊结构）

 

二叉搜索树

性质

一个节点x左子树所有点的关键字都比x的关键字小，右子树所有点的关键字都比x的关键字大。

 

 

treap

“树堆”“Tree + Heap”

性质

每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质 。

复杂度

期望O( logn )        

 

设每个节点的关键字是key，随机权值是rand

如果v是u的左儿子，则key[v] < key[u]

如果v是u的右儿子，则key[v] > key[u]

如果v是u的子节点，则rand[u] > rand[v]

Treap维护权值的时候一般会把相同的权值放在同一个节点上 。

一个treap节点需要维护的信息

左右儿子

关键字

关键字出现次数

堆随机值

节点大小（即子树大小）

 

Treap的旋转

平衡二叉搜索树主要通过旋转来保持树的平衡，即保证复杂度。

旋转有单旋和双旋，treap只需要单旋。

 

 

Treap的插入

先给这个节点分配一个随机的堆权值 ，

然后把这个节点按照bst的规则插入到一个叶子上：

从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子；

然后通过旋转来调整，使得treap满足堆性质。

 

Treap的删除

和普通的BST删除一样：

如果删除值小于当前节点值，则递归至左儿子；大于则递归至右儿子 。

若当前节点数值的出现次数大于 1 ，则减一（通常将同一个权值缩掉），

若当前节点数值的出现次数等于 1 :

若当前节点没有左儿子与右儿子，则直接删除该节点（置 0）；

若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点；

若当前节点有左儿子与右儿子，则不断旋转当前节点，并走到当前节点新的对应位置，直到没有左儿子或右儿子为止。

 

Treap的查询

递归到叶子节点，一路维护信息即可。

 

Treap的分裂合并

用于维护序列，支持将Treap按前k个位置分裂为两棵树 。

分裂的时候维护两棵树，分别代表左边和右边的部分 。

复杂度

因为保证了堆性质，所以复杂度期望下是正确的 。

Treap只需要保证堆性质复杂度就期望正确。

 

splay

“伸展树”“自适应查找树”

每次对一个节点进行操作的时候通过一种方法把这个点旋转至根 。

splay的分裂

用于维护序列，支持将splay按前k个位置分裂为两棵树 。

直接把第k个位置splay到根，然后断开根的右儿子。

splay的合并

将右边部分的第一个位置splay到根，然后让其左儿子为左边部分

复杂度

可以证明复杂度为均摊O(mlogn)

可能存在一次操作复杂度特别高 。

 

splay具有“自适应性” 。

大概就是说splay会根据操作的特点调整树结构，使得操作尽可能高效。

可以去了解一下splay的动态最优性猜想，是个著名的open problem

 

缺点

可以通过势能分析证明splay的复杂度是均摊O( logn )的，也就是说splay在很多次操作中可能会有一次O( n )复杂度的操作 。

而且这样的操作也很好构造 。

所以splay不适合做一些需要撤销操作/可持久化的题目（虽然可以通过随机旋转什么的方法来规避，但还是感觉很吃力）

自身常数比较大 。

优点

splay用来维护序列还是比较好写的，用来维护名次树感觉不好写 。

由于自适应性，splay不需要特殊的技巧就可以高效启发式合并，还可以高效实现LCT（STT）等动态树

 

WBLT（Weight Balanced Leafy Tree）

这个Weight Balanced是指的Balanced by Boundary，也就是BB[α]

和clj那个定义不一样

大概可以理解为通过旋转而不是重构来满足替罪羊树那个平衡关系 。

也就是说替罪羊树是Weight Balanced Tree的一种。

线段树就是一种Leafy Tree，也就是说把信息都存在叶子上，非叶节点都是存储了信息的合并的虚点 。

优点

目前最好写的平衡树，可持久化效率很高 。

缺点

非可持久化的情况下要两倍空间，拿来写LCT（STT）很吃力 。

 

替罪羊树

定义常数平衡因子α

如果一个点的某个儿子，占到了子树大小的α，则认为不平衡，重构这个子树 。

复杂度也是带均摊的，均摊O(logn)，最坏单次操作O(n)。

解决问题

给你一个序列，每次查询区间的分治信息，可能有单点修改或者区间修改 。

给你一棵树，每次查询路径的分治信息，可能有单点修改或者路径修改。

注意

这里维护的信息是可快速合并的信息，具体怎么定义快速合并比较复杂。

建议考虑线段树合并区间答案的时候，考虑如果答案都在左区间，都在右区间的情况，然后剩下的情况就是这次合并需要额外维护的 。

有可能考虑合并需要额外维护的信息时需要额外在线段树节点上维护新的信息。

 

常见的打标记的操作

区间加

区间乘

区间染色（区间修改为一个数）

区间翻转

区间xor

区间值修改

维护出区间中每个极长的 “X” 段的长度，可以发现这个存在一个自然根号：

假设区间长度为size，则最多只有O( sqrt( size ) )种极长 “X” 段的长度 ，

每次对区间进行值修改的时候，即对这个长度为O( sqrt( size ) )的多项式进行求值，暴力计算即可，求值复杂度为O( sqrt( size ) )，即可以O( sqrt( size ) )的时间将一个节点值进行修改，同时维护信息 。

区间符号修改

每次对区间符号进行修改的时候，区间的信息只会变成区间和或者区间乘积，所以我们每个节点要维护区间和和区间乘积 。

符号修改之后，这个节点的极长 “X” 段只会有O( 1 )种了 。

符号进行修改可能影响一些节点的极长 “X” 段，考虑如何维护这个。

对一个节点，我们可以归并两个儿子的极长 “X” 段，来维护出这个节点的极长 “X” 段 。

对一个大小为size的节点进行归并，代价是O( sqrt( size ) )的 。

注意需要特判左儿子的最右极长 “X” 段是否和右儿子的最左极长 “X” 段进行合并 。

区间信息合并

合并区间信息的时候，只需要把左右儿子信息加起来，同时特判O(1)个位置即可

这O(1)个位置就是左儿子的最右部分和右儿子的最左部分

可处理：

标记对标记的影响

标记对信息的影响

信息和信息的合并

复杂性

T( n ) = T( n / 2 ) + O( sqrtn )

sqrt( n ) + sqrt( n / 2 ) + sqrt( n / 4 ) + … + sqrt( 1 ) = O( sqrt(n) )

空间：

T( n ) = 2T( n / 2 ) + O( sqrtn )

sqrt( n ) + 2sqrt( n / 2 ) + 4sqrt( n / 4 ) + … + nsqrt( 1 ) = O( n )

总时间复杂度O( msqrtn )，空间复杂度O( n )

 

均摊复杂度问题

序列染色段数均摊

特点

修改有区间染色操作

用平衡树维护区间的颜色连续段 。

区间染色每次最多只会增加O( 1 )个连续颜色段，用平衡树维护所有连续段即可 。

均摊的颜色段插入删除次数O( n + m )

应用

区间染色，维护区间的复杂信息

区间排序

“ODT”类问题

注意

这里这个颜色段数均摊是有2~3的常数，常数很大。

 

“重量”平衡树

平衡树旋转/重构的节点的size的和是O( nlogn )

这样可以在旋转的时候暴力重构一些信息

应用

动态标号问题

序列

1.在x后面插入y

2.查询x和y在序列上的先后问题，这个要求O(1)

可以线性解决，但是由于其他部分一般带log所以OI中一般采用O( nlogn )的解决方法 。

 

套用动态标号法可以得到平衡树维护后缀数组的算法，被称为“后缀平衡树” 。

可以实现树套树的外层树插入。

 

Old Driver Tree

在有类区间染色操作，以及保证数据随机的情况下 。

可以用一个平衡树维护颜色连续段的暴力来解决 。

复杂度期望O( (n+m)loglogn )，可以做到O( n + m )，但是not practical

在线 

O( (n+m)loglogn )（直接做），O( (n+m)logloglogn )（使用exponential tree），

O( n + m )（使用O( logn/logw )的动态前驱数据结构）

离线

O( n + m )，压位即可

可以证明复杂度是期望O( (n+m)logn )的

假设有k种操作，其中一种是区间染色，定义势能为颜色段个数

每次操作的时候有两种可能性：

1.以O( x )的代价消除O( x )势能，势能+2，概率1/k

2.以O( x )的代价啥都没做，势能+2，概率1-1/k

势能的均摊是O( n + m )

于是这部分总的代价是O( (n+m)k )

所以复杂度瓶颈在于平衡树而不是暴力的均摊部分

应用

各种题都能用，基本上不会被卡

因为大部分出题人都觉得序列维护的那种数据结构题只需要随机数据就足够强了…

不过要注意，别被没有区间染色的部分给卡了…

可以水掉各种题

 

补：

gcd（最大公约数）

gcd(a,b)=gcd(a-b,b)

题目

询问区间gcd

gcd(a[l],a[l+1],……a[r])=gcd(a[l],a[l+1]-a[l],……a[r])

                                     =gcd(a[l],a[l+1]-a[l],a[l+2]-a[l+1],……a[r]-a[r-1]

                                    =gcd(a[l],b[l+1],……b[r]

树上倍增

用于求LCA（最近公共祖先）。

倍增的思想是二进制。

首先开一个n×logn的数组，比如fa[n][logn],其中fa[i][j]表示i节点的第2^j个父亲是谁。

然后，我们会发现一个性质：

fa[i][j]=fa[fa[i][j-1]][j-1]

用文字叙述为：i的第2^j个父亲 是i的第2^(j-1)个父亲的第2^(j-1)个父亲。

这样，本来我们求i的第k个父亲的复杂度是O(k)，现在复杂度变成了O(logk)。

树状数组

类似于线段树，用于区间查询、区间求和。

顾名思义，树状数组就是用数组来模拟树形结构。那么衍生出一个问题，为什么不直接建树？答案是没必要，因为树状数组能处理的问题就没必要建树。和Trie树的构造方式有类似之处。

树状数组可以解决大部分基于区间上的更新以及求和问题。

树状数组可以解决的问题都可以用线段树解决，这两者的区别在于树状数组的系数要少很多，就比如字符串模拟大数可以解决大数问题，也可以解决1+1的问题，但没人会在1+1的问题上用大数模拟。

树状数组的修改和查询的复杂度都是O(logn)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。

缺点是遇到复杂的区间问题还是不能解决，功能还是有限。

求LCP（最长公共前缀）

前置知识

maxsuf（最大后缀）

maxpre（最大前缀）

方法

二分加哈希

左边的哈希值一样，就在右边继续求哈希，

左边的哈希值不一样，就在左边继续求哈希，

直到求出LCP。

离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

用法

有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

用途

缩小值域。

set/map

分别是集合/映射

内部使用红黑树（一种平衡树）实现。

同样的当set<>和map<,>中的第一个参数是自定义类型的时候

需要重新定义小于号。

复杂度基本上是O(log(当前大小))

map相当于是一个下标可以是任何数值的数组，如果访问时没有赋值就会返回零。