关于 KTT

critnos · 2023-08-08 17:16:25 · 题解

原文：https://entropyincreaser.blog.uoj.ac/blog/5217

KTT 维护区间最大子段和。

除了维护区间和，区间最大子段和，区间最大前/后缀和（维护这个和还有长度），还要额外维护一个量表示“这个结点最少加上多少之后区间最大子段和/区间最大前/后缀和的决策会发生变化。”如果给子树加上 x 后发生变化就暴力递归下去，否则直接在原决策上加上长度乘上 x。x 是正数。

下面是阿巴阿巴的复杂度证明，我觉得大概是对的。

复杂度证明：前后缀长度显然只会增加，那么每次增加的时间复杂度是 O(\log n)，总时间复杂度是 O(n\log ^2n)。而对于最大子段和的变化使用势能分析。

一个结点的势能：最大子段和可能从左区间最大子段和、右区间最大子段和、左区间最大后缀和+右区间最大前缀和更新，这可以抽象为三条直线 a,b,c，设当前决策是 p\in\{a,b,c\}，d 表示这个结点到根的距离，当前结点的势能就是 d([k_p<k_a]+[k_p<k_b]+[k_p<k_c])（k 是直线斜率）。整棵树的势能是所有结点的势能之和。显然势能是正的。

考虑一次暴力递归发生时（原文称之为“击败事件”）对势能的影响。这意味着该结点的 p 增大了，势能减小 \ge d；同时父亲的势能增量 \le d-1。综上这次时间复杂度 O(\log n) 的击败事件使势能增加了一个负数。

单次修改会重置 O(\log n) 个结点（非整体加）的势能即把势能增加了 O(\log^2n).

但是！我们还没有考虑最大前后缀和对势能的影响。注意到前后缀的更新次数是 O(n\log n)，单次更新会让势能增加 \le d-1，所以这里的总势能是 O(n\log^2 n)。

综上，时间复杂度 O((n+m)\log^3 n)。