Day 03

· · 算法·理论

树状数组

树状数组基本上是线段树的弱化但又快又好写版本。 维护一个比线段树更快的数据结构，支持对序列：

我们魔改一下线段树的结构，删掉每个结点的右儿子。

得到的这个结构仍然保留树的形态，不过我们发现每个位置只会成为唯一一个区间的右端点，因此我们实际上只有线性的 n 个区间。

因此我们管这种数据结构叫做“树状数组”。

lowbit

观察：如果我们记 lowbit(x) 表示数 x 二进制表示从右往前最低位的 1 与它之前的所有 0 构成的数，例如 x = (101100)_2 ，那么 lowbit(x)=(100)_2。

利用二进制补码的性质，我们可以得到 lowbit(x) = x & (-x)。

我们发现，树状数组的位置i刚好维护了 (i-lowbit(i),i] 这个长度为 lowbit(i) 的区间。

因此我们只需要一个 for 循环就可以轻松维护出树状数组。

二叉搜索树

维护一个数据结构，它是一个集合，支持：

你只需要一个平均复杂度 O(logn) 的算法，不需要保证最坏复杂度。

我们依然使用一棵二叉树去维护这个集合。

这棵二叉树需要满足：一个结点的权值，大于它左儿子的权值，小于它右儿子的权值，如果有相同权值，那么在这个结点的 count[] 上 +1 。

那么这个二叉树看上去就像是把一个排好序的数组“提起来”（换句话说，这个二叉树的中序遍历有序）

那么它为什么叫做“二叉搜索树”呢，因为这棵树可以非常方便地替我们完成“搜素一个值”这个任务。

从树根出发， 每次检查这个值与当前结点的权值的大小关系，如果相等那么找到了，否则如果值比当前结点小，那么向左走，不然向右走。复杂度 O( 树高 ) 。

接下来我们开始分别实现这 6 个功能：

二叉搜索树和线段树

其实二叉搜索树可以看成某种意义上的线段树，这意味着它可以承担一些区间操作的任务，也可以打懒标记。( 比如 splay 和 fhqtreap 可以做的区间 reverse) 同理，线段树也可以视作一种二叉搜索树，这让它也可以维护一个集合。( 动态开点权值线段树 )

平衡树

二叉搜索树最坏时间复杂度显然是 O(n) 的，其原因在于这棵搜索树可以长得很不“平衡”，(最平衡的二叉树就是完全二叉树 )

因此我们想出了各种奇奇怪怪的方法让二叉搜索树保持平衡，来让它能够真正达到 O(logn) 的时间复杂度。

这里给大家介绍一个非常简单但不是很实用的平衡树：替罪羊树。

它的思路很简单暴力：我们不平衡，那么我们每当整棵树不平衡到一个程度了，就把它整个推平重构成一棵完全二叉树。

这个所谓“不平衡到一个程度”，我们认为：其左或右儿子的大小 > 整个子树大小的 0.7 倍，或者删除的点的数量占整棵树的 (1 – 0.7=0.3) 倍。

因为这个操作支持删除不是很容易，因此我们直接采用懒惰的方法，如果一个结点的 count 为 0 就把它留在那里不动它。

可以通过一些深刻的复杂度证明它的复杂度是 O(nlogn) 的。

字符串

字符串当然就是由若干字符拼成的串。

关于字符串，我们讨论的其中一个就是字符串的“匹配”问题，也就是说，我给出两个字符串，你怎么知道其中一个串是另一个串的子串？它在多少地方出现了？这也是我们本次课研究的问题。其它的问题，我们会放到今后学习各种子串黑科技 ( 后缀数组，后缀自动机，基本子串结构 ) 的时候。

概念：

哈希

什么是哈希？哈希是一种容易被卡的算法。

哈希是一种不能保证正确性的算法，但是这不代表你使用哈希会被随机扣分。

它的运作思路是：我们把一个字符串不一一对应地对应到一个数上，然后比较这两个数就可以得到这两个字符串的关系了。

那么，怎么对应呢？

字符串哈希

我们使用这样一种哈希方法：

将整个字符串视为一个 b 进制的数字对一个大质数 p 取模得到的数字。

譬如，对于字符串 s=“abc” ，这种哈希值对应的结果就是 1+2×𝑏+3×𝑏^2 。

其中 b 和 p 的值可以随便取，一般 b 取 29 或者 31 ，p 取 1e9+7 或者 998244353 。

那么，两个相同字符串的哈希值显然是相同的。

更进一步地，我们可以轻松地求出这个字符串所有子串的哈希值。

哈希冲突

一个 100000 长度的字符串，子串的个数将近 1e10 ，可是你的模数只有 1e9 ，这就意味着这个字符串几乎一定会出现两个不同的子串具有相同的哈希值，那么如果你比较这两个子串，就会得到错误的结果，也就是我们所说的“哈希冲突”。 某种意义上，哈希冲突是无法规避的。然而，这种冲突发生的概率非常微小（你不可能把所有 1e10 个子串两两比较）。因此，我们期望它不会在自然状态下出现这种情况。 如果你不想让 OI 比赛的出题人人为地卡掉你的哈希，那么一个办法是使用不太常见的模数(比如 1e9+33)，不过通常不会有毒瘤出题人会专门设计卡某一个特定哈希值的数据。(如果你遇到了，就狠狠地喷会遭世人唾骂的出题人)

不过，一个更保险的方法是使用双值哈希。顾名思义，就是同时用两套 b 和 p 去计算哈希值，这样相当于有了一个双重保险。就几乎不可能出错了，被卡也很难。

哈希表

维护一个数据结构，是一个集合，支持：

要求总共接近 O(n) 地做完这些事情。

我们采取一个极端措施：给插入的值对一个 1e6 左右的数取模 (1e6-3) 。把得到的数当作 vis[] 的数组下标。

但是因为这个数很小，所以很容易出现哈希冲突，怎么办呢？

答案是把这个 vis[] 数组拓展成一个链表。每次插入一个数，如果发现这个数与其它的数哈希冲突了，就把它挂在先前的这个数后面。

这样就可以做到一个几乎线性的查询复杂度，显著优于同台竞争的线段树和平衡树。

Trie树

我们现在有很多字符串，怎么判断哪些字符串出现过，哪些字符串没有出现过呢？

我们考虑一本字典，如果我们想要在一个字典中找到某个单词，我们的做法是：首先找它的第一个字母，翻到指定页数后开始找第二个字母，如法炮制。

发现这个过程很像一棵树，因此我们可以模仿这个过程建一棵树，我们称为 trie 树。

显而易见地，对于一个小写字母字符集而言，trie 树的每个结点需要一个 ch[][26] 来存储它的 26 个儿子，但是无论是插入还是查找都是 O(len) 的。

01trie

因此我们瞬间得到了一个树高 $log$ 值域的二叉搜索树！（当然，与一般的二叉搜索树略有不同） $Trie$ 瞬间就变得非常厉害了！ 唯一的不足是花费的空间和时间是同阶的，都是 $O(nlogV)$，但是常数要比平衡树优秀很多，可以作为一个低配的平衡树使用。 ## 字符串匹配 给定长一点的字符串 $S$（称为文本串）和短一点的字符串 $T$（称为模式串），求 $T$ 在 $S$ 中的哪些位置出现（找T出现位置的开头位置） 要求 $O(|S|+|T|)

不能使用哈希。

KMP算法

这个名字是三个人的首字母。

它涉及到一个比较深刻的东西，叫做 border 。一个字符串 s 的 border 是 s 的一个子串 s’，满足 s’ 既是 s 的前缀又是 s 的后缀，且 s’ 不是 s 本身。

几个 border 的例子：

这是 $s=‘ababa’
s 的前缀 a ab aba abab ababa
最长 border a ab aba
最长 border 长度 0 0 1 2 3

那么，找到 border 有啥用呢？ 我们考虑暴力字符串匹配的过程

S = ‘aaaaaababab’$ , $T=‘aaaaabab’

我们枚举 T 在 S 上的起点 i ，然后用 j 一位一位地匹配。发现 j=6 的时候寄掉了。此时我们需要从 i=2 再重新匹配吗？并不需要。我们匹配了子串 T[1,5] ，那么下一个有可能成为 T 匹配位置的起点会长成这样。

所以问题就很显然了。我们下一步并不需要从头开始，而只需要从 T 的 border 位置开始即可。 那么我们的算法流程是：失配 \Rightarrow 跳 border\Rightarrow 再失配 \Rightarrow 再跳 border 。 这样，我们每次在 S 上移动一步，在 T 上也移动了一步，border 最多增加 1 ，于是我们最多只会增加|S| 次 border ，那么自然也最多回跳小于 |S| 次 border ，复杂度于是就是 O(|S|+|T|) 。 因为这个跳 border 的操作有点像指示失配之后“下一个”位置在哪的数组，因此有人用 nxt 数组表示 border 。

欸，还没讲怎么求最长 border 呢。 说起来简单，因为我们用到的 border 不会超出 i ，因此直接将 T 和自己匹配即可。 具体来讲，我们可以依次求出每个位置的 border ，因为我们每次要求 border[i] 的时候，只需要比较 T[border[i-1]+1] 和 T[i] 是否相等即可，如果不相等，那么就是失配了，我们继续跳 border 。

s 的前缀 a aa aac aaca aacaa aacaaa
最长 border a a aa aa
最长 border 长度 0 1 0 1 2 2

STL

模板 template

相信大家至少用过std::queue<int>，并都对这个 “int” 非常好奇它为啥可以这么写。

实际上这个东西是 C++ 的一个语法，它的作用类似于我们学过的“通配符”，可以检测任何一种类型，甚至是你自己定义的 struct 。

比如，std::queue 的实现是这样的。

你不用管那些吓人的语法，我们将重点落在这里。

这就是我们的那个类型名的位置。

这个 template 决定了 STL 是相当泛用的。

容器 container

容器就是 STL 里的数据结构，是拿来存放数据的瓶瓶罐罐。

容器分为序列容器 (vector,list,deque)，关联容器 (set,map) 和其它容器 (bitset) 。

你可以简单理解为，数组，平衡树，和 bitset 。

它们是一个个的 class( 你可以把它们当作 struct 来用 )，怎么用？

std:: vector <int> vec;

从左到右分别是命名空间 (standard)，容器名，模板参数，变量名。

然后你就获得了一个名叫 vec 的，里面存放 int 类型的 vector 容器。

迭代器 iterator

迭代器像是 STL 版本的指针，用来在容器的各个元素之间移动。

首先，我们造一个 iterator ， std::vector<int>::iterator it;

这一行从 std::vector<int> 这个类中找出它里面的一个类 iterator ，用它定义了一个变量 it 。

那么这个 it 就可以在 vector 上乱转了，比如 for (it = vec.begin(); it != vec.end(); it++)

如果想要访问 iterator 指向的值，就需要使用 *it 。