OI-wiki 中的 Kinetic Tournament Tree（KTT）详解：动态维护函数区间最大值

OI-wiki 中的 Kinetic Tournament Tree（KTT）详解：动态维护函数区间最大值

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读

Kinetic Tournament Tree（KTT，动力学竞赛树）是一种将静态算法"动态化"的数据结构，用于维护一组线性函数在区间平移（TranslateLeft）操作下 0 点处区间最大值的动态变化。本文以 OI-wiki 的 kinetic-tournament-tree.md 为骨架，结合仓库内完整参考实现 ktt_1.cpp 与配套测试数据 ktt_1.in / ktt_1.ans，系统讲解 KTT 的证书机制、懒标记实现、势能复杂度分析，以及向高次函数与近似查询的推广。读完本文，你将掌握 KTT 从理论到代码的完整落地链路，并能独立分析其 $O(n\log^2 n + m\log^3 n)$ 的总时间复杂度来源。

前置知识：线段树。建议先掌握线段树的区间划分、堆式存储与懒标记思想，再阅读本文。

问题引入：线性函数序列上的区间平移与最值查询

给定单变量线性函数序列 $F={f_1,\dots,f_n}$，其中 $f_i: \mathbf{R} \rightarrow \mathbf{R}$，且 $f_i(x)=k_ix+b_i$，$k_i,b_i \in \mathbf{R}$。我们需要维护以下两种操作：

• $\operatorname{QueryMax}(l,r)$：给定 $l$ 和 $r$，返回 $\max_{i=l}^{r}{f_i(0)}$。
• $\operatorname{TranslateLeft}(l,r,\delta)$：给定 $l$、$r$ 和 $\delta$，对区间内所有 $i\in[l,r]$ 执行 $f_i(x) \leftarrow f_i(x+\delta)$。该操作等价于 $b_i\leftarrow b_i+k_i\delta$，其中 $\delta > 0$。

为表述方便，本文假定所有函数互不相同。

操作本质：按位置系数加权区间加

一次函数区间向左平移的本质是 $b_i \leftarrow b_i + k_i\cdot \delta$：常数项加上"斜率 $k_i$ 乘以平移量 $\delta$"。若把所有 $f_i(0)=b_i$ 视作序列上的"值"，则该操作等价于在许多数据结构问题中常见的「按位置系数加权区间加」——对于区间 $[l,r]$ 内的每个下标 $i$，给其值加上一个固定的 $\delta$ 乘上该位置特有的系数 $k_i$。

因此，一次函数区间平移在本质上就是按位置系数加权的区间加法。普通线段树难以高效处理这类操作，因为"当前区间最大值来自哪个函数"会随平移不断改变。KTT 正是为这种场景设计的结构——为了展示其独特的二叉树形分治结构，本文直接从区间平移这一操作入手。

Kinetic Data Structures：运动系统的动态维护框架

Kinetic Data Structures（动力学数据结构，简称KDS）用于维护几何对象系统在连续运动过程中的属性。KTT 是其家族成员，其核心思想包含两个关键概念。

事件队列（Event Queue）

我们假设每个"点"都有一个已知的运动计划，它能够提供该点的完整或部分运动信息。例如，函数 $f_i(x)$ 形成的曲线或直线就能很好地描述动点 $i$ 的运动轨迹。运动计划随时可能变化——可能是由于碰撞，或环境交互的原因；造成运动计划更改的原因称为事件。事件队列会按时间顺序给出事件。

KDS 的一个关键方面是：需要拥有容易维护的事件。即事件队列中的事件类型对应于可能的组合变化，这些变化涉及数量恒定且通常较少的物体。例如，在本题的维护中，使用的一种事件类型是「函数 $f_i(0)$ 与函数 $f_j(0)$ 的大小发生变化」。

需要说明的是，事件队列可以隐式维护，即不需要显式建立按时间排序的堆结构，而是通过结构内的代数条件按需触发。

证书（Certificate）

这些事件应当可以等价于通过一系列低阶代数条件的交来保证，每个代数条件都涉及有限数量的对象。我们将这些条件称为 KDS 的证书（certificate）。例如 $[f_i(0) > f_j(0)]$ 就是一个典型的证书：只要它一直成立，由它保证的性质（如"节点维护的最大值来源不变"）就持续有效。

Kinetic Tournament Tree：基本结构与证书机制

Kinetic Tournament Tree（简称KTT）属于 Kinetic Data Structures，首次出现于 1999 年的论文Data Structures for Mobile Data（J. Basch, L. J. Guibas, J. Hershberger），用于维护连续变化的数据。更普遍地，每一个采用如下**动态化策略（kinetization strategy）**的结构都可以称为 Kinetic Tournament：

1. 为静态算法中的关键操作（例如比较）生成正确性证书，并将每个证书与一个全局事件队列关联，记录该证书可能失效的时间点；
2. 当某个证书失效时，能够高效地更新算法输出并维护证书集合。

在算法竞赛社区，它兴起于 2020 年国家集训队论文《浅谈函数最值的动态维护》。学术界的 KTT 与算法竞赛界的 KTT 在应用领域和实现上有所不同，本文介绍的是为算法竞赛进行过优化的 KTT。

结构设计：在线段树上做锦标赛

首先考虑设计一个与线段树结构相似的静态最大值维护结构：将线段树的结构建立出来，对于每个非叶节点，其权值为两个孩子节点中较大的权值。在执行了 $O(n)$ 次比较后，根节点的权值就是全局最大值。

现在权值开始变化（函数随 $\delta$ 平移）。只要 KTT 能探测到每一次"树上点的最大值来源"发生改变，就能维护全局最大值。为此：

• 对树上节点 $x$ 及其左、右儿子提供的函数 $f_L$、$f_R$，定义证书为「$f_L$ 和 $f_R$ 的大小关系保持不变」；
• 当证书失效时，需要通过树上路径走到当前证书失效的节点来更新它的信息；
• 为维护每个证书失效的时间，注意到证书失效的时刻正是两个函数拥有相同值的时刻，问题就变成求两个线性函数的交点横坐标，可在 $O(1)$ 时间内解决。

节点维护的信息与懒标记

每个树上节点维护：

• 在 $0$ 处取到最大值的函数（即当前"胜者"）；
• 当前证书失效的时间；
• 整个子树内最早失效证书的失效时间。

这样，当某个节点证书失效的时刻到来时，就能在该时刻找到它并更新信息。

区间平移操作可以简单累加，因此使用懒标记处理：

• 定义懒标记 $\Delta_v$ 表示 $v$ 节点子树内的所有函数都应向左平移 $\Delta_v$ 个单位。
• 对新操作"将 $v$ 子树内所有函数向左平移 $\delta$"（即 $f(x)\leftarrow f(x+\delta)$），更新懒标记：$\Delta_v\leftarrow \Delta_v + \delta$，累加子树内所有节点的偏移量。
• 向左平移同时意味着 $0$ 点函数值的变化：若证书的失效横坐标为 $t$，则平移后的失效横坐标应为 $t-\delta$；如果 $t-\delta$ 越过 $0$ 点，就代表证书失效，需要向下递归找到证书所在节点，更新该节点，并把新的信息向上更新到根。这个过程可以跟随修改操作一起进行。

参考实现：ktt_1.cpp 逐函数剖析

仓库中的完整参考实现位于 docs/ds/code/ktt/ktt_1.cpp，其核心部分如下（与文档中的引用片段一致）：

struct node { int l, r; int tag; // the lazy propagation tag int k, b; // the linear function int swc; // the time of certificate violation }; vector<node> v; int IntegerPart(double x) { if (x >= 0 && x <= inf) return int(ceil(x)); return inf; } void push_up(int rt) { int mx = v[rt << 1].b > v[rt << 1 | 1].b ? rt << 1 : rt << 1 | 1, mi = mx ^ 1; v[rt].k = v[mx].k, v[rt].b = v[mx].b; v[rt].swc = v[mx].k < v[mi].k ? IntegerPart(1.0 * (v[mx].b - v[mi].b) / (v[mi].k - v[mx].k)) : inf; } void push_tag(int rt, int val) { v[rt].tag += val, v[rt].swc -= val, v[rt].b += v[rt].k * val; } void push_down(int rt) { if (v[rt].tag) push_tag(rt << 1, v[rt].tag), push_tag(rt << 1 | 1, v[rt].tag), v[rt].tag = 0; } void checkswitch(int rt) { if (v[rt].l == v[rt].r) return; push_down(rt); if (v[rt].swc <= 0) checkswitch(rt << 1), checkswitch(rt << 1 | 1); push_up(rt); } void build(int rt, int l, int r) { v[rt].l = l, v[rt].r = r; if (l == r) return v[rt].k = k[l], v[rt].b = b[l], void(); int mid = (l + r) >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); push_up(rt); } void TranslateLeft(int rt, int l, int r, int val) { if (l <= v[rt].l && v[rt].r <= r) return push_tag(rt, val), checkswitch(rt); int mid = v[rt << 1].r; push_down(rt); if (l <= mid) TranslateLeft(rt << 1, l, r, val); if (mid < r) TranslateLeft(rt << 1 | 1, l, r, val); push_up(rt); } int QueryMax(int rt, int l, int r) { if (l <= v[rt].l && v[rt].r <= r) return v[rt].b; int mid = v[rt << 1].r, res = 0; push_down(rt); if (l <= mid) res = max(res, QueryMax(rt << 1, l, r)); if (mid < r) res = max(res, QueryMax(rt << 1 | 1, l, r)); return res; }

主函数部分负责读入与操作分发：读入 $n,m$ 及每行的 $k_i,b_i$，建树后循环处理 $m$ 个操作——opt == 1执行QueryMax(1, l, r)并输出，opt == 2执行TranslateLeft(1, l, r, delta)。

核心函数语义

• node.swc（switch time）：当前证书失效的时间。对节点 $rt$，其维护的"胜者"是 $0$ 点值更大的儿子 $mx$，输家是 $mi$。若 $mx$ 的斜率更小（v[mx].k < v[mi].k），则在平移过程中胜者会逐渐被反超，交点为 $(v[mx].b - v[mi].b)/(v[mi].k - v[mx].k)$；若 $mx$ 的斜率不小于输家，则胜者永远不会被反超，swc设为无穷大。
• IntegerPart：把实数交点坐标转化为"证书失效发生的离散时刻"，采用ceil向上取整（当 $x$ 超出范围时返回inf）。这一步是算法竞赛实现中常见的整数化处理，避免浮点误差并支持整型懒标记。
• push_up：自底向上合并左右儿子——选出当前 $0$ 点值更大的函数作为节点胜者，并重新计算该节点证书的失效时刻。
• push_tag：对节点打上懒标记，同时更新其影响：b += k * val（$0$ 点值随平移变化）、swc -= val（失效时刻随平移提前 $\delta$）。这正是"证书失效时刻减去平移量"的落地实现。
• push_down：把懒标记下传给两个儿子并清空自身标记，保证进入子树前标记已生效。
• checkswitch：检查证书是否失效（swc <= 0）。若失效则递归进入左右儿子检查并重新合并（push_up），将"最大值来源改变"传播到整棵子树；叶子节点直接返回，不产生递归。这个函数是 KTT 区别于普通线段树的核心——它把"证书失效"这一事件转化为树上的递归修正。
• TranslateLeft：标准线段树区间修改框架：完全覆盖时打标记并checkswitch；否则下放标记、递归左右、回溯push_up。
• QueryMax：标准区间查询框架，完全覆盖时直接返回该节点维护的 $b$（$0$ 点最大值）。

从源码结构看，KTT 与普通线段树的差别集中在三处：节点多存了"胜者函数"（$k,b$）与"证书失效时刻"（swc）；push_tag需要同步维护 $b$ 与swc；以及每次修改后必须调用checkswitch处理可能越过 0 点的证书。这三处正是上文理论中"证书、懒标记、失效检测"三个概念的代码映射。

复杂度分析：势能方法

证明 KTT 的时间复杂度需要用到势能分析。

线性情况的势能函数

设 $d(x)$ 为节点 $x$ 在线段树上的深度（根节点的深度为 $1$）。定义节点 $x$ 的势能为：

$$ \alpha(x) = \begin{cases} d(x) & \text{if the lower slope function has larger value} \ 0 & \text{otherwise}\ \end{cases} $$

即在 $x$ 比较的两个函数中，若拥有较小斜率的函数在 $0$ 点的值更大，则当前节点势能为 $d(x)$，否则为 $0$。

定义整个 KTT 的势能为所有节点势能之和：

$$ \Phi = \sum_x \alpha(x) $$

均摊代价推导

考虑某次对节点 $x$ 和其父亲 $p$ 的实际更新代价 $c=1$，更新前后的势能分别为 $\Phi$ 和 $\Phi'$。计算更新节点 $x$ 的均摊更新代价：当前节点 $x$ 被更新，其势能一定从 $d(x)$ 下降到 $0$；而对 $p$，最坏情况下其势能可能从 $0$ 上升到 $d(p)$：

$$ \begin{aligned} \hat{c} &= 1 + \Phi' - \Phi\ &= 1 + (\alpha'(p) + \alpha'(x)) - (\alpha(p) + \alpha(x))\ &= 1 + (\alpha'(p) - \alpha(p)) + (\alpha'(x) - \alpha(x))\ &\leq 1 + d(p) - d(x)\ &= 0 \end{aligned} $$

对实际代价求和，设初始势能为 $\Phi_s$、最终势能为 $\Phi_t$：

$$ \begin{aligned} \sum c &= \sum \hat{c} + \Phi_{s} - \Phi_{t}\ &\leq \Phi_{s} - \Phi_{t}\ &=O(n\log n) \end{aligned} $$

这部分对应KTT 在仅存在全局修改的情况下，将所有证书失效更新完毕的次数。

区间平移带来的势能上涨

额外考虑区间平移对势能的影响。对于某次区间平移，需要关注的节点应当是其子树中存在、但不是所有节点都被执行区间平移的节点——也就是执行修改操作时在树上经过的节点，其数量不超过 $O(\log n)$ 个。最坏情况下每个节点的势能上涨 $d(x)\le \log n$，因此每次操作上涨 $O(\log^2 n)$ 的势能。

总时间复杂度

为维护区间平移，更新证书的操作将被执行 $O(n\log n + m\log^2 n)$ 次。每次更新证书都需要从树上沿着路径走到证书失效的节点，这部分代价是 $O(\log n)$ 的。因此总时间复杂度为 $O(n\log^2 n + m\log^3 n)$。

值得注意的是，这个方法的优秀之处在于它已经触及问题时间复杂度的下界 $O(\lambda_{s}(n)\log^2 n)$。其中 $\lambda_{s}(n)$ 表示长度最长的 $(n,s)$ Davenport-Schinzel 序列的长度；线性函数对应 $s=1$ 的情况，此时 $\lambda_1(n)=n$。这部分属于计算几何内容，本文不再展开。

高次情况：多项式函数序列的推广

如果维护的不是线性函数而是多项式函数（或更复杂的函数），应如何处理？两个复杂函数之间可能拥有多个交点。给定一个连续、完全定义的单变量函数序列 $F={f_1,\dots,f_n}$，$f_i: \mathbf{R} \rightarrow \mathbf{R}$，其中每对函数的图像至多相交于 $s$ 个点。具有代表性的，$s$ 次多项式函数集合符合这个要求。

对同样的问题使用势能分析。$d(x)$ 仍为节点 $x$ 在线段树上的深度（根深度为 $1$）。定义 $I(x)$ 表示在节点 $x$ 比较的两个函数在 $0$ 点过后还有几个交点。定义节点 $x$ 的势能为：

$$ \alpha(x)=d(x)^{\log_2(s+1)}I(x) $$

整体势能为：

$$ \Phi = \sum_x \alpha(x) $$

考虑某次对节点 $x$ 和其父亲 $p$ 的实际更新代价 $c=1$：当前节点 $x$ 被更新后，其势能由 $d(x)^{\log_2(s+1)}I(x)$ 下降到 $d(x)^{\log_2(s+1)}(I(x)-1)$；而 $p$ 的势能最坏可能由 $0$ 上升到 $d(p)^{\log_2(s+1)}$：

$$ \begin{aligned} \hat{c} &= 1 + \Phi' - \Phi\ &= 1 + (\alpha'(x) - \alpha(x)) + (\alpha'(p) - \alpha(p))\ &\leq 1 - d(x)^{\log_2{(s+1)}} + s(d(x)-1)^{\log_2{(s+1)}}\ &\leq 0 \end{aligned} $$

由第三行到第四行使用了 $d(x)$ 为正整数的限制（最后一个不等式在 $d(x)\ge 1$、$s\ge 1$ 时成立）。

对实际代价求和，得到：

$$ \begin{aligned} \sum c &= \sum \hat{c} - \Phi_t + \Phi_s\ &\leq \Phi_s - \Phi_t\ &= O(ns (\log n)^{\log_2{(s+1)}}) \end{aligned} $$

最终得到复杂度的上界 $O(ns (\log n)^{1+\log_2{(s+1)}} + ms (\log n)^{2+\log_2{(s+1)}})$。当 $s=1$（线性函数）时，该上界退化为 $O(n\log n + m\log^2 n)$ 次证书更新，与前述线性分析一致。

注：以上仅为势能分析给出的上界。复杂度的下界应为 $O(\lambda_{s}(n)\log n)$。有观点认为，这里的势能分析构造可以参考 Davenport-Schinzel 序列对应的 $\lambda_{s}(n)$ 通项公式，以获得更紧的上界。

近似情况：$\epsilon$-近似上包络

当函数变得非常复杂时，精确维护可能代价过高。此时可以引入近似查询。给定一个连续、完全定义的单变量函数序列 $F={f_1,\dots,f_n}$，定义 $\mathfrak U_F(x)$、$\mathfrak L_F(x)$ 和 $\mathfrak E_F(x)$ 分别为上包络、下包络和幅度：

$$ \begin{aligned} \mathfrak U_F(x) & = \max{f_i(x) \mid f_i \in F} \ \mathfrak L_F(x) & = \min{f_i(x) \mid f_i \in F} \ \mathfrak E_F(x) & = \mathfrak U_F(x) - \mathfrak L_F(x) \end{aligned} $$

只要求程序返回 $\tilde{\mathfrak U}_F(x)$ 满足：

$$ \mathfrak U_F(x) \geq \tilde{\mathfrak U}_F(x) \geq \mathfrak U_F(x) - \epsilon \mathfrak E_F(x) $$

即在 $\epsilon \cdot \mathfrak E_F(x)$ 的容差范围内返回上包络的近似值。此时在复杂情况下可以做到 $O((1/\epsilon^2)n\log^3 n)$，与多项式次数无关，并且允许函数同时进行区间左移或右移。

近似情况的价值在于：当函数交点数量 $s$ 很大时，精确维护的势能上界会随 $s$ 显著增长（见高次情况），而 $\epsilon$-近似通过引入可控误差，把复杂度从对"函数复杂性"的依赖中解放出来。

实战验证：用仓库测试数据走一遍 KTT

仓库提供了配套测试数据 ktt_1.in 与标准答案 ktt_1.ans，可用以验证上述实现的行为。

输入数据格式：第一行 $n=5, m=12$；随后 5 行给出函数的 $(k_i, b_i)$ 分别为 $(1,50),(2,30),(3,20),(4,10),(5,5)$；之后是 12 个操作。逐步演算如下：

输出序列为50 105 80 130 210 210 210 155，与标准答案 ktt_1.ans 完全一致。从这个例子可以直观看到：初始时 $f_1(0)=50$ 最大；经过全局平移 $\delta=20$ 后，斜率最大的 $f_5$ 因 $b_5=5+5\times20=105$ 反超成为最大值——这正是"证书失效、胜者切换"发生的瞬间，KTT 通过checkswitch探测并修正了它。手工验算与程序输出吻合，说明 ktt_1.cpp 的实现正确落地了本文描述的理论。

小结

KTT 是 KDS 思想在算法竞赛中的典型应用，其设计链条清晰：

1. 问题抽象：区间平移等价于按位置系数加权区间加，普通线段树无法高效维护"最大值来源"的动态变化；
2. 证书化：把"胜者不变"转化为低阶代数条件（两函数交点），将变化探测归结为 $O(1)$ 求交点；
3. 懒标记 + 失效检测：平移通过懒标记累加，证书失效时刻随之提前，越过 0 点即递归修正；
4. 势能分析：证明线性情况总复杂度 $O(n\log^2 n + m\log^3 n)$，并触及下界 $O(\lambda_s(n)\log^2 n)$；
5. 推广：高次函数通过加权深度势能分析得到 $O(ns(\log n)^{1+\log_2(s+1)} + ms(\log n)^{2+\log_2(s+1)})$ 的上界；近似情况可做到与函数次数无关的 $O((1/\epsilon^2)n\log^3 n)$。

参考实现见 docs/ds/code/ktt/ktt_1.cpp，配套测试数据见 docs/ds/examples/ktt/ktt_1.in 与 docs/ds/examples/ktt/ktt_1.ans，可编译运行验证。

参考文献

• P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606–635, July 2004.
• J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. Journal of Algorithms, 31(1):1–28, 1999.
• G. Alexandron, H. Kaplan, and M. Sharir. Kinetic and dynamic data structures for convex hulls and upper envelopes. Computational Geometry, 36(2):144–158, 2007.

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki