势能线段树

Simulated_annealing · 2026-10-03 13:44:15 · 算法·理论

前言

本文将讲述几道势能线段树经典题目，并逐步得到更一般的势能线段树做题方法。

本文不适合没有线段树基础或不会使用懒标记的选手阅读。

引入

我们用这样一道题目来引入 P4145 上帝造题的七分钟 2 / 花神游历各国。

显然相较于一般的线段树我们发现，我们并不能用开根懒标记来维护区间和。

所以我们考虑递归到叶子修改，这样显然是正确的，但是复杂度肯定不正确。

我们注意到开根只会越开越小。

所以我们考虑怎样减少到叶子的递归。

我们发现如果一个区间的最大值是 0 或 1，那么这个节点一定不用再向下递归了。

这看上去复杂度依旧假完了，是吗？

确实，这样我们确实可以把单次操作卡到 O(n)。

但是我们似乎发现不会过多的递归，在递归多次之后就不会再递归了

但是其实不是的，我们递归会有如下性质：

任何被递归到的节点都必然递归了它的至少一个子节点。
同一个叶子至多被递归 O(\log \log w) 次（w 为初始值）

因此我们注意在开根操作中到同一叶子至多被访问 O(\log \log V) 次。

所以我们发现在开根操作中，总复杂度不超过 O(n \log n\log \log V) 次。

什么，你说 \log \log V 是常数，好吧，其实差不多。

然后这就讲完了。

但是这有没有更一般的分析而不是分析每个叶子访问次数呢？

有的：

我们令 \Phi 为势能量（如果读者拥有一定物理知识，可以思考这与物理的势能概念有什么关系），令 \Phi=\sum_{i=1}^nf(a_i)。

其中

f(n)=\begin{cases}0&n\le 1\\\log_2 \log_ n&n>1\end{cases}

我们发现 f(\sqrt n)=\log_2 \frac{1}{2}\log n=(\log_2 \log n)-1

于是我们发现每次开根操作会使 \Phi 减少，且该次开根操作的复杂度是 O(\Delta \Phi\log n) 的（每个叶子的 f 减少 1）。

此外，我们发现任何时刻 \Phi 非负，且初始 \Phi 为 O(n\log \log V) 的。

于是我们也就可以证明所有修改为 O(n\log n\log \log V) 也就是单次均摊 O(\log n\log \log V)。

进阶

CF438D The Child and Sequence

发现题目中无法直接维护的是取模操作。

而我们知道取模可以写成 a=px+b,0\le b< x。

我们发现如果 p\ge 1 则 b < \frac{a}{2}。

而且，p=0 当且仅当 b>x。

于是我们思考怎样确保递归到的叶子都满足 p\ge 1。

显然我们可以维护区间 \max 若区间 \max 比 x 小这直接退出。

我们依旧有“任何被递归到的节点都必然递归了它的至少一个子节点”的性质。

但是我们现在不能分析每个节点修改的次数，因为单点修改操作。

但是我们依旧可以使用势能分析。

这次我们依旧令 \Phi=\sum_{i=1}^nf(a_i)。

但是其中 f(n)=\begin{cases}1+\log_2 n&n\ge 1\\0 & n=0\end{cases}。

我们发现每次操作会使得这个叶子的 f 至少减小 1。

而且我们还发现每次单点修改至多会让 \Phi 增大 \log V。

故而总 \Phi（初始的和中途增加的）是 O((n+q)\log V) 的。

而修改操作是一共 O(\Phi\log n)=O((n+q)\log n\log V) 的。

其他的还有建树 O(n) 其余操作 O(q\log n)。

所以总复杂度 O((n+q)\log n\log V)。

小结

我们现在应该总结一下什么情况应当使用势能线段树和如何使用势能线段树。

势能线段树通常在修改操作无法快速维护区间信息时使用。

如果你的势能线段树势能分析基于序列：
势能线段树需要维护一样或多样额外信息，使得我们所有递归到的叶子都会减少至少 1 的势能，我们还需要设计一个势能函数，势能函数通常与每个元素的值有关，此时势能线段树的复杂度就是 O((n+q+\Phi)\log n)。

如果你的势能线段树势能分析基于线段树节点：势能线段树将维护一样或多样额外信息使得所有访问后继续向下递归的节点子树减少 1 的势能，我们还需要设计一个势能函数，势能函数与每个节点（很有可能是额外信息）有关，此时势能线段树的复杂度就是 O((n+q)\log n+\Phi)。

基于序列的势能线段树较为基础，而基于线段树节点的势能线段树较为困难。

实战

Lowbit

没找到题目，就口胡一下。

维护序列支持：

区间查询
区间加 \operatorname{lowbit}

此外保证任意时刻每个元素小于 2^B。

那么我们就用 \operatorname{popcount} 作为势能函数吧。

我们发现对于 \operatorname{popcount}(a_k)=1 则说明这是 2 的幂次，修改等价于乘 2。

然后区间额外维护一个各个元素 \operatorname{popcount} 的 \min。

P9069 [Ynoi Easy Round 2022] 堕天作战 TEST_98

这也就是本文最困难的一题了。

这里假设你不会写分块做法。

我们先分析，发现：

如果一段没有 x，我们可以直接修改。
求 a_i\not=0 的和就是求 a_i 的和。
序列值不会增大。

难点是在于区间等于 x 的数是无法维护的。

但是我们知道一个数如果小于 0 了，那么它在以后的任何一次修改中都可以直接改。

于是我们考虑维护区间的非负最小值。

发现如果区间的非负最小值大于 x 我们就可以直接修改。

然后你会发现这是会 TLE 的。 TLE 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 LL;
typedef unsigned long long ull;
const int N=5e5+50,P=(1<<20)-1;
const LL inf=1e24;
int a[N];
struct SegmentTree{
    LL sum[N<<2];
    LL mn[N<<2],tag[N<<2];
    void pushup(int u){
        mn[u]=min(mn[u<<1],mn[u<<1|1]);
        sum[u]=sum[u<<1]+sum[u<<1|1];
    }
    void apply(int u,int len,ll c){
        sum[u]-=LL(len)*c;
        mn[u]-=c;
        tag[u]+=c;
    }
    void pushdown(int u,int l,int r){
        int mid=(l+r)>>1;
        apply(u<<1,mid-l+1,tag[u]);
        apply(u<<1|1,r-mid,tag[u]);
        tag[u]=0;
    }
    void update(int u,int l,int r,int L,int R,int c){
        if(L<=l && r<=R){
            if(mn[u]>c){
                apply(u,r-l+1,c);
                return ;
            }
        }
        if(l==r){
            if(mn[u]==c)return ;
            mn[u]=inf;
            sum[u]-=c;
            return ;
        }
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        if(L<=mid)update(u<<1,l,mid,L,R,c);
        if(R>mid)update(u<<1|1,mid+1,r,L,R,c);
        pushup(u);
    }
    ull query(int u,int l,int r,int L,int R){
        if(L<=l && r<=R)return sum[u];
        int mid=(l+r)>>1;
        ull res=0;
        pushdown(u,l,r);
        if(L<=mid)res+=query(u<<1,l,mid,L,R);
        if(R>mid)res+=query(u<<1|1,mid+1,r,L,R);
        return res;
    }
    void build(int u,int l,int r){
        if(l==r){
            sum[u]=mn[u]=a[l];
            if(a[l]==0)mn[u]=inf;
            return ;
        }
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}sgt;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    sgt.build(1,1,n);
    ull lst=0;
    while(m--){
        int opt,l,r,x;
        scanf("%d%d%d",&opt,&l,&r);
        l^=lst;
        r^=lst;
        if(opt==1){
            scanf("%d",&x);
            x^=lst;
            if(x==0)continue;
            sgt.update(1,1,n,l,r,x);
        }else{
            ull res=sgt.query(1,1,n,l,r);
            lst=res&P;
            printf("%llu\n",res);
        }
    }
    return 0;
}

接着思考，这份代码为什么势能分析错了？

问题在于：if(mn[u]==c)return ;

这会导致并不是每个递归到叶子的节点都减少势能。

于是考虑维护非负严格次小值。

一个节点：

最小值大于 x，直接标记修改所有值。
无次小值且最小值为 x，直接跳过。
无次小值且最小值不为 x，直接标记修改所有值。
最小值小于 x，暴力递归。
最小值等于 x 且次小值大于 2x，直接标记修改所有非最小值。
最小值等于 x 且次小值小于等于 2x，暴力递归。

我们注意到，情况 4 递归到的整棵子树都不会再用，而且情况 4 可能会增加所有祖先的次小值。

而对于操作 6 被访问的节点，次小值至少减半。

所以这提示我们用 \log \text{非负次小值} 来作为势能。

但是我么发现如果我们令每个节点的势能是 \log n\log a_u 会导致操作 4 的复杂度可能导致势能增加，也无法均摊到势能的变化量里，所以考虑补上一项来简化。

我们令节点 u 的非负严格次小值为 a_u，则每个节点的势能可以定义为

\Phi_u=\begin{cases}1+\log n\log V+\log_2 a_u&\text{有次小值且} a_u>0\\1+\log n\log V&\text{有次小值且}a_u=0\\0&\text{无次小值}\end{cases}

然后定义 \Phi=\sum\Phi_u。

对于情况 4 递归后 \Phi 会减少 \Phi_u 也就是说 \Phi 会减少至少 1+\log n\log V，
而递归可能导致至多 \log n 个节点的值增大至多 V 也就是让至多 \log n 个节点势能增大 \log V，
所以算下来总势能减少量不小于递归点数，依旧是说情况 4 的复杂度是 O(\Delta\Phi) 的。

而对于情况 6，访问每个节点会使得 a_u 减半，也就是 \Phi_u 减 1 所以情况 6 的复杂度是 O(\Delta \Phi) 的。

所有修改处理情况 4 和情况 6 之外都会立刻退出。

所以修改操作的复杂度就是操作 4 和操作 6 的复杂度之和。

所以所有修改的复杂度总和是 \Phi。

我们注意到节点数量是 O(n) 的，而且 a_u 是 O(V) 的，所以 \Phi 是 O(n)\times O(\log n\log V)=O(n\log n\log V) 的。

然后沿用上面的“此时势能线段树的复杂度就是 O((n+q)\log n+\Phi)”，我们可以得出复杂度是 O((n+q)\log n+n\log n\log V)=O(n\log n\log V)。

然后讲个小 trick：可以直接开 unsigned long long，每个元素只会溢出一次，而且溢出后足够大。

具体实现来说，每个线段树节点维护信息：

非负最小值
非负最小值出现次数（为了方便情况 5）
区间和
区间次小值
对区间所有元素的标记
对区间非最小元素的标记

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+50,M=N<<2,P=(1<<20)-1;
ll a[N];
void updmin(ull &x,ull y,ull z){
    if(!(x=min(y,z)))x=y|z;
}
struct SegmentTree{
    ull sum[M],mn[M],Min[M],tag1[M],tag2[M];
    int cnt[M];
    void pushup(int u){
        int x=u<<1,y=u<<1|1;
        if(mn[x]>mn[y])swap(x,y);
        mn[u]=mn[x];
        if(mn[x]==mn[y]){
            updmin(Min[u],Min[x],Min[y]);
            cnt[u]=cnt[x]+cnt[y];
        }
        else updmin(Min[u],Min[x],mn[y]),cnt[u]=cnt[x];
        sum[u]=sum[x]+sum[y];
    }
    void apply1(int u,int len,ull c){
        sum[u]-=len*c;
        mn[u]-=c;
        if(Min[u])Min[u]-=c;
        tag1[u]+=c;
    }
    void apply2(int u,int len,ull c){
        sum[u]-=(len-cnt[u])*c;
        if(Min[u])Min[u]-=c;
        tag2[u]+=c;
    }
    void apply(int u,int len,ull val,ull c){
        if(mn[u]==val)apply2(u,len,c);
        else apply1(u,len,c);
    }
    void pushdown(int u,int l,int r){
        int mid=(l+r)>>1;
        apply1(u<<1,mid-l+1,tag1[u]);
        apply1(u<<1|1,r-mid,tag1[u]);
        apply(u<<1,mid-l+1,mn[u],tag2[u]);
        apply(u<<1|1,r-mid,mn[u],tag2[u]);
        tag1[u]=tag2[u]=0;
    }
    void update(int u,int l,int r,int L,int R,ull c){
        if(L<=l && r<=R){
            if(mn[u]>c){
                apply1(u,r-l+1,c);
                return ;
            }
            if(!Min[u]){
                if(mn[u]!=c)apply1(u,r-l+1,c);
                return ;
            }
            if(mn[u]==c && Min[u]>c*2){
                apply2(u,r-l+1,c);
                return ;
            }
        }
        int mid=(l+r)>>1;
        pushdown(u,l,r);
        if(L<=mid)update(u<<1,l,mid,L,R,c);
        if(R>mid)update(u<<1|1,mid+1,r,L,R,c);
        pushup(u);
    }
    ull query(int u,int l,int r,int L,int R){
        if(L<=l && r<=R)return sum[u];
        int mid=(l+r)>>1;
        ull res=0;
        pushdown(u,l,r);
        if(L<=mid)res+=query(u<<1,l,mid,L,R);
        if(R>mid)res+=query(u<<1|1,mid+1,r,L,R);
        return res;
    }
    void build(int u,int l,int r){
        if(l==r){
            sum[u]=mn[u]=a[l];
            Min[u]=0;
            cnt[u]=1;
            return ;
        }
        int mid=(l+r)>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}sgt;
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    sgt.build(1,1,n);
    ull lst=0;
    while(m--){
        int opt,l,r,x;
        scanf("%d%d%d",&opt,&l,&r);
        l^=lst;
        r^=lst;
        if(opt==1){
            scanf("%d",&x);
            x^=lst;
            if(x==0)continue;
            sgt.update(1,1,n,l,r,x);
        }else{
            ull res=sgt.query(1,1,n,l,r);
            lst=res&P;
            printf("%llu\n",res);
        }
    }
    return 0;
}

AC记录

后记

笔者一直不会势能线段树，然后因为做过上帝造题七分钟2，然后一直犯唐觉得自己会了。

但是我现在也没法说我会了（因为我也就看过 4 到题啊）。

所以如果有有价值的势能线段树题目欢迎评论区回复。