UOJ Logo negiizhao的博客

博客

<del>noip退役选手的另一些扯淡</del>维护双向加字符的字符串的隐式后缀树

2018-12-25 00:00:01 By negiizhao

凛冽的风……

仿佛要将这最后的,仅剩的,微不足道的,存在的意义,剥下呢……


大概今年 6 月的时候用后缀树推了一遍 Blumer 的后缀自动机构造算法,还考虑了一些其他相关的东西,不过并没想清楚……前不久听说北大集训出了这样的题,于是就把这个坑填上了……这次要写的是,写起来要考虑的东西略多的维护双向加字符的字符串的隐式后缀树,就当是给大家的圣诞节礼物吧。

6 月时写过用后缀树解释 Blumer 的后缀自动机构造算法,但可能不是很能看,所以就没有发出来了。


阅读这篇文章需要前置技能 Ukkonen's algorithm 并会用后缀树解释 Blumer 的后缀自动机构造算法,以下仅作简要的介绍。

Ukkonen's algorithm 维护了字符串的隐式后缀树,并支持向后增加字符。

隐式后缀树是将后缀 trie 中所有只有一个孩子的结点和它的孩子合并后得到的树,这相当于字符串中所有只出现了一次的后缀的 trie 按后缀树的合并方法合并后得到的树。可以注意到未加入的后缀是所有后缀中最短的一些。

算法维护了最长的未加入的后缀在树中的位置,向后增加字符时,已加入的后缀会增加一个字符,维护的位置也会发生改变,如果树中没有新的位置,那么加入一个后缀,继续检查更短的后缀的位置。

快速找到更短的后缀的位置需要使用后缀链接,一个结点的后缀链接是将当前结点对应的最长的字符串的第一个字符去掉,得到的字符串对应的结点,这个字符串也是这个结点对应的最长的字符串。

Blumer 的后缀自动机构造算法维护了字符串的后缀树,并支持向前增加字符。

向前增加字符相当于加入一个后缀,于是需要找到这个后缀的在树中的最长的前缀在树中的位置,在这个位置加入一个结点。

加入结点的位置可以用后缀自动机的转移快速找到,后缀自动机的转移和后缀链接相反,是在当前结点对应的字符串前增加一个字符,得到的字符串对应的结点,根据 begin-pos 等价关系,容易发现所有串对应的结点是相同的。

显然,如果需要向后增加字符,只能维护隐式后缀树,否则非叶后缀结点的变化将难以维护。于是考虑在 Ukkonen's algorithm 基础上维护类似后缀自动机转移的东西,并用类似 Blumer 的算法的做法支持向前增加字符。

首先需要对隐式后缀树定义转移。

非叶结点到非叶结点的转移和后缀树没有什么区别,用后缀树的性质容易看出是良好定义的。

对于非叶结点到叶结点,我们认为有转移当且仅当非叶结点对应的所有字符串前增加一个字符,得到的字符串都对应这个叶结点。

对于叶结点,显然只有某个后缀对应的结点到长度比它大一的后缀对应的结点的转移。

现在考虑 Ukkonen's algorithm 过程中需要怎么维护转移边。

加入后缀时,如果有加入非叶结点,需要复制它的孩子的所有转移。

如果是这次增加字符导致的第一次加入后缀,那么加入位置结点增加一个到上一个加入的后缀结点的转移,否则增加一个到上一个加入位置结点的转移。

加入的后缀结点有一个到上一个加入的后缀结点的转移。

如果加入了一个非叶结点,显然需要将一些转移修改为到它,这在找下一个后缀的位置时顺便修改即可。注意加入位置结点为根和加入位置结点的 parent 为根的情况。

最后需要检查最长待加入后缀是否和维护的位置的结点对应的最长串相同,如果是,维护的位置的结点增加一个到上一个加入的后缀结点的转移。

现在考虑怎么向前增加字符。

主要框架和 Blumer 的算法类似,但注意到加入一个后缀可能会使一个后缀结点变为非叶结点,这可以通过检查 Ukkonen's algorithm 维护的位置判断。

分裂结点时可能会影响 Ukkonen's algorithm 维护的位置相关的信息,分裂出的结点可能会增加一个到最短已加入后缀的后缀结点的转移。

时间复杂度分析与 Ukkonen's algorithm 和 Blumer 的后缀自动机构造算法基本相同,可能某些分析方法的势函数需要改变。

这个方法有和 Ukkonen's algorithm 和 Blumer 的后缀自动机构造算法相同的时间复杂度,但写起来要考虑的东西略多,不知是否能找到更简单的实现或更好的做法。

更进一步的扩展不在本文讨论范围内,相关内容参见 维护双向加字符的字符串

北大集训2018 Day3 close AC 代码,可能实现得并不优美(

<del>noip退役选手的一些扯淡</del>关于优化形式幂级数计算的牛顿法的常数

2018-11-27 18:16:44 By negiizhao

对不起……让您失望了呢……

2 年过去了……我还是一点进步都没有……一次大型比赛都没打好……

真的会有那样一天……像您那样强吗?……


想写的那些东西果然还是太麻烦了……根本写不动……就写一些没什么意思的东西吧……关于优化求形式幂级数的牛顿法的常数。

虽然写得很糟糕但还算是能看的,所以就发出来了。


以下是废话部分,可以跳过

对于给定的精度 $n$ 和环 $R = \mathbb C$ 或 $\mathbb Z/p$,$R[[x]]$ 中的形式幂级数 $f$ 被表示为一个 $R[x]$ 中的多项式 $f \bmod x^n$。

对于 $f, g \in R[x]$ ,我们可以通过 3 次 FFT 和 $n$ 次乘法用 $O(n \log n)$ 时间计算出 $fg$。对于 $f, g \in R[[x]]$ ,给定 $f \bmod x^n$ 和 $g \bmod x^n$,我们可以用和多项式乘法几乎相同的时间计算出 $fg \bmod x^n = (f \bmod x^n)(g \bmod x^n) \bmod x^n$。

牛顿法

对于形式幂级数 $f, t \in R[[x]]$ ,满足它们的复合 $t(f)=0$ ,令 $f_0 = f \bmod x^n$ ,那么有 $$ f \bmod x^{2n} = f_0 - \frac{t(f_0)}{t'(f_0)} \bmod x^{2n} $$

这可以通过 $t$ 在 $f_0$ 泰勒展开得到: $$ 0 = t(f) = t(f_0) + \frac{t'(f_0)(f - f_0)^1}{1!} + \frac{t''(f_0)(f - f_0)^2}{2!} + \dots $$

注意到 $(f - f_0)^2$ 最低非0项为 $x^{2n}$ 项,于是有 $$ \begin{align} 0 &= t(f_0) + t'(f_0)(f - f_0) \pmod{x^{2n}} \\ 0 &= \frac{t(f_0)}{t'(f_0)} + (f - f_0) \pmod{x^{2n}} \\ f &= f_0 - \frac{t(f_0)}{t'(f_0)} \pmod{x^{2n}}\tag*{$\blacksquare$} \end{align} $$


现在我们考虑各种函数直接按照式子计算所需要的时间。我们认为长度为 $2n$ 的 FFT 计算所需时间为 $T(n)$,2 个精度为 $n$ 的形式幂级数的乘法需要 $M(n) = (3 + o(1))T(n)$ 时间。

倒数

对于 $f \in R[[x]]$,令 $g = 1/f$,求 $g$。

相当于 $t(g)=fg-1=0$,令 $g_0 = g \bmod x^n$ ,那么有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - \frac{fg_0-1}{f} \bmod x^{2n} \\ &= g_0 - (fg_0-1)g \bmod x^{2n} \end{aligned} $$

(好像能直接得到这个式子……)注意到 $fg_0-1 \bmod x^n = 0$ ,所以右侧 $g$ 的精度只需要达到 $n$。 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - (fg_0-1)g_0 \bmod x^{2n} \\ &= 2g_0 - fg_0^2 \bmod x^{2n} \end{aligned} $$

从 $g \bmod x^n$ 计算 $g \bmod x^{2n}$ 需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法,用时 $(9+o(1))T(n)$。所以计算 $g \bmod x^n$ 所需总时间为 $(9+o(1))T(n)$。

商数

对于 $f, h \in R[[x]]$,令 $g = 1/f, q = hg = h/f$,求 $q$。

显然先求 $g = 1/f$,再求 $q = hg$ 即可。总时间为 $(12+o(1))T(n)$。

平方根

对于 $f \in R[[x]]$,令 $g = f^{1/2}, h = 1/g = f^{-1/2}$,求 $g$。

相当于 $t(g)=g^2-f=0$,令 $g_0 = g \bmod x^n, h_0 = h \bmod x^n$ ,那么有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - \frac{g_0^2-f}{2g_0} \bmod x^{2n} \\ &= g_0 - \frac{(g_0^2-f)h_0}{2} \bmod x^{2n} \end{aligned} $$

从 $g \bmod x^n, h \bmod x^n$ 计算 $g \bmod x^{2n}$ 需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法,计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代,用时 $(18+o(1))T(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $(18+o(1))T(n)$ ,如果不需要计算 $h$,可以省略最后一次迭代中的相关计算,总时间为 $(13.5+o(1))T(n)$。

对数

对于常数项为 $1$ 的 $f \in R[[x]]$,令 $\displaystyle g = \log f = \sum_{i=1}^\infty \frac{(-1)^{i-1}(f-1)^i}{i}$,求 $g$。

我们有 $$ (\log x)' = \left(-\sum_{i=1}^\infty \frac{(1-x)^i}{i}\right)' = \sum_{i=0}^\infty{(1-x)^i} = \frac{(1-(1-x))\sum_{i=0}^\infty{(1-x)^i}}x = \frac1x $$

所以 $(\log f)'=f'\log'f=f'/f$,于是求商数即可。总时间为 $(12+o(1))T(n)$。

指数

对于常数项为 $0$ 的 $f \in R[[x]]$,令 $\displaystyle g = \exp f = \sum_{i=0}^\infty \frac{f^i}{i!}, h = 1/g = 1/\exp f$,求 $g$。

为了方便阅读,以下用 $\smallint(f)$ 表示 $\displaystyle \sum_{i=1}^\infty \frac{[x^{i-1}]f}ix^i$。

相当于 $t(g)=\log g-f=0$,令 $g_0 = g \bmod x^n$ ,那么有 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - \frac{\log g_0-f}{1/g_0} \bmod x^{2n} \\ &= g_0 - (\log g_0-f)g_0 \bmod x^{2n} \\ &= g_0 - (\smallint{({g_0}'/g_0)}-f)g_0 \bmod x^{2n} \end{aligned} $$

从 $g \bmod x^n, h \bmod x^n$ 计算 $g \bmod x^{2n}$ 需要 1 次计算倒数的迭代,需要 1 次长度为 $2n$ 的乘法、1 次长度为 $4n$ 的乘法,计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代,用时 $(27+o(1))T(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $(27+o(1))T(n)$ ,如果不需要计算 $h$,可以省略最后一次迭代中的相关计算,总时间为 $(22.5+o(1))T(n)$。


考虑多项式乘法,注意到很多情况下我们知道结果中至少一半的系数,只有中间 $n$ 个不知道,而长度为 $n$ 的 FFT 实际上计算的是循环卷积 $fg \bmod x^n - 1$,所以我们可以减去已知的系数,得到未知的 $n$ 个系数。

倒数

对于 $f \in R[[x]]$,令 $g = 1/f$,求 $g$。

考虑 $g \bmod x^{2n} = g_0 - (fg_0-1)g_0 \bmod x^{2n}$,$\deg((f \bmod x^{2n})g_0) \geq 2n$, 但 $\deg(g_0) < n$ 所以 $\deg((f \bmod x^{2n})g_0) < 3n$ ,因为 $g_0 = g \bmod x^n$ 又有 $fg_0 \bmod x^n = 1$,所以只需要计算 $(f \bmod x^{2n})g \bmod x^{2n} - 1$ 即可。同样计算 $(fg_0-1)g_0 \bmod x^{2n}$ 也只需要长度为 $2n$ 的循环卷积。用时 $(6+o(1))T(n)$。所以计算 $g \bmod x^n$ 所需总时间为 $(6+o(1))T(n)$。

商数或对数

对于 $f, h \in R[[x]]$,令 $g = 1/f, q = hg = h/f$,求 $q$。

直接求 $g$ 再求卷积所需总时间为 $(9+o(1))T(n)$。如果不需要计算出 $g$ 并使用混合基 FFT,有稍微快一些的方法,考虑在求倒数的最后一次迭代中乘 $h$。

$$ \begin{aligned} q \bmod x^{2n} = hg \bmod x^{2n} &= h(g_0 - (fg_0-1)g_0) \bmod x^{2n} \\ &= h((1-(fg_0-1))g_0 \bmod x^{2n} \\ &= (h-h(fg_0-1))g_0 \bmod x^{2n} \end{aligned} $$

再次注意到 $fg_0-1 \bmod x^n = 0$ ,所以 $h$ 的精度只需要达到 $n$。 $$ \begin{aligned} q \bmod x^{2n} &= (h-(h \bmod x^n)(fg_0-1))g_0 \bmod x^{2n} \end{aligned} $$

这样需要计算 2 次长度为 $2n$ 的循环卷积和 1 次长度为 $3n$ 的卷积,用时 $(10.5+o(1))T(n)$。计算 $hg \bmod x^{2n}$ 所需总时间为 $(16.5+o(1))T(n)$,所以计算 $q = hg \bmod x^n$ 所需总时间为 $(8.25+o(1))T(n)$。

平方根

对于 $f \in R[[x]]$,令 $g = f^{1/2}, h = 1/g = f^{-1/2}$,求 $g$。

类似地,考虑 $g \bmod x^{2n} = g_0 - (g_0^2-f)h_0/2 \bmod x^{2n}$。计算 $g_0^2$ 需要 1 次长度为 $n$ 的循环卷积,计算 $(g_0^2-f)h_0$ 需要 1 次长度为 $2n$ 的循环卷积,计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代,用时 $(10.5+o(1))T(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $(10.5+o(1))T(n)$ ,如果不需要计算 $h$,可以省略最后一次迭代中的相关计算,总时间为 $(7.5+o(1))T(n)$。

指数

对于常数项为 $0$ 的 $f \in R[[x]]$,令 $g = \exp f, h = 1/g = 1/\exp f$,求 $g$。

首先需要改写迭代式,令 $f_0 = f \bmod x^n$。 $$ \begin{aligned} g \bmod x^{2n} &= g_0 - (\smallint{({g_0}'/g_0)}-f)g_0 \bmod x^{2n} \\ &= g_0 - g_0\smallint{({g_0}'/g_0-f')} \bmod x^{2n} \\ &= g_0 - g_0\smallint{((g_0h_0)({g_0}'/g_0-f'))} \bmod x^{2n} \\ &= g_0 - g_0\smallint{((g_0h_0){g_0}'/g_0-(g_0h_0)f')} \bmod x^{2n} \\ &= g_0 - g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')} \bmod x^{2n} \end{aligned} $$

计算 $g_0h_0$ 和 ${g_0}'h_0$ 需要 2 次长度为 $n$ 的循环卷积,计算 $(g_0h_0-1){f_0}'$ 和 $g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')}$ 需要 2 次长度为 $2n$ 的循环卷积,所以从 $g \bmod x^n, h \bmod x^n$ 计算 $g \bmod x^{2n}$ 用时 $(9+o(1))T(n)$。计算 $h \bmod x^{2n}$ 需要 1 次计算倒数的迭代,所以总时间为 $(15+o(1))T(n)$。如果不需要计算 $h$ ,可以省略最后一次迭代中的相关计算,总时间为 $(12+o(1))T(n)$。


显然,上面的做法还有很大的优化空间,没必要每次计算循环卷积都计算 2 遍 DFT 再计算 1 遍 IDFT。

倒数

对于 $f \in R[[x]]$,令 $g = 1/f$,求 $g$。 $$ g \bmod x^{2n} = g_0 - (fg_0-1)g_0 \bmod x^{2n} $$

迭代中有两次和 $g_0$ 相关的长度为 $2n$ 的循环卷积,可以记录下 $\mathcal F_{2n}(g_0)$ 而不是重新计算一遍。总时间为 $(5+o(1))T(n)$,是乘法的 $1\frac23$ 倍。

商数或对数

对于 $f, h \in R[[x]]$,令 $g = 1/f, q = hg = h/f$,求 $q$。

令 $g_0 = g \bmod x^n, g_1 = (g \bmod x^{2n} - g_0) / x^n, h_0 = h \bmod x^n, h_1 = (h \bmod x^{2n} - h_0) / x^n$。

如果需要求 $g$,考虑计算 $$ q \bmod x^{2n} = (g \bmod x^{2n})(h \bmod x^{2n}) \bmod x^{2n} = g_0h_0 + (g_0h_1 + g_1h_0)x^n \bmod x^{2n} $$

计算 $g_0, g_1$ 和中间结果 $\mathcal F_{2n}(g_0)$ 需要 $(10+o(1))T(n)$ 时间,计算 $\mathcal F_{2n}(g_1), \mathcal F_{2n}(h_0), \mathcal F_{2n}(h_1)$ 需要 $(3+o(1))T(n)$ 时间,计算 $g_0h_0, g_0h_1 + g_1h_0$ 需要 $(2+o(1))T(n)$ 时间,所以计算 $g \bmod x^{2n}, q \bmod x^{2n}$ 总时间为 $(15+o(1))T(n)$,计算 $g \bmod x^n, q \bmod x^n$ 总时间为 $(7.5+o(1))T(n)$,是乘法的 $2\frac12$ 倍。

如果不需要求 $g$,那么考虑计算 $$ q \bmod x^{2n} = h(1-(fg_0-1))g_0 \bmod x^{2n} $$

令 $\epsilon_1 = (fg_0-1) / x^n$ $$ \begin{aligned} q \bmod x^{2n} &= h(1-\epsilon_1x^n)g_0 \bmod x^{2n} \\ &= (h_0+h_1x^n)(1-\epsilon_1x^n)g_0 \bmod x^{2n} \\ &= (h_0+(h_1-h_0\epsilon_1)x^n)g_0 \bmod x^{2n} \\ &= h_0g_0+(h_1-h_0\epsilon_1)g_0x^n \bmod x^{2n} \end{aligned} $$

计算 $g_0$ 需要 $(5+o(1))T(n)$ 时间,计算 $\mathcal F_{2n}(g_0), \epsilon_1$ 需要 $(3+o(1))T(n)$ 时间,计算 $\mathcal F_{2n}(h_0), \mathcal F_{2n}(\epsilon_1)$ 需要 $(2+o(1))T(n)$ 时间,计算 $h_0g_0, h_0\epsilon_1$ 需要 $(2+o(1))T(n)$ 时间,计算 $(h_1-h_0\epsilon_1)g_0 \bmod x^{2n} - 1$ 需要 $(2+o(1))T(n)$ 时间,所以计算 $q \bmod x^{2n}$ 总时间为 $(14+o(1))T(n)$,计算 $q \bmod x^n$ 总时间为 $(7+o(1))T(n)$,是乘法的 $2\frac13$ 倍。

平方根

对于 $f \in R[[x]]$,令 $g = f^{1/2}, h = 1/g = f^{-1/2}$,求 $g$。 $$ g \bmod x^{2n} = g_0 - (g_0^2-f)h_0/2 \bmod x^{2n} $$

保留前一轮迭代计算的 $\mathcal F_{n}(g_0)$,这样只需要 $(0.5+o(1))T(n)$ 时间即可得到 $g_0^2$,计算乘法时用到的 $\mathcal F_{2n}(h_0)$ 可以保留用于计算倒数,用时 $(7.5+o(1))T(n)$。所以计算 $g \bmod x^n, h \bmod x^n$ 所需总时间为 $(7.5+o(1))T(n)$ ,如果不需要计算 $h$,可以省略最后一次迭代中的相关计算,总时间为 $(5.5+o(1))T(n)$,是乘法的 $1\frac56$ 倍。

指数

对于常数项为 $0$ 的 $f \in R[[x]]$,令 $g = \exp f, h = 1/g = 1/\exp f$,求 $g$。 $$ g \bmod x^{2n} = g_0 - g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')} \bmod x^{2n} $$

这里会用到一个技巧,已知 $f \bmod x^{2n} + 1$ 和 $\mathcal F_{2n}(f)$ 用 $T(n)$ 时间计算 $\mathcal F_{4n}(f)$,这只需要计算一次 DFT。也可以实现成直接计算 $\mathcal F_{4n}(f)$,然后能轻松得到 $\mathcal F_{2n}(f)$。

保留前一轮迭代计算的 $\mathcal F_{n}(g_0)$。计算 $\mathcal F_{n}(h_0), \mathcal F_{2n}(h_0)$ 需要 $(1+o(1))T(n)$ 时间,计算 $g_0h_0$ 需要 $(0.5+o(1))T(n)$ 时间,计算 ${g_0}’h_0 \bmod x^n - 1$ 需要 $(1+o(1))T(n)$ 时间,已知 $\mathcal F_{n}(g_0)$ 计算 $\mathcal F_{2n}(g_0)$ 需要 $(0.5+o(1))T(n)$ 时间,计算 $(g_0h_0 - 1){f_0}' \bmod x^{2n} - 1$ 需要 $(3+o(1))T(n)$ 时间,计算 $g_0\smallint{({g_0}'h_0-f'-(g_0h_0-1){f_0}')} \bmod x^{2n} - 1$ 需要 $(2+o(1))T(n)$ 时间,计算 $\mathcal F_{2n}(g \bmod x^{2n}), h \bmod x^{2n}$ 需要 1 次计算倒数的迭代,注意到 $\mathcal F_{2n}(h_0)$ 已算出,所以总时间为 $(12+o(1))T(n)$。如果不需要计算 $h$ ,可以省略最后一次迭代中的相关计算,总时间为 $(10+o(1))T(n)$,是乘法的 $3\frac13$ 倍。


上面的一些计算仍然有优化空间(更精细地处理 DFT 相关计算),但会使做法变得非常复杂(上面这些已经相对比较复杂了……),$o(1)$ 部分也会变得很大。如果有兴趣的话,似乎可以在这些地方找到进一步优化的办法和一些其他优化方法?

Removing redundancy in high-precision Newton iteration

Newton's method and FFT trading

Faster algorithms for the square root and reciprocal of power series

Faster exponentials of power series

Top trees用于仙人掌?O(log n)时间?带link和cut的QCACTUS?。。。

2017-12-31 23:53:07 By negiizhao

//为防止误解,还是声明一下。。下面标引用的东西是照着某著名slide写的(

某动态的超仙人掌???

总是有出题人喜欢把序列上用线段树解决的题目出到树上,让选手强行写个树链剖分或树分治或某种动态树数据结构。

这种行为已经很无趣了。

所以我们想让大家知道,不光可以放在静态树上,动态仙人掌也是可以的。

以上都是在扯淡。

----------------

先丢个隙间吧..补完某些东西再把copy过来..

----------------

希望今天我们讲的东西能够给大家一点启发。

(希望大家不要拿这种东西出题。

(平时玩玩就算了,出到比赛里大概是会被打死的。

Open Problems:

用于仙人掌的worst-case top trees?

能否进一步将top trees推广到其他有特殊性质的图上?

科技小论文?一些奇怪的东西?QTREE系列加上link和cut?。。。

2017-12-21 01:58:29 By negiizhao

emmmmmm...前段时间学校要写个科技小论文。。。

也不知怎么的,莫名就写了个奇怪东西,反正不是论文

大概就是找来一堆论文(主要也就那几个),翻译拼凑一番(参考文献都不需要找了)。。。

把(一部分)动态树数据结构(ET-trees、ST-trees和top trees)粗略介绍了一遍。

顺便说一下,真正的top trees使用姿势可能在11页。。。对应的模板题大概是QTREE系列加上link和cut。。。

(Alstrup et al.: "Top trees generalize balanced binary search trees!")

(模板题可能还有link cut 找类似重心的东西。。。)

某些词完全就是强行翻译吧!

里面提到了重量平衡树(weight-balanced trees),这东西并不是陈立杰提出的那个。。。

并不知道他为什么要起这个名。。。不可能没有听说过weight-balanced trees。

由于ddl,很多东西就没详细说了。。。

比如self-adjusting top trees究竟是怎样的东西。

实际速度测试及对比可以看Dynamic Trees in Practice。。。

先把一些“大问题”讲清楚吧?

废话也就不多说了。。。这里是隙间。。。

最后那里赶ddl的痕迹很明显。。。很多东西都没说清楚,也懒得写了,改了title部分就丢了上来。

那个slide是论文答辩用的。。。也是赶的。。。明显少了一些东西,图没有对齐,连\pause都没加。。。

其实嘛,还考虑了一些相关的东西,但短期内不一定有时间写。

共 4 篇博客