数据结构笔记

· · 个人记录

基本数据结构

1. 前缀和

前缀和用于解决一维静态问题，可以查询前缀半群信息或区间群信息。

实现过程：从前往后记录前缀的信息，查询前缀时直接使用，查询区间时用两个端点的信息相减。

例题：略。

2. 树状数组

用于解决一维动态问题：单点修改，查询区间群信息。

实现过程：lowbit(i)=i\text{ and }-i，i 节点记录的是 i-lowbit(i)+1\sim i 的信息。

修改时 p\rightarrow p+lowbit(p)\rightarrow p+lowbit(p)+lowbit(p+lowbit(p))\rightarrow \dots。

查询时 p\rightarrow p-lowbit(p)\rightarrow \dots。

例题：树状数组 1。

3. 线段树

用于解决一维动态问题：区间修改，查询区间群信息。

实现过程：每个区间从 mid 分开变成两个子节点区间，每次修改和操作就最多只有 O(\log n) 个区间了。

例题：线段树 1。

不那么简单的基本数据结构

1. 树套树

可以用于解决 n 维动态问题，单点修改，查询正交（指与坐标轴平行的范围）半群信息。

第一维中的线段树每一个节点都有一棵线段树，就可以完成高维问题。

例题：暂无。

2. K-D Tree

后面会提到。

3. 可持久化

解决询问强制在线的静态问题。

可以认为是记录下了扫描线中每个过程都记录了下来。

实现过程：每次对于一个新版本修改的节点，都新建一个节点表示，但是仍然连接之前的节点，这样每次修改至多 O(\log n) 个新建节点。

例题：可持久化数组。

常用套路

1. 差分

用于减少询问维数且常数影响极小。

几乎无代价降低问题难度。

实现过程与前缀和相反，略。

例题：略。

2. 扫描线

可以将静态的高维问题转化为动态的低维问题。

实现过程：按顺序扫描其中一维，将每一个有变化的位置全都拿出并用数据结构维护每次变化。

例题：扫描线。

3. 莫队

普通的一维扫描线可以认为是若干前缀按照右端点排序后依次处理问题。

莫队的范围将前缀改为区间，也可以认为是一种扫描线。

3.1. 序列区间莫队

处理双自由度问题，二维扫描线，复杂度 O(n\sqrt m)。

实现过程：最初有两个端点 l,r，对 l 分块后按 l 所在块排序（第二关键字为 r），这样每次 l 的移动都不超过 \sqrt n 个，r 总共移动 \sqrt n 次，每次最多为 n。

例题：小 B 的询问、小 Z 的袜子。

3.2. 双前缀莫队

两个序列，查询与两个序列的前缀有关，如果信息支持差分则可以与双前缀莫队转换。复杂度 O(n\sqrt m)。

实现过程：与序列区间莫队类似。

例题：暂无。

3.3. 带修莫队

把时间看做一维，即三维莫队，复杂度 O(nm^{\frac 23})。

实现过程：对 $l$ 的块，$r$ 的块以及时间排序，其它同序列区间莫队。 例题：[数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)。 #### 3.4. 矩形莫队 询问为矩形，四维莫队。 例题：暂无。 #### 3.5. 子树莫队 子树不删除莫队等价于树上的启发式合并，复杂度 $O(n\log n)$。 例题：暂无。 #### 3.6. 树上路径莫队 即树上莫队，在欧拉序上进行，复杂度 $O(n\sqrt m)$。 实现过程：每次对于一条路径分别计算两个端点到 LCA 的值。 例题：暂无。 ## 动态问题转为静态问题 将时间轴视作一个维度，维护每个元素各时刻的值，然后分治或从另一维扫描线等。 ### 1. 区间 mex 用扫描线扫右端点，用权值线段树记录每个点最后出现的位置。 查询时在线段树上直接二分到最小的最后出现位置在 $l$ 之前的值即为答案。 ### 2. 线段树历史版本和 历史版本和是指每一次修改之后这个节点位置的值之和。 线段树节点维护以下信息： - $s$：区间和 - $t$：加法标记 - $hs$：区间历史和 - $ht$：区间加法标记和 - $tg$：这个节点与子节点的最后一次更新时刻的差 pushdown 时考虑 $hs$ 和 $ht$ 的变化，把每一次操作之后的值作为一个宽为 $1$，长为当前值的矩形并放在一起。 容易发现，$hs$ 比之前增加的那一部分的宽为 $tg$，将其分为上下两部分，下面的部分是一个长为 $s_s$ 的长方形，上面每个数总共增加了 $ht$，所以 $hs_s\gets hs_s+s_s\cdot tg+ht\cdot len_s$。 类似的，有 $ht_s\gets ht_s+t_s\cdot tg+ht$。 其它直接维护即可。 ### 3. 线段树历史最值 类似上面，$ht_s\gets \max(ht_s,t_s+ht)$，$hmx_s\gets \max(hmx_s,mx_s+hmx)$，其它直接维护。 ## 例题 ### 1. [One Occurrence](https://www.luogu.com.cn/problem/CF1000F)（改） 给定长为 $n$ 的序列，$m$ 次查询，询问区间中有多少值只出现过一次。 做法一：直接莫队，略。 做法二：考虑记录每个数 $a_i$ 上一次出现的下标 $pre_i$ 和下一次出现的下标 $nxt_i$，将询问区间看作二维平面上的一个点 $(l, r)$。只有当 $pre_i < l_j \le i$ 且 $i \le r_j < nxt_i$ 时 $i$ 才会对询问 $j$ 产生 $1$ 的贡献，这样就变为了一个矩形加，单点查值的问题。 ### 2. [作业](https://www.luogu.com.cn/problem/P4396) 给定长为 $n$ 的序列，求 $[l, r]$ 区间内值在 $[x, y]$ 中不同值的个数。 做法一：莫队加值域分块。 做法二：运用升维的技巧，记录 $a_i$ 上一次出现的位置 $pre_i$，题目变为求 $i\in[l, r], a_i\in[x, y], pre_i < l$ 的点数，这是一个三维的问题，直接三维数点即可。 ### 3. BZOJ 3489 A simple rmq problem 给出一个长度为 $n$ 的序列，给出 $m$ 个询问，每次问 $[l, r]$ 中只出现过 $1$ 次的数的最大值，或报告无解。强制在线，空间最多 $O(n \log n)$。 和 One Occurrence 一样的套路，记下来 $pre_i$ 和 $nxt_i$，将每个询 问看作二维平面上的一个点 $(l, r)$。每次操作变为对 $pre_i < l_j \le i$ 且 $i \le r_j < nxt_i$ 的一个矩形取 $\max$，然后单点查询。 然而我们发现取 $\max$ 后不好消除某个值的影响，因此并不能直接用扫描线做。我们可以将这个问题转换为扫描线 $+$ 区间插入 $+$ 区间删除 $+$ 单点取 $\max$，这个可以用线段树标记永久化做。 考虑到这题强制在线，这一类扫描线可做的题强制在线后一般都是用可持久化解决。直接将每个节点上的堆可持久化的话空间 $O(n \log^2 n)$，不能通过本题。但你发现访问历史节点 $max$ 只需要维护一个普通的堆，将历史的 $max$ 值都记下来就行了，空间 $O(n \log n)$，可以通过。 如果本题不强制在线有什么简单的做法呢？可以将矩形按值排序，遍历每个矩形，更新矩形内部答案，删点即可。 ### 4. [套娃](https://www.luogu.com.cn/problem/P9970) 考虑如何求区间 $\text{mex}$, 可以直接扫描线从左到右扫右端点，用值域线段树维护每个颜色最后的出现位置，然后在线段树上二分即可。 我们观察一下做扫描线时每个左端点到当前右端点的区间的 $\text{mex}$ 数组的变化，发现当加入的数为 $x$ 时，会将原来 $\text{mex}$ 为 $x$ 的那个连续段分裂，并在最右端加入一个新连续段。 可以发现，每次指针右移一定会让连续段个数增加或不变，且连续段个数不变的次数最多为 $O(n)$ 次，而连续段数的上限为 $n$，所以总共只会有 $O(n)$ 个本质不同的连续段。 简而言之，就是将 $[l, r]$ 的 $\text{mex}$ 画到二维平面上，则会由 $O(n)$ 个矩形构成。 接下来就好做了。对于每个矩形，记左端点在 $[l1, r1]$ 内，右端点在 $[l2, r2]$ 内，那能产生影响的区间就是 $[l2-r1 + 1, r2-l1 + 1]$，扫一遍就行。 （这里本来还有一道例题，但是因为是联考所以就不放了） ## K-D Tree 树套树实际上是一种 DAG 的结构，并不能下推懒标记。这时 k-D Tree 就可以实现许多树套树做不到的操作。 以二维 2-D Tree 为例，考虑这样一种分治结构： - 初始只有一个根节点； - 对于一个点集，先按照 $x$ 坐标排序，接着按 $x$ 的中位数将点集分成两半，每部分对应一个儿子节点； - 接着对于每一部分按照 $y$ 坐标排序分成两部分，每部分又对应一个子节点； - 一直循环这两步直到点集只剩一个点。 k-D Tree 的复杂度分析类似于线段树。 以二维为例，只需要统计操作矩形的每一条边的递归次数，$\times 4$ 就是矩形操作的复杂度。 每 $2$ 次划分会将点集分为 $4$ 部分，而一条平行于坐标轴的边只会递归进其中两部分，因此时间复杂度 $T(n)=2T(\frac n4)+O(1)$。 由主定理得到 $T(n)=O(\sqrt n)

k-D Tree 只有操作范围均为 k 维正交范围时复杂度正确。其它情况（如圆形询问或半平面）在随机数据下也很快，但可以被卡。

有时做一些剪枝可以大幅减小 k-D Tree 的常数，例如求矩形最大值时记录当前 ans=k，小于就不递归下去。

还可以乱搞查询上面说的奇怪的范围。

k-D Tree 例题

1. 区间逆序对

题意：m 次查询，求 a_l,a_{l+1},\dots,a_r 逆序对数，1\le n,m\le 5\times 10^4。

莫队加其它数据结构可以做到 O(n\sqrt m\log n)。

用扫描线扫询问右端点，数据结构维护左端点的答案。

右端点每次加入一个值相当于 i<r 且 a_i\ge a_r 的元素都 +1。

用 k-D Tree 维护答案，复杂度 O(n\sqrt n+m)。

2. 方方方的数据结构

对时间轴分块，对序列建线段树维护可以做到 O(n\sqrt m\log n)。

维护一个二维平面，两维是时间和下标，处理出每个操作影响的时间范围，则每个操作相当于修改序列 [l,r] 时间 [x,y] 的矩形。

直接做 k-D Tree 复杂度是 O(n\sqrt n^2)=O(n^2) 的，但可以只处理被询问的点，复杂度 O(n\sqrt n)。

3. 异或

给定一个长为 n 的序列 a 和 01 序列 b，每次操作给出 x 并将所有 a_i=x 的位置 b_i\gets b_i\oplus 1，每次操作后求 b 连续的 1 的段数。1\le n,m\le 5\times 10^4。

在两端放两个 0 之后问题相当于是 b_i\oplus b_{i+1}=1 的数量的一半。

维护这个东西，我们在平面中插入点 (a_i,a_{i+1})，每次修改就是将 a_i=x 和 a_{i+1}=x 两条直线全都 \oplus 1，以及全局查询，可以用 k-D Tree 维护。

4. 翻转

一个长为 4^n 的数组 a，有几种操作：

  1. \forall i\in[l,r],a_i\gets \lfloor\sqrt {a_i}\rfloor
  2. \forall i\in[l,r],a_i\gets a_i+v
  3. 求 \sum\limits_{i=l}^r a_i
  4. \forall i<rev(i),swap(a_i,a_{rev(i)})$，其中 $rev(i)$ 表示 $i$ 二进制逆序（前后翻转）的结果，如 $n=2$ 是 $rev(7)=14
1\le n\le 9,1\le m\le 3\times 10^4

把 (i,rev(i)) 放到平面上用 k-D Tree 维护，操作 4 就相当于交换两个坐标轴。

接下来考虑怎么维护操作 1。对每个区间记录 max 和 min，若某个区间 max-min=\sqrt{max}-\sqrt{min}，则相当于每个数都减去相同的数，给区间打减法标记即可，否则递归到两个子区间分别处理。

复杂度证明可以考虑势能分析：每次区间加会递归到 \sqrt n 个节点，总共增加的势能是 \sqrt n\cdot\log V，而每次递归到一个节点会花费 O(1) 减小 1 势能。

弱化版：uoj 228. 基础数据结构练习题

5. rrusq

平面上大小为 n 的点集 a，点有点权，有 m 个矩形 b_1\sim b_m 和 q 次查询，每次查询 b_l\sim b_r 的矩形所覆盖的点权之和。1\le n,m\le 10^5,1\le q\le 10^6。

先考虑把问题弱化到序列上怎么做。

扫描线扫右端点 r，对于序列中每个元素维护覆盖它的编号最大的区间，设为 x，那么 x\ge l 说明它被 [l,r] 间的区间的并覆盖。于是问题变为区间染色求颜色 \ge l 的点权之和，可以 ODT。

回到原问题，用 k-D Tree 处理，但是考虑如何使用类似颜色均摊段的方法维护编号。

可以在 update 时每个 k-D Tree 节点都打标记：

这样每个标记只会被回收 1 次，复杂度正确。