P14302 基础倍增练习题 6 / 小 U 的树 题解 / 斜二进制倍增学习笔记

zrl123456 · 2025-10-29 23:00:58 · 题解

:::::info[题目基本信息] 考察：倍增（省选/NOI-）。
题目简介：
你有 n 个点，它们有点权，初始时它们间没有连边。
你需要进行 m 次操作或查询：

• 操作：给两个不联通的点连边。
• 查询：询问两个连通的点间的路径的点权的最大子段和。

数据范围：

• 数据强制在线。

时间限制：4s。
空间限制：512MB。
::::: 斜二进制倍增模板题（出题人题解）。
先引入斜二进制是什么。
:::::success[斜二进制] 斜二进制是第 i 位表示的数是 2^i-1 的一种进制（当然了尽可能用高位表示）。
容易发现一些性质：

• 每一位只可能出现 0,1 或 2。
• 最多出现 1 个 2。
• 若出现了 2，那么比 2 所在位低的位都为 0。

设函数 \text{skewlowbit}(x) 表示 x 的最低的不为 0 的位。
::::: 下面引入斜二进制倍增：
:::::success[斜二进制倍增] 定义一棵树是通过线段树偏移得到的，每个点都只作为一个区间的右端点，类似 BIT，每个点的区间为 [x-\text{skewlowbit}(x)+1,x]。
令 lb_x=x-\text{skewlowbit}(x)，这样方便我们跳区间，这样我们就可以倍增了。
类似 BIT 一样倍增即可。
::::: 在这个题中，斜二进制倍增要上树，每次新增点的时候选择较小的一个子树进行重构，时间复杂度是启发式合并的 \Theta(n\log n)。
讲的好像有点草率了。细节见代码吧。

时间复杂度为 \Theta(n\log n)。

code