从理解斜二倍增，到放弃斜二倍增

· · 算法·理论

::::warning[严正声明]{open} 对于梦熊联盟，以及其实际控制人和主要管理人员实际控制的其它机构，禁止任何人于正在临时或长期参与其任何活动期间，以任何直接或间接方式转载，引用，使用，传播或展示：本人在2024年5月或以后创作的任何内容或片段，包括所有声明为公开发表的内容在内！学生或教师本人自行阅读学习为被允许的例外情况，但此授权不包括在上述实体活动期间在其平台上进行转载，引用，传播等。 ::::

公开资源推荐和征集：

什么是斜二倍增？我看不懂斜二倍增怎么办？

问题： 我有一棵有根树，想支持在线动态 O(1) 加叶子，在线 O(\log n) 查询路径可合并信息（比如路径最大值个数，路径最大子段和），内存 O(n)，怎么办？

在下文中，为了简便，我们设定：查询的信息基于点权而非边权。

传统解法：

  1. 直接上LCT：但是难写且常数大。
  2. 树剖：因为动态加点得随机选重儿子，但是如果数据不随机又得上平衡调整，然后你发现自己发明了LCT。
  3. 每 \log n 层树分块/取关键点：这思路能做，但还是没那么好写。
  4. 树上倍增：好写好用，但是每个点要 O(\log n) 预处理，怎么办？

我们考虑怎么优化树上倍增。树上倍增预处理的信息总共 O(n\log n) 个，这很有用，但是做路径查询其实不需要这么多。你看线段树，树剖+线段树都是 O(n) 空间就能做路径查询了。能不能对倍增也这么干？

尝试直接让线段树上树。方便起见，我们取完美线段树（区间长度都恰好是 2 的幂）：我们对于树上每个到根路径，把它当成一个深度为下标的序列，预处理出线段树上所有应该有的点。

也就是说，对于每个树上的点 u，设它的深度为 d(u)，那么：线段树上每有一个以 d(u) 为右端点的长度 L 的区间，我们就预处理从 u 向上 L 个点的路径段信息。（深度从 1 开始算）

可以发现，这等于：对于每个点 u，我们处理了向上长度 2^1,2^2,\dots ,2^{\mathrm{lowbit}(d(u))} 的所有区间。也就是我们对树上倍增添加一个上限 2^{\mathrm{lowbit}(d(u))}。我们可以像线段树那样，查询每个点到根路径的任意区间，那么仍然可以 O(\log n) 查找LCA以及求路径可合并信息。

这样，我们已经把树上倍增几乎变成线段树的 O(n) 复杂度。

但还有一个小问题：线段树虽然总复杂度是 O(n) 的，但是单个位置为右端点的区间数仍然可以达到 O(\log n)。那么树上这种深度的节点很多时复杂度还是会退化到 O(n\log n)。如果能把线段树每个区间右端点变成互不相等的，就能解决这个问题。

斜二倍增

这其实很简单：我们把每个线段树区间的定义从两个子树区间的并，改成：两个子树区间的并后面再多加一个点。也就是形如：

这个线段树称为斜二进制线段树。这样每个点存的区间数都变成了严格的 1 个，而且仍然可以线段树查询（只是每一层要多合并一个单点）。具体来说：设 L(x) 表示以 x 为右端点的斜二进制线段树区间长度（上图橙色数字），则对于每个树上的点 u，设它的深度为 d(u)，我们预处理从 u 开始向上长度为 L(d(u)) 的路径段信息即可。L 数组倍增预处理即可。

之后的用法就和普通倍增一样，具体代码可以参考介绍博客 - UT。

我不想学斜二倍增！普通倍增能代替吗？

其实可以，直接按前文所述对倍增添加一个上限 2^{\mathrm{lowbit}(d)}即可。此处 d 是倍增起点的深度或下标。

那么怎么解决同深度点太多时复杂度不对的问题呢？

方法一. 如果问题可以换根，可以先遍历树找一个好的根，总存在一个根使得每个点深度的 \mathrm{lowbit} 位数和是 O(n) 的。

证明和构造思路：考虑对树进行黑白染色，取黑/白根时所有同色（或者异色，看深度定义）点的深度全为奇数。所以递归到较小颜色为偶数的情况里选取，然后继续递归即可。

方法二. 这个更简单，而且通用：我们一开始均匀随机选取一个全局的 [1,2^{\lceil \log n \rceil}] 正整数常数 C，然后我们定义 \mathrm{lowbit'}(x)=\mathrm{lowbit}(x+C)，改用 \mathrm{lowbit'} 做倍增上限即可。

证明思路：这相当于把所有下标和线段树区间整体平移了一下，容易发现不影响线段树的复杂度。但这会让每个点 \pmod{2^{\lceil \log n \rceil}} 都变成均匀随机的，而均匀随机整数的 \mathrm{lowbit} 期望（平均）等于 1。所以期望复杂度正确。

缺点：倍增数组不定长，内存分配可能是个问题。不过出题人不刻意卡的话 vector 即可。卡就手动分一下。

因为本来就差不多（随机化和确定性的区别）目前可以完全代替斜二倍增，适合不想学新代码的选手。

题外话：对于有些问题倍增 O(n\log n) 个信息是必要的。比如树上求两个路径的最长公共前缀二分哈希时，必须要任意两个点都能走相同长度。

我普通倍增也不想学了

树分块：每 \log n 层树分块/取关键点，关键点个数是 O(n/\log n) 然后关键点之间跑带 \log 的算法，查询的时候暴力跑到第一个关键点即可。

代码

随机偏移倍增（方法二）求 LCA 的核心代码（我写的比较繁杂，可以根据你自己的倍增代码修改）：

和普通倍增唯一区别是倍增步数取了个 \min。

int L(int x){return __builtin_ctz(x+C);} // lowbit位数。其中C是全局预处理常数，在O(n)值域随机的一个正整数
int B(int x){return 31-__builtin_clz(x);} // 二进制最高位数
// dep：深度 f[i][j]：i的2^j级祖先，其中j<=min(B(dep[i]),L(dep[i]))
int lca(int u, int v){
    if(dep[u]<dep[v])swap(u,v);
    int dd=dep[u]-dep[v];
    while(dd){ // 跳到dep[u]==dep[v]
        int di=min(L(dep[u]),B(dd));
        u=fa[u][di], dd-=(1<<di);
    }
    for(int i=B(dep[u]);i>=0;){
        int di=min(min(B(dep[u]),L(dep[u])),i);
        if(fa[u][di]==fa[v][di])
            i=min(i,di-1); // 不用再尝试>=di的了
        else
            u=fa[u][di], v=fa[v][di];
    }
    if(u!=v)u=fa[u][0],v=fa[v][0];
    return u;
}

坚决反对与虎谋皮，以营销炒作的方式“推广知识”，破坏社区秩序的行为！

坚决反对通过向部分不懂算法的家长/教练危言耸听，吹嘘特定知识重要性，强迫学生学习，破坏教学秩序的行为！

坚决支持建设高质量公开资料推荐平台和日报刊物平台！

对于梦熊联盟，以及其实际控制人和主要管理人员实际控制的其它机构，禁止任何人于正在临时或长期参与其任何活动期间，以任何直接或间接方式转载，引用，使用，传播或展示：本人在2024年5月或以后创作的任何内容或片段，包括所有声明为公开发表的内容在内！学生或教师本人自行阅读学习为被允许的例外情况，但此授权不包括在上述实体活动期间在其平台上进行转载，引用，传播等。