https://wiki.cvbbacm.com/ 2026-04-30T04:02:24+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-06-05T15:49:06+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84:%E4%BA%8C%E7%BB%B4%E7%BA%BF%E6%AE%B5%E6%A0%91&rev=1591343346&do=diff 前言 用处与一维线段树类似，实现区间的修改、查询工作，知识是在二维的区域中实现的。 两种实现方式 * 普通列表项目每一个节点代表一颗线段树 * 普通列表项目四分法转为一维线段树$O(n^2\times log_n^2)$$O(log_n^2)$$O(n)$ text/html 2020-07-06T09:15:44+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84:%E5%B9%B6%E6%9F%A5%E9%9B%86&rev=1593998144&do=diff 并查集 前言 并查集应用广泛，用于判断元素是否属于同一个集合以及合并集合。 复杂度 最坏到 $O(n)$，单独使用路径压缩达到 $O(n+f(1+\log_{2+f/n}n))$，单独使用按秩合并可达到 $O(\log{n})$，两者同时使用可以达到 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，可以认为非常小。按秩合并即每次将小的集合合并到大的集合中去，可以减少修改次数。$\text{fa}$$m$$\text{find}$$\text{fa}$$\text{fa}$$\text{fa[x]}$$\text{fa}$$\text{fa}$$\text{fa}$$\text{fa}$$\text{fa}$$\text{fa}$$m$$h$$1\to2\to3\to1$… text/html 2020-05-27T18:15:51+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84:%E7%BA%BF%E6%AE%B5%E6%A0%91&rev=1590574551&do=diff 线段树 前言 解决的问题 在线维护修改、查询区间最值、求和，可以扩充到二位线段树、三位线段树。 复杂度 一维线段树每次更新和查询的时间复杂度为$O(log{N})$ 概念 二叉树的结构，每一个节点代表一个区间，每个子节点代表父结点区间的一半。 初始版本左儿子下标是父亲下标的两倍，右儿子下标为父亲下标的两倍+1。 text/html 2020-05-22T20:40:32+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84:%E8%87%AA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91&rev=1590151232&do=diff 自平衡二叉查找树 未完待续..（例题代码什么的再补） 二叉查找树(BST) 在二叉树中查找一个节点的复杂度是O(n)。我们可以构建二叉查找树来改善查询时间。 特征 在二叉查找树中每一个节点的左子树中所有结点的值都小于该结点的值，右子树中所有结点的值都大于该结点的值。$log_2{n}$$log_2{n}$$\quad\quad $$\quad\quad $ text/html 2020-07-26T19:10:22+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:no_morning_training:shaco:%E7%9F%A5%E8%AF%86%E7%82%B9:%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84:ac%E8%87%AA%E5%8A%A8%E6%9C%BA&rev=1595761822&do=diff 简述 AC自动机可以说是KMP的进阶版，支持多个模式串在目标串中的查询。 复杂度为$O((N+M)\times L)$。 思路 首先对模式串进行trie树的构建。 接着引入$\text{fail}$的概念：对于trie树的每一个结点都有一个fail值，fail对应了另一个树上的结点，从root到fail的字符串是从root到该结点的字符串的最大后缀。 类似于$\text{KMP}$$\text{Next}$