各种常见的树和其算法

线段树

概念

线段树是一种二叉搜索树,满足二叉树每个节点小于等于2,每个节点最多有俩个子树.何为搜索

要知道,线段树的每个节点存储了一个区间,也可以理解成一个线段,而搜索,就是在这些线段上进行搜索操作

• 解决的问题

线段树的适用范围很广,可以在线维护修改以及查询区间上的最值,求和,更可以扩充到二维线段树(矩阵树)和三维线段树(空间树).对于一堆线段来说,每次更新以及查询的时间复杂度为O(logN)

• 线段树和其他RMQ算法的区别

常用的解决RMQ问题有ST算法,二者处理时间都是O(NLogN),而且ST算法单次查询操作是O(1),看起来比线段树好多了,但二者的区别在于线段树支持在线更新,而ST算法不支持在线操作

　　这里也存在一个误区，刚学线段树的时候就以为线段树和树状数组差不多，用来处理RMQ问题和求和问题，但其实线段树的功能远远不止这些，我们要熟练的理解线段这个概念才能更加深层次的理解线段树。

基本内容

现在请各位不要带着线段树只是为了解决区间问题的数据结构，事实上，是线段树多用于解决区间问题，并不是线段树只能解决区间问题，首先，我们得先明白几件事情。

　　每个结点存什么，结点下标是什么，如何建树。

　　下面我以一个简单的区间最大值来阐述上面的三个概念。

对于A[1:6]={1,8,6,4,3,5}来说,红色代表每个节点存储的区间,蓝色代表节点的值

可以发现,每个叶子节点的值,就是数组的值,每个非叶子节点的度都为2,且左右俩个孩子分别存储父亲的一半空间.每个父亲节点存储的值也就是俩个孩子存储的最大值

上面的每条结论应该都容易看出来。那么结点到底是如何存储区间的呢，以及如何快速找到非叶子结点的孩子以及非根节点的父亲呢，这里也就是理解线段树的重点以及难点所在，如同树状数组你理解了lowbit就能很快理解树状数组一样，线段树你只要理解了结点与结点之间的关系便能很快理解线段树的基本知识。

　对于一个区间[l,r]来说，最重要的数据当然就是区间的左右端点l和r，但是大部分的情况我们并不会去存储这两个数值，而是通过递归的传参方式进行传递。这种方式用指针好实现，定义两个左右子树递归即可，但是指针表示过于繁琐，而且不方便各种操作，大部分的线段树都是使用数组进行表示，那这里怎么快速使用下标找到左右子树呢。

对于上述线段树，我们增加绿色数字为每个结点的下标

则每个结点下标如上所示，这里你可能会问，为什么最下一排的下标直接从9跳到了12，道理也很简单，中间其实是有两个空间的呀！！虽然没有使用，但是他已经开了两个空间，这也是为什么无优化的线段树建树需要22k（2k-1 < n < 2k)空间，一般会开到4n的空间防止RE。

　　仔细观察每个父亲和孩子下标的关系，有发现什么联系吗？不难发现，每个左子树的下标都是偶数，右子树的下标都是奇数且为左子树下标+1，而且不难发现以下规律

　具体证明也很简单，把线段树看成一个完全二叉树（空结点也当作使用）对于任意一个结点k来说，它所在此二叉树的log2（k） 层，则此层共有2log2(k)个结点，同样对于k的左子树那层来说有2log2(k)+1个结点，则结点k和左子树间隔了22log2(k)-k + 2(k-2log2(k))个结点，然后这就很简单就得到k+22log2(k)-k + 2(k-2log2(k)) = 2*k的关系了吧，右子树也就等于左子树结点+1。

　　是不是觉得其实很简单，而且因为左子树都是偶数，所以我们常用位运算来寻找左右子树

• k<<1（结点k的左子树下标）
• k<<1|1（结点k的右子树下标）

　整理一下思绪，现在已经明白了数组如何存在线段树，结点间的关系，以及使用递归的方式建立线段树

作用

线段树的维护是用小区间更新大区间,线段树是平衡二叉树,所以时间复杂度总是log级别的

他能解决的问题需要满足区间加法,才能把大问题分成子问题解决

满足的

• 区间求和
• 区间最大最小值

不满足的

• 区间的众数
• 区间的最长连续问题
• 最长不下降问题

基本操作

建树

写代码时,用位运算效率更高

fa为父节点的索引

• l = fa*2 （左子树下标为父亲下标的两倍）
• r = fa*2+1（右子树下标为父亲下标的两倍+1）

线段树数组一般需要开到4n才能确保不会越界访问

建树的时候要先从叶子节点开始

父节点为子节点的和

单节点修改

修改数列中下标为i的数据,从根节点向下深搜

如果当前节点的左儿子的区间[L,R]包含了i,也就是L<=i<=R

就访问左儿子,否则访问右儿子

直到L=R 也就是搜到了只包含这个数据的节点,就可以修改它,不要忘了将包含次数据的大区间值更新

仅有单点修改的区间查询,不需要处理lazy标记

查询区间

步骤

如果要查询的区间完全覆盖当前区间,直接返回当前区间的值

如果查询区间和左儿子有交集,搜索左儿子

如果查询区间和右儿子有交集搜索右儿子

最后合并俩边查询的数据

区间修改

如果要修改的区间完全覆盖当前区间,直接更新这个区间,打上lazy标记,如果没有完全覆盖,且当前区间有lazy标记,先下传lazy标记到子区间,再清除当前区间的lazy标记

如果修改区间和左儿子有交集,搜索左儿子,如果和右儿子有交集,搜索右儿子,最后将当前区间的值更新

1. 覆盖lazy,2下传更新

区间修改后的区间查询是这样的

区间修改后的区间查询

如果要查询的区间完全覆盖当前区间,直接返回当前区间的值,如果没有被完全包含,下传lazy标记

如果查询区间和左儿子有交集,搜索左儿子

如果查询区间和右儿子有交集,搜索右儿子

最后合并俩遍查询的数据

比如524这几个全部+1

并查集

并查集是一种树形的数据结构,用于处理一些,不想交集合的合并与查询问题

比如有n个元素,分数不同的n个集合,俩种操作

1. 给出俩个元素的关系,合并俩个集合
2. 查询俩个元素是否存在关系

构建并查集

并查集主要包含以下几种基本操作：

init(s)：建立一个新的并查集，其中包含s个单元素集合
union(x, y)：把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并
find(x)：找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了

一个集合构建一棵树,人选一个元素作为该集合的根节点

建立pre数组记录每个元素的父节点

pre[当前节点]=父节点

根节点的父节点=自己本身

并查集的操作分为俩类,并和查

操作

给出关系后,如何进行合并?

将一个集合的树变为另一个集合的字数(将一个集合的根节点的父节点,改为另一个集合的根节点)

pre[B的根节点]=A的根节点,就可以将俩棵树合并为一棵树

普通查询

从该元素访问父节点(一般是递归查找)知道一步步访问到根节点,再对俩个元素的根节点进行对比判断

按秩合并

按秩合并是指总是将更小的树连接至更大的树上。因为影响执行效率的是树的秩（深度），更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。当两棵秩同为r的树联合时，它们的秩r+1

路径压缩算法

在查询操作时,最终目的是找到这个元素所在的这棵树的根节点,那么她和其他元素是如何联系的,对我们来说就没有意义了

在每次查询的时候,对被查询元素到根节点沿途经过的节点顺便把经过节点的父节点都改为更节点

这样的结构能让数据在O(1)的时间复杂度完成查询

最小生成树

36定义前导

无向图:没有方向的图称之为无向图,主要是没有方向的区别

连通图无向图中,任意俩个顶点都有路径想通,则称为连通图

树:如果一个连通图不存在回路,也就是不存在环,就是一个树

生成树

它是一个连通图的连通子图

它含有连通图中的全部顶点,有且仅有足以构成一棵树的n-1条边(如果生成树中再加一条边,必定构成环)

对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

最小生成树连通图知道所有生成树中,边权和代价最小的生成树,就是最小生成树

算法

比如要在n个城市之间铺设光缆,主要目的是,使n个城市的任意俩个之间都可以通信,但光缆的铺设费用很高,且各个城市之间铺设光缆的费用不同

因此一个目标是,使铺设光缆的总费用最低

最小生成树有俩种经典算法prim,kruskal

prim算法

从已知的某个点开始向外扩散,寻找最小的邻边,挨个将顶点假如集合,已加入集合的不能再加入(否则会成环)知道所有顶点加入集合,构成最小生成树

比如从1开始,右上角是数组

kruskal算法

克鲁斯卡尔算法从整个连通图最小的一条边开始贪心,边能最小就要最小的(只要不成环) 不断合并最后构成最小生成树,是否构成环,以及合并是利用并查集来辅助操作的

kruskal算法是把所有的路径长度排序,最后再去合并集合,如果在当前集合中的就不再添加进集合中了

最小生成树不一定是唯一的,但是他们的边权之和都是相等的

如何选择俩种算法

kruskal是对整个图的边进行贪心,只需要一次排序,在边很小的情况下只需要一次排序就能求出最小生成树,但在边很多的情况下,复杂度就会变高,相比之下prim算法比较稳定

所以

kruskal:稀疏图

prim:稠密图

最短路径算法

最短路径有三大算法

• dijkstra:求无负权变的单源最短路,基于顶点求单源最短路n个顶点,m条边算法时间复杂度为O(n^2),
• bellman-ford:可以求带负权变的图的单元最短路,并且可以判断图是否存在负环,存在傅欢的图求最短路是没有意义的,因为它的路径权会无限缩小
• floyd:可以求带复权边,但不带负环的多源最短路

单源最短路:从某一点触发,到其他所有点的最短路径

dijkstra

迪杰斯特拉

利用贪心策略实现,与prim算法异曲同工

设一个集合,保存已经找到的最短路径点

1. 设一个集合,保存已经找到最短路径的顶点,先将起点加入集合
2. 将起点到所有点的距离存在dis数组里,不能直接达到的点(起点与该点无边)存为无穷大
3. 在dis数组中找一个最小值,当前值一定是起点到该点的最短路径,将该点加入集合
4. 遍历其他点,如果他们通过这个最短的点作为中转,比源点直接到达,就替换这些顶点到源点的dis值(松弛操作)
5. 又从dis中找到最小值,重复上面的操作,直至T集合包含的所有顶点

因为贪心算法,只是贪心眼前最小值,如果后续的数据中有负权就考虑不到

bellman-ford

贝尔曼福特算法

对边进行松弛操作 一般采用邻接表或是前向星存储

第i条边

e[i].x:边的起点

e[i].y:边的终点

e[i].z:边的权值

步骤

1. 将除起点外所有的顶点到起点的距离数组dis初始化为无穷大
2. 迭代:便利图中每一条边对每条边的俩个顶点进行松弛操作,直到不能再松弛
3. 判断负环:如果迭代超过n-1次后,还能继续松弛,则存在负环

时间复杂度为O(n*m)

优化:若在某一次迭代k后,没有点进行松弛操作,则代表已经找出了所有的最短路,迭代结束,直接跳出循环

floyd

弗洛伊德算法

本质上是动态规划算法

任意节点到i->j的最短路径只有俩种可能

• 直接i到j
• 从i经过若干节点k到j

f(k,i,j)表示i节点可以通过1-k顶点的最短路径

k=0 原图f(0,ij)

f(k,i,j)的俩个状态转移方程为

f(k-1,i,j)

f(k-1,i,k)+f(k-1,k,j) i到j经过k点

他的核心思想是

如果某个节点位于从起点到终点的最短路径上,那么起点到终点的最短路径为=起点到该节点的位置+该节点到终点的最短路径

同理

如果某个节点不在从七点到终点的最短路径上,起点到终点的路径>起点到该节点的路径+该节点到终点的最短路径

内部维护了俩个表

D列表为距离列表(Distance Table),S为次序列表(Squence Table)

D列表

存储了任意俩个节点间的最短距离

首先填充D列表,对于不存在的直接访问的设置为无穷

用终点填充次序列表

进行第一次迭代,此时k=0,本次迭代的本质就是判断图中任意俩个节点的最短距离,是否更有可能通过节点0

不断比较从起点到节点0的距离+从节点0到终点的距离只和,是否小于,当前直接到终点的距离

等进行了五次迭代就获得了他们任意俩点之间的最短距离,和最短距离路径

RMQ和ST

RMQ算法全称为Range Minimum/Maximum Query即区间最值(最小值或者最大值)查询

其实这个问题至少有三种解法

1. 朴素算法:每次都遍历一遍,找到最值,时间复杂度O(n)
2. 线段树:维护每个区间的最小值,时间复杂度:建树o(n),查询O(log2N)
3. ST算法:实质就是动态规划,需要推出转移方程,时间复杂度:建表(Onlog2n)查询O(1)

一般来说ST算法效率是最高的,对查询次数不是特别多的RMQ来说线段树也是可以的

ST算法

sparse Table 稀疏表

st算法的本质就是动态规划,我们需要用一个二维的dp数组来保存区间最值

由于4[log10]=3 建表结束

查询公式为

main(F[l,k],F[r-2<<k+1,k])

AVL树

二叉(BST)树是n个节点构成,所以对于某些情况,二叉树会退化成一个有n个节点的线性链表

AVL是自平衡二叉查找树.通过左右旋转来实现的

平衡树插入和删除的时候,会通过旋转将高度保持在LogN,其中俩款具有代表性的平衡树分别为AVL树(高度平衡树,具备二叉树的全部特性,而且左右子树高度不超过1)和红黑树

局限性

AVL树适合插入与删除次数比较少,但查找多的情况

由于维护这种高度平衡锁付出的代价比从中获得的收益还大,故而实际应用的不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入和删除不频繁,只是对查找要求比较高,那么AVL还是较优于红黑树