朝花夕拾

写一个以前不知道在晕晕乎乎写些啥的算法。

我本人介绍本篇文章涉及到的算法的第一次是 2024.2.24，然后大概在 2024.7~8 月左右搬到了 CF，然后在算法非原创+英语超级烂+讲的很多错的情况下获得了 64 upvotes，我也不知道为什么。2025.6 左右我已经想写这篇文章，但是没有动手。

本文考虑过不写分块和 Sqrt Tree，但是后来有感觉算了。

本文的算法都能用二进制优化做到询问 O(1)，但是我不是很想写具体的优化方法。

本文阅读逻辑：

2->4->6->7 主线任务。

1->3->5 支线任务。

8 附加任务。

从这里开始数是第一节。

本文的起点是分块。

预处理块间信息，块内信息可以做到 O(n\sqrt{n}) 预处理。

第二节，猫树。

建出一个类似线段树的结构，预处理每一段的前缀和后缀，询问的时候找到第一个跨线层（即一个结点和他的兄弟都包含询问区间的一部分）然后就直接做就行了。O(n\log n)。

从这里其实能初见树状结构的端倪了，不过由于还是线段树型，对这个不是很敏感。

分 k 层的复杂度为 \frac{kn^2}{2^k}。

第三节，Sqrt Tree。

我们考虑一个这样的结构：对 \sqrt{n} 分块，对每一个 \sqrt{n} 的小块再对 \sqrt[4]{n} 分块，以此类推，第 k 层对 \sqrt[2^k]{n} 分块。

同样对于每一个预处理前缀后缀和块间，然后找到第一个跨线层也可以做了。O(n\log\log n)。

分 k 层的复杂度为 kn^{1+\frac{1}{2^k}}。

第四节。

不知道该叫啥，如果真的要叫的话就四区间合并吧。

每层关于 \log n 分块，找到第一个跨线层用猫树维护。O(n\log^*n)。

分 k 层的复杂度为 O(kn\log^{(k)}n)。

第五节。

试图对 \log\log 分块然后用 Sqrt Tree,显然失败了，复杂度还是 \log^*。

第六节。

在第四节的基础上再画一层树结构，变成 O(n\log^{**}n)。

第七节。

画 \alpha(n) 层就是 n\alpha(n) 了。

第八节。

这块由于讲的错误太多，具有误导性，在 2025.12.15 被删掉了。