OI-wiki 中的 Kinetic Tournament TreeKTT详解动态维护函数区间最大值【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读Kinetic Tournament TreeKTT动力学竞赛树是一种将静态算法动态化的数据结构用于维护一组线性函数在区间平移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_ixb_i$$k_i,b_i \in \mathbf{R}$。我们需要维护以下两种操作$\operatorname{QueryMax}(l,r)$给定 $l$ 和 $r$返回 $\max_{il}^{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_ik_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 DataJ. Basch, L. J. Guibas, J. Hershberger用于维护连续变化的数据。更普遍地每一个采用如下**动态化策略kinetization strategy**的结构都可以称为 Kinetic Tournament为静态算法中的关键操作例如比较生成正确性证书并将每个证书与一个全局事件队列关联记录该证书可能失效的时间点当某个证书失效时能够高效地更新算法输出并维护证书集合。在算法竞赛社区它兴起于 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 }; vectornode 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.swcswitch 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$与证书失效时刻swcpush_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$ 的实际更新代价 $c1$更新前后的势能分别为 $\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 序列的长度线性函数对应 $s1$ 的情况此时 $\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(s1)}I(x) $$整体势能为$$ \Phi \sum_x \alpha(x) $$考虑某次对节点 $x$ 和其父亲 $p$ 的实际更新代价 $c1$当前节点 $x$ 被更新后其势能由 $d(x)^{\log_2(s1)}I(x)$ 下降到 $d(x)^{\log_2(s1)}(I(x)-1)$而 $p$ 的势能最坏可能由 $0$ 上升到 $d(p)^{\log_2(s1)}$$$ \begin{aligned} \hat{c} 1 \Phi - \Phi\ 1 (\alpha(x) - \alpha(x)) (\alpha(p) - \alpha(p))\ \leq 1 - d(x)^{\log_2{(s1)}} s(d(x)-1)^{\log_2{(s1)}}\ \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{(s1)}}) \end{aligned} $$最终得到复杂度的上界 $O(ns (\log n)^{1\log_2{(s1)}} ms (\log n)^{2\log_2{(s1)}})$。当 $s1$线性函数时该上界退化为 $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可用以验证上述实现的行为。输入数据格式第一行 $n5, m12$随后 5 行给出函数的 $(k_i, b_i)$ 分别为 $(1,50),(2,30),(3,20),(4,10),(5,5)$之后是 12 个操作。逐步演算如下步骤操作操作后 $b$ 序列输出11 1 5查询 $[1,5]$$(50,30,20,10,5)$$50$22 1 5 20区间左移 20$(70,70,80,90,105)$—31 1 5$(70,70,80,90,105)$$105$41 1 3—$80$52 1 2 30$(100,130,80,90,105)$—61 1 5—$130$72 3 5 10$(100,130,110,130,155)$—82 1 2 40$(140,210,110,130,155)$—91 1 5—$210$101 1 3—$210$111 2 4—$210$121 3 5—$155$输出序列为50 105 80 130 210 210 210 155与标准答案 ktt_1.ans 完全一致。从这个例子可以直观看到初始时 $f_1(0)50$ 最大经过全局平移 $\delta20$ 后斜率最大的 $f_5$ 因 $b_555\times20105$ 反超成为最大值——这正是证书失效、胜者切换发生的瞬间KTT 通过checkswitch探测并修正了它。手工验算与程序输出吻合说明 ktt_1.cpp 的实现正确落地了本文描述的理论。小结KTT 是 KDS 思想在算法竞赛中的典型应用其设计链条清晰问题抽象区间平移等价于按位置系数加权区间加普通线段树无法高效维护最大值来源的动态变化证书化把胜者不变转化为低阶代数条件两函数交点将变化探测归结为 $O(1)$ 求交点懒标记 失效检测平移通过懒标记累加证书失效时刻随之提前越过 0 点即递归修正势能分析证明线性情况总复杂度 $O(n\log^2 n m\log^3 n)$并触及下界 $O(\lambda_s(n)\log^2 n)$推广高次函数通过加权深度势能分析得到 $O(ns(\log n)^{1\log_2(s1)} ms(\log n)^{2\log_2(s1)})$ 的上界近似情况可做到与函数次数无关的 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考