KTT 小结

cheng2010 · 2025-11-14 22:05:44 · 算法·理论

偶然看到，感觉挺牛逼，可以优化一些刁钻的 dp。

理论

考虑这样一个问题：

给定 k,b,x，每次给 k 或 b 加上一个数 a，查询 l,r，求 \displaystyle \max_{i=l}^{r}\{b_i+k_i x_i\}。

可以看到操作本质上是区间加上不同的数，只用调整那个 a。

用到 dp 上就是 f_{i}=\max(w1(i,j) f_j+w2(i,j)) 之类。

限制是必须加正数！否则时间复杂度无法保证。

KTT 本质就是线段树，每个节点存 kx+b 的 k,b，如果加就是 a 加上 ak。

然后，在线段树中我们要维护一个极其关键的值，\rm intr，我们称其为交替阈值。其中，交替是 KTT 一个重要的操作，他使得 KTT 可以处理最大值的询问，也给 KTT 解决的问题带来了限制。

交替：本问题与常规线段树问题最大的不同是，即便是对一整段区间修改同样的东西，这段区间的最大值也有可能改变，这就叫交替。我们不关注交替之后谁是最大值，因为我们可以直接 pushdown 加 pushup 计算出来，我们只关注什么时候会交替，这时候就需要交替阈值这个东西了。

线段树存的东西：k,b,lazy,intr，其中 intr 就是每次对 x 加上 k 时，它就减上 k，<0 时就该交替了。

可见，KTT 其实就是用阈值来剪枝。

接下来一个个函数来讲讲。

以下是一些前置，部分内容下面会说：

#include<bits/stdc++.h>
#define int long long
#define LL p<<1
#define RR p<<1|1
using namespace std;
const int N=1e6+7;
const int INF=1e18;
struct Line
{
    int k,b;
    inline bool operator < (const Line&B) const{return b==B.b?k<B.k:b<B.b;}
    Line(){k=b=0;}
    Line(int _a,int _b):k(_a),b(_b){};
    friend inline int operator ^ (const Line&A,const Line&B)
    {
        Line X=A,Y=B;
        if(X.k<Y.k||(X.k==Y.k&&X.b<Y.b)) swap(X,Y);
        if(X.b>=Y.b) return INF;
        return (Y.b-X.b)/(X.k-Y.k); 
    }
};
struct Tree
{
    Line l;
    int lazy,intr;
    Tree(){lazy=l.k=l.b=intr=0;}
    Tree(int _a,int _b,int _c,int _d):l(_a,_b),lazy(_c),intr(_d){};
    friend inline Tree operator + (Tree A,Tree B)
    {
        Tree res;
        res.l=max(A.l,B.l);
        res.intr=min({A.intr,B.intr,A.l^B.l}); 
        return res;
    }
};

一、build

就是一些初始化。

inline void build(int p,int l,int r)
{
    tr[p]=Tree(-INF,-INF,0,INF);
    if(l==r) return;
    int mid=l+r>>1;
    build(LL,l,mid);
    build(RR,mid+1,r); 
}

二、pushdown

inline void push(int p,int x)
{
    tr[p].lazy+=x;
    tr[p].l.b+=x*tr[p].l.k;
    tr[p].intr-=x;//距离交点更近一步。
}
inline void pushdown(int p)
{
    int&x=tr[p].lazy;
    push(LL,x),push(RR,x);
    return x=0,void();
}

根据定义算即可。

三、pushup

其实就一句话。

tr[p]=tr[LL]+tr[RR];

就是前面的：

friend inline Tree operator + (Tree A,Tree B)
{
    Tree res;
    res.l=max(A.l,B.l);
    res.intr=min({A.intr,B.intr,A.l^B.l}); 
    return res;
}

重点在 Line 中的 ^ 运算。

friend inline int operator ^ (const Line&A,const Line&B)
{
    Line X=A,Y=B;
    if(X.k<Y.k||(X.k==Y.k&&X.b<Y.b)) swap(X,Y);
    if(X.b>=Y.b) return INF;//平行或交点<=0则不会更替。
    return (Y.b-X.b)/(X.k-Y.k); 
}

就是求交点，因为一次函数是单调的，所以按交点讨论，和李超线段树差不多。

顺便提，我这种写法常数有点大，在上面的 ^ 运算中，可以写成一个函数，返回一个 pair，具体地，可以这样写：

inline pair<Line,int> merge(Line X,Line Y)
{
    if(X.k<Y.k||(X.k==Y.k&&X.b<Y.b)) swap(X,Y);
    if(X.b>=Y.b) return {X,INF};
    return {Y,(Y.b-X.b)/(X.k-Y.k)};
}

这样求交点时顺便把最大值求了，常数自然减小。

不过个人认为重载好看一点，方便查错，而且除了 Ynoi 没人会卡你这个常数。

四、rebuild

KTT 所特有的函数，当 \text{intr} \le 0 时，最大值会改变，就要重构，其实就是遍历一遍然后 pushdown/up。

inline void rebuild(int p)
{
    if(tr[p].intr>0) return;
    pushdown(p);
    rebuild(LL),rebuild(RR);
    pushup(p);
    return; 
}

五、set

单点修改，没什么好说的。

inline void Set(int p,int l,int r,int x,Tree k)
{
    if(l==r) return tr[p]=k,void();
    int mid=l+r>>1;
    pushdown(p);
    if(mid>=x) Set(LL,l,mid,x,k);
    else Set(RR,mid+1,r,x,k);
    pushup(p); 
}

六、update

区间改 k。

注意要 rebuild 以确保答案，然后就没了。

inline void update(int p,int l,int r,int L,int R,int x)
{
    if(L<=l&&r<=R)
    {
        push(p,x);
        rebuild(p);
        return;
    }
    pushdown(p);
    int mid=l+r>>1;
    if(mid>=L) update(LL,l,mid,L,R,x);
    if(mid<R) update(RR,mid+1,r,L,R,x);
    pushup(p);
}

七、query

不必多说。

inline int query(int p,int l,int r,int L,int R)
{
    if(L<=l&&r<=R) return tr[p].l.b;
    pushdown(p);
    int mid=l+r>>1;
    if(mid>=R) return query(LL,l,mid,L,R);
    if(mid<L) return query(RR,mid+1,r,L,R);
    return max(query(LL,l,mid,L,R),query(RR,mid+1,r,L,R));
}

拼起来就是模板题的代码啦。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
namespace KTT
{
    #define int long long
    #define LL p<<1
    #define RR p<<1|1
    const int N=1e6+7;
    const int INF=1e18;
    struct Line
    {
        int k,b;
        inline bool operator < (const Line&B) const{return b==B.b?k<B.k:b<B.b;}
        Line(){k=b=0;}
        Line(int _a,int _b):k(_a),b(_b){};
        friend inline int operator ^ (const Line&A,const Line&B)
        {
            Line X=A,Y=B;
            if(X.k<Y.k||(X.k==Y.k&&X.b<Y.b)) swap(X,Y);
            if(X.b>=Y.b) return INF;
            return (Y.b-X.b)/(X.k-Y.k); 
        }
    };
    struct Tree
    {
        Line l;
        int lazy,intr;
        Tree(){lazy=l.k=l.b=intr=0;}
        Tree(int _a,int _b,int _c,int _d):l(_a,_b),lazy(_c),intr(_d){};
        friend inline Tree operator + (Tree A,Tree B)
        {
            Tree res;
            res.l=max(A.l,B.l);
            res.intr=min({A.intr,B.intr,A.l^B.l}); 
            return res;
        }
    }tr[N];
    inline void push(int p,int x)
    {
        tr[p].lazy+=x;
        tr[p].l.b+=x*tr[p].l.k;
        tr[p].intr-=x;
    }
    inline void build(int p,int l,int r)
    {
        tr[p]=Tree(-INF,-INF,0,INF);
        if(l==r) return;
        int mid=l+r>>1;
        build(LL,l,mid);
        build(RR,mid+1,r); 
    }
    inline void pushdown(int p)
    {
        int&x=tr[p].lazy;
        push(LL,x),push(RR,x);
        return x=0,void();
    }
    inline void pushup(int p)
    {
        tr[p]=tr[LL]+tr[RR];
    }
    inline void rebuild(int p)
    {
        if(tr[p].intr>0) return;
        pushdown(p);
        rebuild(LL),rebuild(RR);
        pushup(p);
        return; 
    }
    inline void Set(int p,int l,int r,int x,Line k)
    {
        if(l==r) return tr[p].l=k,void();
        int mid=l+r>>1;
        pushdown(p);
        if(mid>=x) Set(LL,l,mid,x,k);
        else Set(RR,mid+1,r,x,k);
        pushup(p); 
    }
    inline void update(int p,int l,int r,int L,int R,int x)
    {
        if(L<=l&&r<=R)
        {
            push(p,x);
            rebuild(p);
            return;
        }
        pushdown(p);
        int mid=l+r>>1;
        if(mid>=L) update(LL,l,mid,L,R,x);
        if(mid<R) update(RR,mid+1,r,L,R,x);
        pushup(p);
    }
    inline int query(int p,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R) return tr[p].l.b;
        pushdown(p);
        int mid=l+r>>1;
        if(mid>=R) return query(LL,l,mid,L,R);
        if(mid<L) return query(RR,mid+1,r,L,R);
        return max(query(LL,l,mid,L,R),query(RR,mid+1,r,L,R));
    }
    #undef int
    #undef LL
    #undef RR 
}
int n,q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    KTT::build(1,1,n);
    for(int i=1;i<=n;i++)
    {
        int k,b;
        cin>>k>>b;
        KTT::Set(1,1,n,i,{k,b});
    }
    while(q--)
    {
        int opt,l,r,x;
        cin>>opt>>l>>r;
        if(opt==1)
        {
            cin>>x;
            KTT::update(1,1,n,l,r,x);
        }
        else
        {
            cout<<KTT::query(1,1,n,l,r)<<'\n';
        }
    }
}

:::

KTT 的时间复杂度分析非常困难，论文中说是 \log^3 的，不过可以比较一下，10^5 的数据量 KTT 110ms，树剖两只老哥 150ms，线段树一只老哥 80ms，所以只要不特意去卡就可以看作小常数 \log^2。

运用

KTT 还有神秘运用。

经典问题

考虑如下问题：

区间加，区间求最大子段和。

如果加的数是正数的话，我们就有 KTT 做法。否则就是什么分块套上闵可夫斯基和了。

因为求区间最大子段和在线段树上本质就是一堆取 \max，所以就是 KTT 可以做得东西。