fzs 线段树

fzs7

2024-11-06 20:28:44

Life & Travel

fzs 线段树,顾名思义,就是本人在 CSP-2024 考场上发明的神秘线段树,这是一种神秘的数据结构,可以帮助我们大大劣化我们代码的时间复杂度。

众所周知,线段树单点加的时候会加一条从叶子到根的链,这种链加问题启发我们对线段树进行一个树链剖分,然后就可以在 O(\log^2 n) 的时间内进行一次单点加。

区间加怎么做呢?暂时没有想到,那就在区间内每一个点进行一次单点加就好了。

综上,区间加的时间复杂度是 O(n \log^2 n) 的。

考虑查询,只要按正常线段树的查询即可,由于在剖分的那一棵树上单点查是 O(\log n) 的,所以在原树上查点的时候时间复杂度也要乘上 \log n,这样一来,区间查询的时间复杂度就是 O(\log^2 n)

这样,我们就实现了一棵区间加 O(n \log^2 n),区间查询 O(\log^2 n),我们将它称为二次 fzs 线段树,记作 fzxds^2,特别的,我们将朴素的线段树称为一次 fzs 线段树,记作 fzxds^1

考虑到树剖后的那一棵线段树还是朴素的,所以可以用 fzxds^2 来替代,将其称为 fzxds^3,注意到对于 fzxds^n(n \in N^+) 总有一棵线段树是朴素的,所以总可以用 fzxds^2 来替代,而且可以用任意的 fzxds^n 来替代,设这个合并过程为加法,还满足 fzxds^n+fzxds^m=fzxds^{n+m},这个性质可以使得我们极其容易地劣化我们代码的时间复杂度。

一些实现更加精细的 fzsds 可以实现 fzsds^{+\infin},时间复杂度可以达到惊人的 O(n\lim\limits_{x→ +\infin}\log^{x}n),可以为劣化时间复杂度起到更优秀的作用,可以帮助大家在 CF/AT/Luogu 上快速下分。