暂时退役前部分数据结构 / 算法总结
arfa
·
2019-12-17 12:29:11
·
个人记录
2020.6.20 , 中考大劫。
\text{数组}
数组可以支持 O(1) 查询 , O(1) 修改 , O(n) 插入 , 这是很强大的功能。
\text{栈}
栈可以做很多事情 , 其实就是模拟一个后进后出的数组。
\text{队列}
队列也可以做很多事情 , 它是栈意义上的扩张。
单调队列每次往前删数最差都是 O(n) 的。n , 所以插入删除均摊还是 O(1) 。
有些人会把“单调序列”说成“单调队列” , 如导弹拦截这道题 , 大家自己辨识清楚。
\text{链表}
一个点出度入度都是 1 , 就是链表。O(n) 查询 O(n) 修改 , O(1) 插入。
\text{前缀和}
通过记录 1 \dots n 的信息来达到 O(1) 查询 , O(n) 修改的强大结构。
为什么要单独来讲这样一个简单的结构 ?
\text{差分}
很有趣的东西 , 很喜欢考树上差分。O(1) , 查询 O(n) 。val_i 的定义是 : num_i-num_{i-1} 。
对于区间修改 [l,r] , 就 val_l+k , val_{r+1}+k 即可。val 相加。
考虑树上差分。\text{lca}\{u,v\} 的区间。val_u 和 val_v 都加上 k , \text{father\{lca}\{u,v\}\text{\}} 和 \text{lca}\{u,v\} 都减去 k 。\text{lca}\{u,v\} 只用加一次 , 所以这样子能达到目的。
当然这只是对于点的差分 , 对于边的以及其它可以看 : Danny_boodman 的博客。
\text{并查集}
说一点树的知识先 :1 个入度 k 个出度的图就是 k 叉树。\text u \implies \text{root} 和 \text v \implies \text{root} 弄出来。
很多人喜欢把这个数据结构说成江湖传说。O(1) , 或者说是 O(\alpha(n)) 。Ω(m \log _{1+\frac n m}n) , 具体看 Atalod的博客。
关于按秩合并 , 我没用过。\text{size} 来何必 , 并且不压缩。\log n , 有什么用?\log 。
\text{线段树}
线段树可以说不是树 , 是一种分治。
但是为什么叫线段树呢?
好了 , 这里扯到分治了。[l,r] 分为 [l,\text{mid}] 和 [\text{mid+1},r] 处理。O(\log n) 。\text{max , min} 之类。
对于权值线段树 , 喜欢拿来套。k 小 , 查询最大最小,[l,r] , 它的值代表值域在 [l,r] 内的树的个数。
线段树的题目很灵活 , 定义可以自己弄。
这里不得不提及一下树状数组了。n^2 , 线段树是 4 \times n^2 。
对于二维的线段树 , 建议大家还是多多画图 , 然后理解。O(n^2) 的。m 个 , 所以空间可以做到 O(m \log^2 n) 。\text{KD-Tree} 或树状数组会好一点。
线段树功能还有很多 , 比如 : OI wiki。
\text{主席树}
主席树 , 因为发明者 (黄 jia tai , 后面两个字忘了) 的拼音可以凑成***总理 , 所以因此确立。\text{Chair tree} , 有很多博主写的是 \text{Chair-man tree} ?。k 小等贡献不独立的问题。
何为主席树 ? 主席树是很多线段树连在一起。n 珂线段树 , 那么你是不是可以用这些线段树 ,[l,r] 里面的一些值呢 ?[1,r] 代表第 1 珂到第 r 珂树的和。n 珂线段树 ?[1,r] 前缀和线段树 ,[1,r-1] 到 [1,r] 在线段树就只会有一次插入 ,\log n 的空间。n \log n 的。
可持久化就是说我可以查询在以前的数组的问题 , 也就是现在的数组已经改变。r 珂树不一定要维护 [1,r] 的线段树和 ,[1,l] 的 (l \leq r )。l 直接跳到 r 。n 珂线段树我会怎么做。
当让主席树也有缺点 , 它必须处理一些能前缀和的东西。
关于动态的主席树吗 , 因为主席树是维护一个前缀和的。
\text{树链剖分}
假如区间上的东西都变成了树上的 , 那么有三种情况。
假设我们从每一个叶子节点往上一直到根为一个区间 , 然后数据结构维护。\log 个。O(n) , 而时间就是 O(n \log^2 n) 。
由于树链剖分将树分成了 \log n 个不相交的区间 ,\log ,
\text{CDQ 分治}
发明者没有记错的话叫陈丹琪吧。
首先考虑分治的定义 , 在线段树中讲过。[l,\text{mid}] 和 [\text{mid+1},r] 。[l,\text{mid}] 的内部答案 , [\text{mid+1},r] 的内部答案 , [l,\text{mid}] 对 [\text{mid+1},r] 的贡献。
其实我们就考虑如何求 [l,\text{mid}] 对 [\text{mid+1},r] 的贡献即可。2 \times m 个左端点是 1 右端点是 r 的询问。
等等 , 这些询问好像左端点都是 1 , 那是不是可以排序呢 ?O(n) 统计贡献了。
考虑到只会递归 \log n 层 , 且每一层的总量是 O(n) ,O(n \log n) , 加上迷一样的总定理 , 准确表示就是 O(f(n) \log n) 。常数还是不小的。O(n) , 不过这个处理实在一层里面的 ,O(n) , 又因为有 O(\log n) 层 , 所以可行。
但是这样做有什么好处呢 ?
\text{莫队}
重头戏 \times 1 。莫队的起名应该是因为队长叫莫涛吧。
贡献不独立 , 啥意思 ?\sum\limits^{\text{数字种类个数}}_{c=1}(\sum\limits^r_{i=l} [num_i=c])^2 , 十万询问。n^{\frac 2 3}m 做出来。
如果你是暴力的话 , 那么时间复杂度莫不是 O(nm) ?O(\text{玄学}) 了。(定义 \text{玄学} \leq nm )nm 的。l 标一个块 , 按照 l 所在的块为第一关键字和 r 为第二关键字排序 ,O(nm^{\frac 1 2}) 。
我们来算一下 , 假设块里面有 k 个询问 , 那么移动的的总量其实是 \frac {n^2} k+mk 。k=m^{\frac 1 2} 。 所以总的复杂度就是 O(nm^{\frac1 2}) 。n 越小 m 越大莫队其实越快。
我们算复杂度的时候要把莫队的关键字弄进去。
对于第二个误区 , 举个例子 , 考虑二维的莫队 , 矩阵 n \times n ,n^2m^{\frac 2 3} , 看起来很快。
说起二维莫队 , 我就来讲讲莫队复杂度的规律。k 个关键字的话 (就像带修莫队有 3 个关键字) :O(\text{可移动位置个数} \times \text{询问}^{\frac{k-1} k}) , 简单写就是 O(nm^{1-k^{-1}}) 。\frac{n}{m^{k^{-1}}} 。k 维莫队 , 可以认为它的复杂度是 O(n^km^{\frac {2k-1} {2k}}) ,O(n^2m^{\frac 3 4}) 。是不是很慢。k 维分块的复杂度是 O(n^{\frac {k-1}{k}}m) 。
莫队的复杂度这样定义以后不会再因为其他数据结构的加入而更改 ,\log 数据结构 , 复杂度太高。O(1) , 而查询通常可以达到 n^{\frac 1 2} , 这样子复杂度就比较小 O(n^{\frac 1 2}m+nm^{\frac 1 2}) 。
莫队还有一个骚操作 , 就是二次离线莫队了。O(m) 。留坑。nm^{\frac 1 2} \log n 了……nm^{\frac 1 2} 询问。 我们只需要用分块或者其它东西 ,O(1) 的复杂度即可。O(nm^{\frac 1 2}) 。
\text{upd : 2019-12-19}
先顺带一提 , 我第一次看懂二次离线莫队的博客是 ZZQ 的博客。n+m 空间的做法。[l,r] \implies [l,r+k] , 这些询问是不是有一些特点。i \in (l,r] , 那么每一个的贡献其实就是 num_i \implies [l,i) num_i \implies [1,i)-num_i \implies [1,l) 了。
左端点看起来不能处理 , 但是会发现每一个询问的转移 $l$ 是不会变的。
所以说我们的空间复杂度就变成了 $O(n+m)$。
但是这样子好像不那么严谨 , 我继续写出来所有的转移供打码。
为了方便我还是写只有 $\pm1$ 的情况。
$[l,r] \implies [l,r+1]$ : $+num_{r+1} \implies [1,r]-[1,l-1]
[l,r] \implies [l,r-1]$ : $-num_r \implies [1,r-1]-[1,l-1]
[l,r] \implies [l+1,r]$ : $-num_l \implies -[1,l]+[1,r]
[l,r] \implies [l-1,r]$ : $+num_{l-1} \implies -[1,l-1]+[1,r]
注意一下我们把第一种情况都写在前面 , 第二种都是后面。
\text{upd : 2019-12-27}
我自己出了一道题目 , 给教堂拿去比赛了。不过没人切。\sum\limits_{1 \leq i,j \leq n}[num_i \mod num_j=k] ,num_i=k 且 num_j > k 的话也是有贡献的,k , 第二种贡献为膜你为 k 即可。
Link
\text{分块}
重头戏 \times 2 。分块是一种数据结构 , 也是一种思想。O(1) , 修改 O(n^{\frac 1 2}) 。
用处一 ,O(1) 的分块。O(1) 插入的限制内做很多查询为 O(n^{\frac 1 2}) 的东西。
那什么时候查询是 O(1) 呢?
具体来说就是建立一颗树 , 每个节点代表一个区间 , 像线段树一样。
不同的是对于区间长度为 $k$ 的节点 , 它有 $k^{\frac 1 2}$ 个儿子 , 每个儿子对应区间长度 $k^{\frac 1 2}$。
这样子的话查询的复杂度就是 $O(\log \log n)$ 的了。
对于修改 , 区间修改和单点修改都跟线段树一样的 , 打标记即可。
修改的复杂度为 $\sum\limits^{\log \log n}_{i=1} n^{\frac 1{2^i}}$ , 加起来不会超过 $2n^{\frac 1 2}$。
$\text{upd : 2019-12-27}
我自己出了一道题目 , 给教堂拿去比赛了。不过也没人切。Link。\max\limits_{l \leq i,j \leq r\ ,\ num_i \not = num_j ,\ \text A(num_i)-\text A(num_j) \leq K} \text A(num_i) 。\text A(T)=\sum\limits^n_{i=1} [T=num_i] 。K 的时候 , 有贡献-K 的数的个数的数组 , 这个东西维护 O(1) 。O(1) 就可以了啊 , 查询 O(n^{\frac 1 2}) 0 就是有贡献 ,
那我们还是要说说为什么有些时候我们的分块查询和修改都不是 O(1) ,
用处二 ,\text{FHQ Treap} 是一个常数及其大的算法。O(\log \sqrt{n}) 。\text{Treap} 维护即可。O(\log k+\log \left\lfloor\frac{n}{k}\right\rfloor) (k 为块的数量)O(\log n) , 所以我说是对“常数”的优化。\text{Sqrt tree} , 然而我不会。
第二个例子 , 题目是求 T=10^{11} 内的质数个数 , 正解洲阁筛暴毙 ,[1,\left\lfloor\frac{T}{k}\right\rfloor \times k] 的表 (k 为块的数量)O(k) , 查询的时间复杂度为 O(\left\lfloor\frac{T}{k}\right\rfloor) 。k 可以设置成 k=n^{\frac 1 2} , 10^{5.5} 。\text{Miller} 来求的 , 假如这种算法的复杂度为 30 \log n ,3 \times 10^{6.5} \log 10^{11} 。3 \times \left\lfloor\frac{T}{k}\right\rfloor \log 10^{11}=k , 当然不用准确求出。
好奇的算一下 \left\lfloor\frac{T}{k}\right\rfloor=\left\lfloor\frac{k}{30}\right\rfloor , k=(30T)^{\frac 1 2} 。\sqrt{30} 倍 , 时间复杂度降了 \sqrt{30} 倍。
上述办法可能还是会被卡 , 其实可以将 k 直接调成 10^7 ,3 \times 10^5 \log 10^{11} 了!O(\frac T k \log T) , 常数 30 。空间 O(k) 。O(\frac{T^{\frac{3}{4}}}{\ln T}) , 空间 O(n^{\frac 1 2}) 。
\text{upd : 2020-1-26}
有一道题 , 可以打表 , 分块打表更快。\sum\limits^n_{i=1} f(i) , f(a) 为 a 的最小质因子。\text{Min25} 。 然后讲讲如何打表。n 分成 \frac n k 个块 , 每个块有 k 个数。a 的最小质因子不大于 a^{\frac 1 2} , 所以我们预处理 n^{\frac 1 2} 里的质数个数。O(k \ln n^{\frac 1 2}) , 空间为 O(\frac n k) 。\frac n k=k \ln n^{\frac 1 2} , 显然 k={(\frac n {\ln n^{\frac 1 2}})}^{\frac 1 2}=\frac{n^{\frac 1 2}}{\ln^{\frac 1 2} n^{\frac 1 2}} , 时空复杂度就都是 O(\sqrt{n \ln n^{\frac 1 2}}) 。10^{12} ~10^{13} 的范围。
用处三 ,[l,r] , 将 num_l 放在 num_r 的位置上 , (l,r] 向左平移。n,m=10^5 。O(n^{\frac 1 2}) 。
当然分块还可以做一些问题 , 比如查询区间第 k 小。O(m \log n) 的。\text{Recf}[l,r] 为 [1,l] 区间中数值在第 r 块的个数 ,\text{Times}[l,r] 为 [1,l] 区间中数值为 r 的个数。O(mn^{\frac 1 2}) , 空间 O(n^{\frac 3 2 }) 。
但是不要以为分块只是为了把经典数据结构思路简单化了。k 小带单点修改呢 ? 难道我们要用 n^{\frac 1 2} \log n 的二分 ?O(k \log n) , 修改是 O(\left\lfloor\frac{n}{k}\right\rfloor) , 我们列一个方程。k=\left\lfloor\frac{n}{\log n}\right\rfloor^{\frac 1 2} , 那么复杂度就变为 n^{\frac 1 2} \log^{\frac 1 2} n , 人们喜欢写成 \sqrt{n \log n} 。
有一些经典的问题 , 比如区间众数。
我们把这个数列分成 $\frac n k$ 块 , 每个块有 $k$ 个数。
然后我们预处理一个 $\text{Ans}[l,r]$ 代表 $l$ 块到 $r$ 块的答案 , $\text{Times}[l,x]$ 代表 $1$ 到 $r$ 块数字为 $x$ 的个数。
这样子的话 , 我们每一次查询 , 就已经有了一个整块的答案 ,
然后在散块那里去更新看有没有比这个众数的出现次数更多的。
时间复杂度 $O(mk)$ , 空间复杂度 $O(\frac{n^2}{k})$。两者可达最优 , 为 $O(nm^{\frac 1 2})$。
最最最经典的问题 , 莫过于树套树了。主要操作可以看二逼平衡树。
我们设一个 $\text{Times}[i,j]$ 为在第 $i$ 块,权值为 $j$ 的个数。设 $\text{Fock[i,j]}$ 代表 $1$ 到第 $i$ 块权值为 $j$ 的个数。
设 $\text{Block}[i,j]$ 代表 $1$ 到第 $i$ 块,权值在第 $j$ 块的个数。查询的时候我们直接搞一搞,修改我们也搞一搞就好了。
查询 $k$ 的排名 , 只需要对边角暴力一下 , 然后用 $\text{Block}$ 统计答案 (要对本块再次进行暴力)。
查询排名为 $k$ 的数字,我们再次把边角加起来 , 然后同 $\text{Block}$ 一起统计答案。
单点修改 , 我们把 $\text{Times}$ 改一下 , 然后对后面的 $\text{Fork}$ 和 $\text{Block}$ 进行实时维护。
查 $k$ 的前继,我们把边角加起来 , 然后看 $k$ 这个块有没有前继 , 没有用 $\text{Block}$ 往前跳 , 后继同理。
这题 , 未来日记。比较好玩。
如果有人将此题的数据卡 $\text{std}$ 的复杂度到 $O(mn^{\frac 1 2} \log _{1+\frac n m}n)$ , 那么他巨。
首先我们设一个 $\text{Times}[i,j]$ 为第 $i$ 块,权值为 $j$ 的个数。
设 $\text{Fock}[i,j]$ 代表 $1$ 到第 $i$ 块权值为 $j$ 的个数。设 $\text{Block}[i,j]$ 代表 $1$~$i$ 块 , 权值在第 $j$ 块的个数。
满足 $\text{Times}[i,j]$ 实时更新, 且一次我们只触及 $x,y$ 两个数,等于单点修改 , 所以只需要 $n^{\frac 1 2}$ 的时间就可以更新 $\text{Fock}[i,j]$ , $\text{Block}[i,j]$ 同理。
其次 , 我们对大块进行修改的时候,直接一个并查集即可。
不过我们会发现,对于残余的块修改的时候 , 我们可能会违背这个块的并查集。所以对残余块修改时重构一下这个块的并查集。
其它题解上面说只重构 $x,y$,常数减。
然后就是一些关于位置的问题。
比如 , 两个操作 , 第一个操作 , 查询一个区间某个数的出现次数。
第二个操作 , 对于区间 $[l,r]$ , 将 $num[r]$ 转移到 $num[l]$ , 然后将 $num[i]$ 转移到 $num[i+1]$ , $i \in (l,r]$。 就是平移。
这个东西只需要亿点细节 , 用分块就可以了。
想想 , 在分块里面套队列的话 , 每一次平移 , 前后搞一下即可。
还有一道题 , 天降之物。
因为这道题我并没有 $\text{A}$ 且我的方法会被卡 (应该)。 所以我就随便说说。
由于答案只能由左右两边的点与自己构成,意思就是一个 $x$ 和一个 $y$,
如果它们之间存在着 $x_1$,那么对答案产生贡献的就只有 $(x_1,y)$ 而不可能是 $(x,y)$ , $\text{Dis}(x,y)$ 一定大于 $\text{Dis}(x_1,y)$。
考虑分块,记录一个 $\text{Ans}[i,x,y]$ 代表第 $i$ 块 $x$ 和 $y$ 的答案,动态空间可以做到 $n^{\frac 3 2}$。
然后记录一个 $\text{Dis}[i,x,0/1]$ 代表第 $i$ 块最左边 (或者右边) 离块的边缘的距离是多少。
前者先记录单独每一个块的答案,后者用来记录跨块的答案贡献。当然,如果你觉得自己的空间写得十分的小的话,你可以尝试搞两个分块,那就不用后者了。
但是考虑到 $\text{Ans}[i,x,y]$ 的空间需要动态,所以需要一个 $\text{Num}[i,x]$ 记录第 $i$ 块 $x$ 的编号,然后还要开一个队列来维护这些编号 , 空间常数巨大。
$\text{upd : 2020-1-28}
\text{upd : 2020-2-20}
\text{upd : 2020-2-23}
三天说的是同一个东西我就直接全部一起 \text {upd} 了。\text{idea} 是康了 \text{lxl} 的建表法进行的少许改动 , 所以还是称之为 \text{lxl} 建表法。
本算法可以有效的提高求 \text{rmq} 的使用效率 , 当然 , 是比笛卡尔树会简单很多。\text{st} 表慢。
以下可以默认 n=m=10^7 , 且求最大值。
我们把序列分成 \frac n k 块 , 每块有 k 个数。\frac n k \log \frac n k 。O(1) 了。O(mk) , 建表 \frac n k \log \frac n k 。mk=\frac n k \log \frac n k , 可以得出 k\approx 4.58862 , 也就是说整个程序的运算量大概在 4.58862 \times 10^7 左右 , 加常数很大。
然后我们有两种解决方式 , 一种是直接调块 , 一种是套线段树。(\frac n k)^{-2} , 那么如果我们的询问均摊 , 就会有 (\frac n k)^{-2}m 个询问是在同一块的。(\frac n k)^{-2}mk , 等于 \frac {mk^3} n 。k=\log n , 建表的时间复杂度就是 O(n \log(n \log^{-1} n) \log^{-1} n) , 会发现 {n^{-2}m\log^3 n} 还不到 1 。\frac n k \log \frac n k=m \log k , k\approx 7.177707 ,
完结。
$\text{upd : 2020.2.1}
一个新的 \text{idea} , 但是并没有程序验证过。x , 历史查询区间和。x 即可。那么查询到这个地方的和就是这个块的大小乘上 x 。\frac n k 块 , 每块的大小为 k 。那么整块的记录空间就是 O(\frac {mn} k ) 的。因为每次查询只会有两个散块 , 所以记录空间就是 O(mk) 的。O(\frac {mn} k+mk) 。