APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年10月3日 1297点热度 0人点赞 0条评论

数据结构

树状数组,堆

线段树

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

并查集

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

平衡树

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

dfs 序与树链剖分

非传统方法

  • 点事件
  • 分块
  • cdq 分治

树状数组

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

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

线段树

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

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

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

并查集

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

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

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

平衡树

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

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ DFS OI 并查集 数据结构 树 树状数组 算法
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
WPscan扫描Wordpress漏洞的工具使用教程 #笔记#进制转换 二次元头像(老婆)生成器 HDU 1806 Frequent values(区间RMQ问题)题解 Jawbone Jambox Mini蓝牙音响上车指南与刷机 waifu2x:图片放大效果
标签聚合
OI ST 洛谷 C++ 动漫 C/C++ 日常 HTML
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang