多叉线段树

考虑这么一个东西： $O(n)$ 次区间查询 $\max$ ， $O(n\log n)$ 次单点加正数。

如果直接线段树，那么复杂度是 $O(n\log^2 n)$ 的。

还可以分块，但是这里修改和查询的差没有那么离谱，做到 $O(n\sqrt n)$ 还是比较不牛。

我们把线段树魔改一下，改成 $\log$ 叉的，这样线段树的树高变成了 $\log_{\log n}n=\dfrac{\log n}{\log \log n}$ 。

考虑单点修改，我们提前预处理好每个位置的对应到线段树的那个叶子，然后不断跳父亲，这里每个节点的信息可以直接被更新，不用 pushup，因此这样复杂度是只跟树高有关也就是 $O(\frac{\log n}{\log \log n})$ 的，那么修改的总复杂度就是， $O(\frac{n\log^2 n}{\log \log n})$ 。

再考虑查询，可以分析出暴力查询会访问到的节点个树是叉数乘上树高乘上一个常数，也就是单次 $O(\frac{\log^2 n}{\log \log n})$ ，总复杂度也是 $O(\frac{n\log^2 n}{\log \log n})$ 。

这样子总复杂度就是 $O(\frac{n\log^2 n}{\log \log n})$ 。

不过感受一下，修改的常数比查询小很多，所以可以把叉数开小一些应该会更快（？

同理 $O(n)$ 次区间修改 $O(n\log n)$ 次单点查询也可以类似的干法。

这里我们利用了线段树查询单点的性质加速了整个过程，其实要求严格树高的处理一个单点比较困难，如果线段树要 pushup 或者 pushdown 就图图了，所以只能依赖直接更新信息以及标记永久化（当然也坑能我太菜了）。

本文作者：World Creater

本文链接：http://worldcreaterwc.github.io/logsegtree/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

线段树

最后更新：2024-12-19, 03:18:27

上一页下一页

By World Creater.