Old Driver Tree (ODT)，又称珂朵莉树，是源于 lxl 出的「CF 896C」的，对一类以推平区间作为关键操作的维护数列方法。
原理很简单：使用一棵平衡树（大多数情况下为std::set），每个节点存储一段权值相等的极长区间。
一些操作
下述时间复杂度时， $n$ 表示平衡树中的节点数量（即序列中权值相等的极长区间数量）。
split
将某一个权值相等的区间分裂成两个，要求 $pos$ 为后一个的左端点。
在平衡树中找到跨过 $pos$ 的区间，删除并添加新区间即可。复杂度稳定 $O(\log_2{n})$ 。
assgin
将区间 $[l,r]$ 推平。
先把 $l$ 和 $r + 1$ 进行 split 操作，再把 $[l,r]$ 合成一个节点。
注意要先 split $r+1$ 再 split $l$ 。
单次复杂度最坏 $O(n)$ 。
其他操作
在平衡树上遍历节点即可。
复杂度的证明
假设在数据真随机的情况下，开始时有 $n$ 个长为 $1$ 的区间，接下来有 $k$ 个区间推平操作。
考虑一次推平操作后，点 $i$ 作为一个权值相等的极长区间的结尾的可能性为:
$$1 - \dfrac{i + \binom{i - 1}{2} + \binom{n - i}{2}}{\binom{n}{2}} = 1 - \dfrac{2i(n - i - 1)}{n(n - 1)} \approx \left(\dfrac{i}{n}\right)^2 + \left(1 - \dfrac{i}{n}\right)^2$$
假设这 $k$ 次区间推平是独立的，那么 $k$ 次推平后点 $i$ 作为一个权值相等的极长区间的结尾的可能性约为 $((\frac{i}{n})^2 + (1 - \frac{i}{n})^2)^k$ 。
所以总的权值相等的极长区间的总数即约为 $\sum\limits_{i=1}^{n}((\frac{i}{n})^2 + (1 - \frac{i}{n})^2)^k\approx n\int_0^1 (x^2 + (1 - x)^2)^k \mathrm{d}x$ 。
$$\begin{aligned}
& n\int_0^1 (x^2 + (1 - x)^2)^k \mathrm{d}x \\
=\ & n \int_{-1/2}^{1/2} ((\frac{1}{2} + x)^2 + (\frac{1}{2} - x)^2)^k \mathrm{d}x \\
=\ & n \int_{-1/2}^{1/2} (\frac{1}{2} + 2x^2)^k \mathrm{d}x \\
=\ & n\cdot 2^{-k} \int_{-1/2}^{1/2} (1 + 4x^2)^k \mathrm{d}x \\
=\ & n\cdot 2^{-k} \sum\limits_{i=0}^{k} \binom{k}{i}\cdot 4^i \int_{-1/2}^{1/2} x^{2i} \mathrm{d}x \\
=\ & n\cdot 2^{-k} \sum\limits_{i=0}^{k} \binom{k}{i}\cdot 4^i\cdot \frac{(1/2)^{2i+1} - (-1/2)^{2i+1}}{2i+1} \\
=\ & n\cdot 2^{-k} \sum\limits_{i=0}^{k} \binom{k}{i} \frac{1}{2i + 1} \\
\le\ & n\cdot 2^{-k} \sum\limits_{i=0}^{k} \binom{k}{i} \frac{1}{i + 1} \\
=\ & n\cdot 2^{-k} \cdot \frac{2^{k+1} - 1}{k + 1} \\
=\ & O(\frac{n}{k})
\end{aligned}$$
所以，最坏情况下 $k$ 次区间推平的复杂度是 $O(n\log_2k)$ 。
lxl的题解，Akababa的原证明。另外，Blaze也给出了一种证明方法。
代码实现及例题
「CF 896C」Willem, Chtholly and Seniorious
例题。
维护长为 $n$ 的序列， $m$ 个操作，可能为区间加、区间推平、区间查询第 $k$ 小，区间查询 $(\sum_{i=l}^{r} a_i^x)\mod y$ 。
$1\le n,m\le 10^5$ ，数据随机生成。
思路
直接上 ODT 即可。
由于要区间加，记得节点开 $mutable$ 。
1 |
|
「CometOJ contest#14 D」转转的数据结构题
一个长为 $m$ 的整数序列 $c$ ，初值全为 $0$ ；一个长为 $n$ 的操作序列，第 $i$ 个用三元组 $(l_i, r_i, v_i)$ 描述，代表将 $c_{l_i}, c_{l_i + 1}, c_{l_i + 2}, \cdots, c_{r_i}$ 赋值为 $v_i$ 。
$q$ 个询问，第 $i$ 个有两个参数 $x_i$ , $y_i$ ( $x_i\le y_i$ )，回答对初值全为 $0$ 的空序列 $c$ ，按顺序执行序号位于 $[x_i,y_i]$ 中的操作后， $c$ 中所有整数的和。
$1\le n,m,q\le 5\times 10^5,0\le v_i\le 2\times 10^9$ 。
思路
将询问按照 $y_i$ 排序。使用类似 ODT 的方法来维护 $c$ 序列。
对平衡树上的每个节点存储一个时间戳 $t$ ，即这个节点是由哪次操作产生的。发现询问 $x_i, y_i$ 即为做完前 $y_i$ 个操作后，时间戳不小于 $x_i$ 的节点的和。这可以很容易地使用树状数组维护。
将时间后移（即进行下一个修改）时修改树状数组即可。
考虑这个方法的时间复杂度。每个节点最多只会被删除 $1$ 次。而一个修改在插入 $1$ 个节点的同时最多只会分裂 $2$ 个节点，所以节点的变化次数是 $O(n)$ 的。
所以，虽然这个题的数据不随机，然而时间复杂度是稳定 $O(n\log_2{n})$ 的。
1 |
|