APTX Blog

A Moe Blog Set By APTX

#C/C++#数据结构:树状数组/线段树/并查集/树链剖分

数据结构

树状数组,堆

线段树

  •  单点,区间
  • 动态开结点

并查集

  • 加了路径压缩之后不能随便撤销
  • 使用启发式合并复杂度是 O(n log n),按秩合并是 O(nα(n))。

平衡树

  • treap 比较好写
  • splay 比较难写, noip 也不会考这么高级的东西
  • 只能说 (开了 O2 的)set 秒杀一切

dfs 序与树链剖分

非传统方法

  • 点事件
  • 分块
  • cdq 分治

树状数组

具体思想就是要维护一个序列 a 的前缀和,我们可以维护一个辅助序列 s,使得 si = j2(ilowbit(i);i] aj,然后我们发现可以用
O(log n) 的时间维护 s

修改 + 查询的代码一共不超过五行。

线段树

一种基于分治的数据结构,能够解决可以先分治再合并的问题。

对于线段树的理解一定要注意,线段树的核心是可合并性:一旦这个问题具有可合并性,就可以使用线段树来做。

线段树可以维护比前缀和更多的信息,但是有更大的常数(4)树状数组(1/2)。

并查集

并查集能够快速实现集合的合并,并且查询两个元素是否位于同一个集合。最经典的应用是 kruskal 算法。

常见的优化有两个:路径压缩;按秩合并。两个都加上可以实现单次操作 O(α(n)) 的时间。

如果需要维护撤销操作,就不能用路径压缩,也不能用按秩合并,因为这两个操作都是不可逆的。这个时候只能够使用启发式合并,单次操作复杂度降为 O(log n)

平衡树

一种非常强的维护序列的数据结构,能够在 O(log n) 时间内完成很多区间操作,并且支持对区间形态的修改。经常使用的平衡树包括 splaytreap 等,动态树也是基于 splay 产生的。

NOIP 不会直接考察平衡树,而我们经常使用的是 STL 当中使用平衡树实现的容器——set, map  。

SET/MAP

STL 当中使用得最多的两种数据结构。

SET/MULTISET

  • 维护一个有序集合(multimap 可以支持集合当中有相同的元素)
  • 支持询问第 k 大,快速插入,删除
  • 可以重定义比较函数
  • 开了 O2 可以看作单次操作常数时间

MAP/MULTIMAP

  • 维护一些有序的 pair,每个 pair 有两个参数:键值和权值按照键值排序,同一个键值只能对应一个权值(multimap 当中每个键值可以对应不止一个权值)
  • 自动重载 [] 运算符

dfs

1 号点为根,对树进行一遍 dfs 遍历,在每个点进栈和出栈的时候将点加入到 dfs 序列当中,最终得到一个长度为 2n dfs 序列。

这个 dfs 序列有如下几个性质:

  • 长度为 2n,且每个元素恰好出现两次。
  • 一棵子树对应一个区间,区间的起点和终点恰好是这棵子树的根的两次出现的位置。如果 u v 的子树当中那么 u 对应的区间完全包含于 v 对应的区间。
  • w u v 的路径之上当且仅当在序列当中 u 的任意一次出现和 v 的任意一次出现所确定的区间当中点 w 出现一次。(树上莫队的基础)

树链剖分

每个点选择一个点数最多的儿子作为重儿子,这个点和重儿子之间的边称为重边,和其他儿子之间的边称为轻边。

将点重新标号,根为 1 号,之后优先标号重儿子,其他的儿子随意顺序。这样一条重链一定对应一个区间。

任意两点之间的路径一定不超过 O(log n) 条轻边。

非传统方法

非传统方法是指对于一些数据结构题,我们不使用真正意义上的高级数据结构例如线段树,平衡树等,而是使用一些算法和最基础的数据结构例如数组,链表等来解决。

点事件

  • 将一整个操作序列分成一个一个小事件(称为点事件),按照一定的顺序处理这些事件,不一定是原先的事件顺序。

扫描线

  • 一般和点事件一起使用
  • 考虑一个二维平面,有一条无限长的线从一个方向往另一个方向扫过,按照线扫到的顺序处理关键点


cdq 分治

  • 对操作序列进行分治

整体二分(省选难度)

  • 如果询问操作可以二分回答,而且题目允许离线,就可以使用整体二分。

以上By:北京大学图灵班 胡家琛

PPT以后放在我的Onedrive上

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注