【详细介绍】一种基于 zkw 线段树的区间查询刻画

· · 个人记录

大概是系列相关 trick 的整合。默认读者已经掌握了 zkw 线段树。

考察 zkw 线段树的查询结构（左闭右开 0-index 区间）：先将 l 加上 M，再将 r 加上 M+1，随后重复以下流程直到 l 与 r 成为兄弟，每次结束后将 l 与 r 减半：若 l 为偶数则将其兄弟置入贡献节点左序列的末端，若 r 为奇数则将其兄弟置于贡献节点右序列的首段。最后拼接左右贡献序列，我们即按序得到了所有的贡献节点，将其从左至右累计贡献即可。如果写过 zkw 线段树的代码，这段应当不难理解。

不难注意到，zkw 线段树堆式存储的特性为我们带来了另一条优秀性质：叶子 l 与叶子 r（保证其不相同且不为兄弟）的 lca 的两个儿子分别为 l>>__lg(l^r) 与 r>>__lg(l^r)，且这两个节点是兄弟。证明就是考虑这俩的 lcp 之后的长度是 __lg(l^r)。我们同时考虑，对于同一个节点作为路径上的 l 或 r 存在，它能造成的贡献各自是固定的。以 l 为例，若这个节点编号是奇数则没有贡献，否则是其兄弟的值。于是我们把一个节点的两种贡献打包成一个 pair（注意两项转移顺序一正一反），然后问题转化为线段树上叶子到某个已知的祖先（不含）的路径查查询。

于是我们现在要解决的就是一棵满二叉树上从叶子开始的祖先-后代链查询问题。然后我们可以搞出一吨算法，这里简单列举一些（将叶子数量定义为 n，它一定是一个二的幂）：

  1. 暴力查询。

优势是修改影响到的元素很少，两个操作都是 O(\log n)。

等价于线段树。这个例子是为了让读者更好理解而存在的。

  1. 暴力前缀和。

修改的时候会影响到 O(1+2+4+\cdots+n)=O(n) 个点，但查询的时候可以直接查维护好的前缀和了，是 O(1)，这很棒。预处理需要一个额外的 O(n\log n)。

等价于猫树。

  1. 按高度分段

我们把深度为全局高度一半的点拿出来作为一层并据此切割，这样树就被切割成了 O(\sqrt n) 个大小为 O(\sqrt n) 的联通块。修改的时候只修改涉及到的不超过 3 个块，查询的时候一条链至多在两层里各占一段，这样修改是 O(\sqrt n) 查询是 O(1)，预处理需要一个额外的 O(n\log n)。事实上，改成多层分块可以把修改搞成 O(n^\epsilon)。

等价于分块套猫树。

  1. 树上倍增

具体算法过于简单不多赘述。预处理复杂度 O(n\log\log n) 查询 O(\log\log n)。如果用一些斜二进制的相关技巧改装一下，可以把预处理复杂度和空间搞到线性。不支持修改。

从这里开始没有简单等价。

  1. 长链剖分

其实不是那么长剖，但类似。我们定义一个点的高度是它到叶子的路径上的点数（这个概念后面会多次用到）。我们维护一个点向上高度个祖先中对每一个的路径查询结果。查询的时候倍增跳一步然后交给长剖就行，注意这里不能换斜二。预处理 O(n\log\log n) 查询 O(1)。复杂度的依据是每个点高度和是线性的，读者自证不难。

  1. 按高度分段 promax

我们对高度进行某种分块手段使每一层的前缀和状态数依次减半。假设底层高度是 h，那么倒数第二层点数就是 O(\frac nh)，那么高度应该是 O(\frac{h\times 2^h}2)。于是我们一共有 O(\log^*n) 层，总状态数 O(n)。前者是查询复杂度，后者是预处理复杂度。

可以对每个叶子块间累前缀和。预处理换查询。

  1. 并查集

直接离线把询问挂到节点上然后开带权并查集。每个点的秩锁定为 \lceil\frac mn\rceil 加高度，可以证明复杂度是一个 \alpha 的。实现上单路压就行。

也可以看 https://return20071007.blog.uoj.ac/blog/9292。

  1. 阿克曼（达到复杂度下界）

https://return20071007.blog.uoj.ac/blog/9298。

  1. 上树。

可以直接走 GBST 然后类似刻画，但细节很多。另一种写法是开剖（每个点连边到链顶的爹，链间相关复杂度分析和线段树类似），然后开一个全局线段树应付链内。

复杂度不变。

以上。如果后面还发现什么东西可能会在这里加。