？链剖分

· · 休闲·娱乐

事情的起因是我看到了这个帖子，然后突发奇想：能不能自己创造一些树链剖分呢？

放上来的都是通过了【模板】树链剖分的方式。

声明：以下若有雷同纯属巧合。

自适应轻链剖分

在选重儿子时，若重儿子大小超过了一半，则选重儿子，否则选最轻的儿子。

这种树链剖分的时间复杂度证明和普通重链剖分的证明一样，都是跳一次轻链树的大小至少 \times2，因此也是 \log n 的，考场上放心用。

随机大小剖分

对于非叶子节点 x 每个儿子 y 有 \frac{siz_y}{siz_x-1} 的概率成为重儿子，且恰好有一个成为重儿子。

这种做法的期望是不超过 \ln n 的。

:::info[证明]

前置知识：

\forall t>0,\ln t\le t-1\\ \ln a-\ln b=\ln\frac ab

还有裂项相消。

一个点 y 到父亲 x 的边是轻边的概率是

1-\frac{siz_y}{siz_x-1}\le-\ln\frac{siz_y}{siz_x-1}=\ln\frac{siz_x-1}{siz_y}\le\ln\frac{siz_x}{siz_y}

因此从 s 跳到根节点的期望轻边数量是

\sum \ln\frac{siz_x}{siz_y}=\sum \ln siz_x-ln siz_y=\ln\frac{siz_{rt}}{siz_s}\le\ln n

:::

所以这个东西似乎比最坏 \log n 的树剖快？

事实证明这种树链剖分在卡重链剖分的【模板】动态 DP（加强版）比重链剖分快。随机大小剖分 重链剖分

一般情况下也不比重链剖分太劣。

考场上随便用。

平均大小剖分

选重儿子时选子树内所有节点子树大小的平均值的儿子。

这种做法时间复杂度最坏为 \sqrt n，不过在一般情况下速度堪比普通重链剖分。

:::info[证明] 令

all_x=\sum_{y\in subtree_x}siz_y,\qquad ave_x=\frac{all_x}{siz_x}.

设一条从某个节点到根经过的轻边的儿子是 v_1,v_2,\dots,v_k，即 (v_i,fa_{v_i}) 是轻边。

记

m_i=siz_{v_i},\qquad a_i=ave_{v_i}.

设 s_i=son_{fa_{v_i}}，因为 v_i 是轻儿子，按“平均大小”选重儿子，所以

ave_{s_i}\ge ave_{v_i}.

又因为一定有

ave_x\le\frac{siz_x+1}{2},

所以

siz_{s_i}\ge 2ave_{s_i}-1\ge 2ave_{v_i}-1,

于是

siz_{fa_{v_i}} \ge siz_{s_i}+siz_{v_i}+1 \ge siz_{v_i}+2ave_{v_i}. \tag{1}

因为 v_{i+1} 是 fa_{v_i} 的祖先，所以 siz_{v_{i+1}}\ge siz_{fa_{v_i}}，结合 (1) 得

m_{i+1}\ge m_i+2a_i. \tag{2}

显然 v_1,v_2,\dots,v_i 都在 v_i 子树内，所以

all_{v_i}\ge\sum_{j=1}^isiz_{v_j}=\sum_{j=1}^im_j,

因此

a_i=\frac{all_{v_i}}{m_i}\ge\frac{\sum_{j=1}^im_j}{m_i}. \tag{3}

下面归纳证明：存在常数 c>0，使得只要 m_i\le i^2，就有

m_i\ge ci^2.

当 i=1 时 m_1\ge1，显然 m_1\ge c。

假设对 j<i 已有 m_j\ge cj^2。若 m_i\le i^2，由 (3) 得

a_i\ge\frac{\sum_{j=1}^{i-1}m_j}{m_i} \ge\frac{c\sum_{j=1}^{i-1}j^2}{i^2} =\Omega(i).

因此存在常数 c'>0，使得

a_i\ge c'i.

由 (2) 得

m_{i+1}\ge m_i+2c'i.

取 c 足够小，结合归纳假设 m_i\ge ci^2，可使

m_i+2c'i\ge c(i+1)^2.

于是 m_{i+1}\ge c(i+1)^2，归纳成立。

因此：

综上，对每个 i 都有

i=O(\sqrt n).
因此轻边总数 k=O(\sqrt n)，即跳的轻链次数是 \sqrt n 级别的。

考场上小心用。