树状数组 & Trie树
树状数组
要求
- 满足结合律 & 可差分
- 结合律： (x\ \circ\ y)\ \circ\ z ，其中 \circ 是一个二元运算符
- 可差分：具有逆运算的运算，即已知 x\ \circ\ y 和 x 可以求出 y
- 在差分数组等的帮助下，还可解决更强的区间加单点值和区间加区间和的问题
实现
- 从 c[x] 开始往前跳，由 c[x] 管辖 a[x-\text{lowbit}(x) + 1\dots x]
- 令 x\leftarrow x - \text{lowbit}(x) ，如果 x=0 说明已经跳到尽头了，终止循环
- 否则回到第一步
- 将跳到的 c 合并
- l(x)=x-\text{lowbit}(x)+1 即 l(x) 是 c[x] 管辖范围左端点
- 对于任意正整数 x ，总能将 x 表示成 s\times 2^{k+1}+2^k 的形式，其中 \text{lowbit}(x)=2^k
性质
- 对于 x\le y ，要么有 c[x] 和 c[y] 不交，要么有 c[x] 包含于 c[y]
- 在 c[x] 真包含于 c[x+\text{lowbit}(x)]
- 对于任意 x<y<x+\text{lowbit}(x) ，有 c[x] 和 c[y] 不交
- 设 fa[u] 表示 u 的直系父亲：
- u<fa[u]
- u 大于任何一个 u 的后代，小于任何一个 u 的祖先
- 点 u 的 \text{lowbit} 严格小于 fa[u] 的 \text{lowbit}
- 如果 c[1] 的高度是 0 ，则点 x 的高度是 \log_2\text{lowbit}(x)
- c[u] 真包含于 c[fa[u]]
- c[u] 真包含于 c[v] ，其中 v 是 u 的任意祖先
- c[u] 真包含于 c[v] ，其中 v 是 u 的任意后代
- 对于任意 v'>u ，若 v' 不是 u 的祖先，则 c[u] 和 c[v'] 不交
- 对于任意 v<u ，如果 v 不在 u 的子树上，则 c[u] 和 c[v] 不交
- 设 u = s \times 2^{k+1}+2^k ，则其儿子数量为 k = log_2\,\text{lowbit}(x) ，编号分别为 u-2^t\,(0 \leq t \leq k)
- u 的所有儿子对应 c 的管辖区间恰好拼成 [l(u),u-1]
时空复杂度
- 空间复杂度 O(n)
- 时间复杂度：查询 O(\log n) ，单点修改 O(\log n)
区间加 & 区间求和
-
考虑序列 a 的差分数组 d ，其中 d[i]=a[i]-a[i - 1]
-
由于差分数组的前缀和就是原数组，所以 a_i=\sum^i_{j=1}d_j
-
考虑将查询区间和通过差分转化为查询前缀和
-
那么考虑查询 a[1\dots r] 的和，即 \sum^r_{i=1}a_j ，进行推导：
\sum^r_{i=1}a_i=\sum^r_{i=1}\sum^i_{j=1}d_i\times(r-i+1)=\sum^r_{i=1}d_i\times(r+1)-\sum^r_{i=1}d_i\times i -
\sum^r_{i=1}d_i 并不能推出 \sum_{i=1}^rd_i\times i 的值，所以要用两个树状数组分别维护
二维树状数组
-
也被称作树状数组套树状数组，用来维护二维数组上的单点修改和前缀信息问题
-
用 c(x,y) 表示 a(x-\text{lowbit}(x)+1,y-\text{lowbit}(y)+1)\dots a(x,y) 的矩阵总信息
-
即一个以 a(x,y) 为右下角，高 \text{lowbit}(x) ，宽 \text{lowbit}(y) 的矩阵的总信息
-
对于单点修改，设：
f(x,i)=\left\{\begin{matrix}x &i=0 \\f(x,i-1)+\text{lowbit}(f(x,i-1)) &i>0 \end{matrix}\right. -
即 f(x,i) 为 x 在树状数组形态上的第 i 级祖先（第 0 级祖先是自己）
-
则只有 c(f(x,i),f(y,j)) 中的元素管辖 a(x,y) ，修改 a(x,y) 时只需要修改所有 c(f(x,i),f(y,j))
-
其中 f(x,i)\le n,f(y,j)\le m
// 修改 for (int i = x;i <= n;i += lowbit(i)) for (int j = y;j <= m;j += lowbit(j)) c[i][j] += v; // 询问 int ans = 0; for (int i = x;i > 0;i -= lowbit(i)) for (int j = y;j > 0;j -= lowbit(j)) ans += c[i][j]; return ans;
子矩形加、求子矩形和
-
考虑维护差分数组：
d(i,j)=a(i,j)-a(i-1,j)-a(i,j-1)+a(i-1,j-1) -
对左上角 (x_1,y_1) ，右下角 x_2,y_2 的子矩形区间加 v
-
相当于在差分数组上，对 d(x_1,y_1) 和 d(x_2+1,y_2+1) 分别单点加 v
-
对 d(x2+1,y_1) 和 d(x_1,y_2+1) 分别单点加 -v
-
对于点 (x,y) ，它的二位前缀和可以表示为
\sum^x_{i=1}\sum^y_{j=1}\sum^i_{h=1}\sum^j_{t=1}d(h,k)=\sum^x_{i=1}\sum^y_{j=1}d(i,j)\times(x-i+1)\times(y-j+1)\\=\sum^x_{i=1}\sum_{i=1}^yd(i,j)\times(xy+x+y+1)-d(i,j)\times i\times(y+1)-d(i,j)\times j\times(x+1)+d(i,j)\times i\times j -
所以需要维护四个树
-
状数组，分别维护 d(i,j),d(i,j)\times i,d(i,j)\times j,d(i,j)\times i\times j 的和信息
权值树状数组
- 例：单点修改，查询全局第 k 小
- 对于单点修改，只需要将对原序列的单点修改转化为对权值数组的单点修改即可
- 具体来说，原数组 a[x] 从 y 修改为 z ，转化为对权值数组 b 的单点修改就是 b[y] 单点减 1 ， b[z] 单点加 1
- 对于查询第 k 小，考虑二分 x ，查询权值数组中 [1,x] 的前缀和，找到 x_0 使得 [1,x_0] 的前缀和 <k
- 而 [1,x_o+1] 的前缀和 \ge k ，则第 k 大的数是 x_0+1 ，这里认为 [1,0] 的前缀和是 0
- 时间复杂度 O(\log^n)
- 也可以用倍增代替二分，时间复杂度降低为 O(\log n)
全局逆序对（全局二位偏序）
- 给定长度为 n 的序列 a ，求 a 中满足 i<j 且 a[i] > a[j] 的数对 (i,j) 的数量
- 设当前 a[i] = x 查询 b[1\dots x-1] 的前缀和，即为左端点为 a[i] 的逆序对数量
- b[x] 自增 1
Trie
定义
- 一颗像字典一样的树
维护异或极值
-
将数的二进制表示看作一个字符串，就可以建出字符集为 \{0,1\} 的 \texttt{Trie} 树
-
给你一棵带边权的树，求 (u,v) 使得 u 到 v 之间的路径的边权异或和最大，输出这个最大值
-
指定一个根 root 用 T(u,v) 表示 u 到 v 之间的路径的边权异或和，那么 T(u,v)=T(root,u)\oplus T(root,v) ，因为 \text{lca} 以上的部分异或两次抵消了
-
如果将所有 T(root,u) 插入到一棵 \texttt{Trie} 树中，就可以对每个 T(root,u) 快速求出和它异或和最大的 T(root,v)
-
从 \texttt{Trie} 的根开始，如果能向和 T(root,u) 的当前为不同的子树走，就向那边走，否则没有选择
int T[maxn][2], cnt; void insert(int v,int rt) { for (int i = 29;i >= 0;i --) { if (!T[rt][(v >> i) & 1]) T[rt][(v >> i) & 1] = ++ cnt; rt = T[rt][(v >> i) & 1]; } } int query(int v,int rt) { for (int i = 29,k;i >= 0i --) { k = !((v >> i) & 1); if (T[rt][k]) rt = T[rt][k], ans += (1 << i); } else rt = T[rt][k]; return ans; }
有限状态自动机
- \texttt{deterministic finite automaton,DFA}
- 由：
- 状态集合 Q
- 字符集 \Sigma
- 状态转移函数 \delta:Q\times\Sigma\to Q ，即 \delta(q,\sigma)=q',\ q,q'\in Q,\sigma\in \Sigma
- 一个开始状态 s\in Q
- 一个接收的状态集合 F\subseteq Q
- 组成的五元组 (Q,\Sigma,\delta,s,F)
AC 自动机
-
以 \texttt{Trie} 的结构为基础，结合 KMP 的思想建立的
-
在初始时会将若干个模式串丢到一个 \texttt{Trie} 里，然后在 \texttt{Trie} 上建立 AC 自动机
-
构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想
- 考虑字典树中当前的结点 u ，u 的父节点是 p ， p 通过字符
c的边指向 u ，即 \operatorname{trie[p,\texttt{c}]=u} - 假设深度小于 u 的所有结点的 fail 指针都已求得。
- 如果 \operatorname{trie[fail[p],\texttt{c}]} 存在：则让 u 的 fail 指针指向 \operatorname{trie[fail[p],\texttt{c}]} 。相当于在 p 和 \operatorname{fail[p]} 后面加一个字符
c，分别对应 u 和 fail[u] 。 - 如果 trie[fail[p],\texttt{c}] 不存在：那么我们继续找到 trie[fail[fail[p]],\texttt{c}] 。重复 1 的判断过程，一直跳 fail 指针直到根节点
- 如果真的没有，就让 fail 指针指向根节点
// 模板 struct node { node *fail; node *next[26]; int count; node() { count = 0; memset(next, NULL, sizeof(next)); } } *q[15]; void insert(char *str, node *root) { node *p = root; int i = 0, index; while (str[i]) { index = str[i] - 'a'; if (p -> next[index] == NULL) p -> next[index] = new node(); p = p -> next[index]; i++; } p->count++; } void buildAcAutomation(node *root) { int i; root -> fail = NULL; q[head++] = root; while (head != tail) { node *temp = q[tail++]; node *p = NULL; for (i = 0; i < 26; i++) { if (temp -> next[i] != NULL) { if (temp == root) temp -> next[i] -> fail = root; else { p = temp -> fail; while (p != NULL) { if (p -> next[i] != NULL) { temp -> next[i] -> fail = p -> next[i]; break; } p = p -> fail; } if (p == NULL) temp -> next[i] -> fail = root; } q[head++] = temp -> next[i]; } } } } int query(node *root) { int i = 0, cnt = 0, index, len = strlen(str); node *p = root; while (str[i]) { index = str[i] - 'a'; while (p -> next[index] == NULL && p != root) p = p -> fail; p = p -> next[index]; p = (p == NULL) ? root : p; node *temp = p; while (temp != root && temp -> count != -1) { cnt += temp -> count; temp -> count = -1; temp = temp -> fail; } i++; } return cnt; } - 考虑字典树中当前的结点 u ，u 的父节点是 p ， p 通过字符
希望大家给蒟蒻一个赞 qwq