KTT 学习笔记

白子妹妹

KTT 在做 $a_i{x}_i+b_i$ 的时候，能方便的做 $x_i$ 区间加 $b_i$ 区间加区间查最大。

这意味着，在一些（神秘）题目里，我们对于一个位置增量是固定的数的倍数时很方便，类似做一些等差数列的时候（虽然大多数题目维护直线就够了）。

KTT 简介 ​

KTT（Kinetic Tournament Tree）是由 EntropyIncreaser 在其论文《浅谈函数最值的动态维护》给出的用于解决区间加正数和区间最大子段和问题的数据结构。

论文在 2020 年集训队论文集里。

时间复杂度是 3 个 $\log$。

相关链接 ​

By EntropyIncreaser 区间增量最大子段和的 polylog 做法: https://entropyincreaser.blog.uoj.ac/blog/5217

By Petit_Souris KTT 入门: https://www.luogu.com.cn/article/7zzxpepq

By Otomachi_Una_ KTT 学习笔记: https://www.luogu.com.cn/article/u0ouhel6

维护 $ax+b$ ​

我们维护 $x$ 的单点加是容易的。一个方便的写法是线段树储存叶子节点处储存 $a,b$，每次单点加 $v$ 就令 $b\leftarrow va$，再依次上传取 $b$ 的最大值。

然后再想区间加，这个时候如果在父节点处直接对着最大的 $b$ 加显然会有问题，因为有可能另一个增长率更快的线超过了原先的最大的 $b$。

那么，维护出一个数 $x$，使得一次加上了超过 $x$ 的数则当前节点子树节点 $max$ 会发生改变。这个是方便维护的，只要从左子树的 $x$ 右子树的 $x$ 以及两个子树的最大的线的交点的纵坐标取 $min$ 就好了。

然后在修改的时候直接令 $x\leftarrow x-v$，若 $x<0$ 了则递归 pushdown 到子树再 pushup 上来重构当前子树，可以证明这样做是 ${\log }^3$ 的。

复杂度要用势能分析证明，相关证明在 2020 年集训队论文中。

例题(先咕了，我自己没写几道)。