线段树扩展应用

l1ng21y12026 · 2025-10-30 16:12:41 · 算法·理论

线段树扩展应用

（一）区间最值操作

考虑区间 chkmin，使用 Segment tree beats。算法如下：

维护区间最大值，严格次大值，最大值出现次数。下称 f1,f2,fc。

当对区间 chkmin(v) 时：

• 若 v\ge f1，这个区间不会被修改。直接返回。

• 若 f2<v<f1，这个区间内只有最大值被修改。

  我们对最大值单独开一个标记维护。此时相当于对最大值 +(v-f1)。

• 若 v\le f2，我们递归子区间。

当只有单点修改时，时间复杂度是 O(n\log n) 的。

考虑只有 v\le f2 时递归子区间可能产生多余贡献。此时，该区间的最大值和次大值合并。也就是说，这个区间的不同值的个数 -1，然后造成了 1 的贡献。

线段树每层的不同值个数总和是 O(n) 的，\log 层合一起总共 O(n\log n) 个不同值。一次单点修改给整颗树增加 \log n 个不同值，总共最多增加 O(m\log n) 个不同值。故最多多造成 O(n\log n) 的贡献。

当有区间加时，时间复杂度是 O(n\log^2 n) 的。

一次区间加会将它作用的整区间的所有父节点的不同值个数 +1，共作用 \log 个子区间，每个子区间 \log 个祖先，总共会增加 O(m\log^2 n) 个不同值。

那么现在问题变成了：区间加，针对区间最大值加，区间历史最值，区间和。

若没有历史最值，我们可以维护区间内最大值的个数，并单独记录最大值的加标记；另外维护非最大值的加标记，那么区间和的变化量容易求出。

考虑区间历史最值，可以经典地维护最大值加标记的历史最大值，那么区间历史最值可以由之前的 max 加上加标记的历史 max 更新。

需要注意的是，在下传区间最大值加标记时，我们需要知道子区间的 max 是否是父区间的 max。我们不能直接调用值，因为可能有一个还没有被标记修改。

由于实际上只有区间最大值加，所以区间内最大值的分布在 up 之前都不改变，于是我们记录区间 max 的是否来源于 ls,rs 即可判断 ls,rs 的 max 是否是 x 的 max 即可。

开始实现，我们要维护：

ll fs[N<<2];// 区间和
int len[N<<2];// 区间长
int f1[N<<2],f2[N<<2],fc[N<<2];// 区间最大值 , 次大值 , 最大值个数
int fh[N<<2];// 区间历史最大值
bool ml[N<<2],mr[N<<2];// 区间最大值是否是 ls/rs 的最大值（即 up 时是否由 ls/rs 转移 max）
int gs1[N<<2],gh1[N<<2];// 最大值加标记 , gs1的历史最大值
int gs2[N<<2],gh2[N<<2];// 非最大值加标记 , gs2的历史最大值

然后依次考虑 up,dn 内各个值的转移更新。

inline void up(int x)
{
    fs[x]=fs[ls]+fs[rs];
    if(f1[ls]==f1[rs])
    {
        f1[x]=f1[ls];
        f2[x]=max(f2[ls],f2[rs]);
        fc[x]=fc[ls]+fc[rs];
        ml[x]=1,mr[x]=1;
    }
    else if(f1[ls]>f1[rs])
    {
        f1[x]=f1[ls];
        f2[x]=max(f2[ls],f1[rs]);
        fc[x]=fc[ls];
        ml[x]=1,mr[x]=0;
    }else{
        f1[x]=f1[rs];
        f2[x]=max(f2[rs],f1[ls]);
        fc[x]=fc[rs];
        ml[x]=0,mr[x]=1;
    }
    fh[x]=max(fh[ls],fh[rs]);
}
inline void dn(int x)
{
    if(gh1[x]==-inf)return;
    fs[x]+=1ll*gs1[x]*fc[x]+1ll*gs2[x]*(len[x]-fc[x]);
    fh[x]=max(fh[x],f1[x]+gh1[x]);
    f1[x]+=gs1[x];
    f2[x]+=gs2[x];
    if(x<=(n<<1))
    {
        if(ml[x])
        {
            gh1[ls]=max(gh1[ls],gs1[ls]+gh1[x]);
            gs1[ls]+=gs1[x];
        }else{
            gh1[ls]=max(gh1[ls],gs1[ls]+gh2[x]);
            gs1[ls]+=gs2[x];
        }
        gh2[ls]=max(gh2[ls],gs2[ls]+gh2[x]);
        gs2[ls]+=gs2[x];
        if(mr[x])
        {
            gh1[rs]=max(gh1[rs],gs1[rs]+gh1[x]);
            gs1[rs]+=gs1[x];
        }else{
            gh1[rs]=max(gh1[rs],gs1[rs]+gh2[x]);
            gs1[rs]+=gs2[x];
        }
        gh2[rs]=max(gh2[rs],gs2[rs]+gh2[x]);
        gs2[rs]+=gs2[x];
    }
    gs1[x]=gs2[x]=0,gh1[x]=gh2[x]=-inf;
}
void bld(int x=1,int l=1,int r=n)
{
    gs1[x]=gs2[x]=0,gh1[x]=gh2[x]=-inf;
    len[x]=r-l+1;
    if(l==r)fs[x]=a[l],f1[x]=a[l],f2[x]=-inf,fc[x]=1,fh[x]=a[l];
    else bld(ls,l,mid),bld(rs,mid+1,r),up(x);
}
void pls(int le,int ri,int v,int x=1,int l=1,int r=n)
{
    if(le<=l&&r<=ri)
    {
        gs1[x]+=v,gh1[x]=max(gh1[x],gs1[x]);
        gs2[x]+=v,gh2[x]=max(gh2[x],gs2[x]);
        dn(x);
        return;
    }
    dn(ls),dn(rs);
    if(le<=mid)pls(le,ri,v,ls,l,mid);
    if(mid<ri)pls(le,ri,v,rs,mid+1,r);
    up(x);
}
void cmn(int le,int ri,int v,int x=1,int l=1,int r=n)
{
    if(v>=f1[x])return;
    if(le<=l&&r<=ri&&f2[x]<v)
    {
        gs1[x]+=v-f1[x],gh1[x]=max(gh1[x],gs1[x]);
        dn(x);
        return;
    }
    dn(ls),dn(rs);
    if(le<=mid)cmn(le,ri,v,ls,l,mid);
    if(mid<ri)cmn(le,ri,v,rs,mid+1,r);
    up(x);
}

可以看一下 chkmin 的写法。只在满足 sec<v<max 时针对 max 进行修改。剩下的情况递归或者返回。

例题

P6242 【模板】线段树 3（区间最值操作、区间历史最值）。

（二）历史最值

有的历史最值较为简单，可以直接标记维护，无需矩乘分析。

标记 gs,gh。gh 记录 gs 的最值。

tree_history[x]=max(tree_history[x],tree_val[x]+tag_history[x]);
tree_val[x]+=tag_val[x];

tag_history[ls]=max(tag_history[ls],tag_val[ls]+tag_history[x]);
tag_val[ls]+=tag_val[x];

考虑前后合并即可。

像区间 chkmin 区间加这种，可以转化为只有区间加，我们就可以方便地直接维护。

但是有的题目有很多操作（区间加、区间赋值），还要维护历史最值，那我们使用矩乘分析。

例题

P4314 CPU 监控：区间加、区间赋值、历史最值。

使用 (1,v,h) 表示区间最大值，区间历史最值。

定义广义矩阵乘法 (+,\max)。考虑区间加 k：

构造时，A_{i,j} 表示 i\to j 的贡献，即左边 [1,v,h] 的第 i 个，对右边 [1,v+k,\max(h,v+k)] 的第 j 个的贡献系数。

区间赋值 k：

注意到转移矩形只有右上角四个位置有值，设为 (a,b,c,d)。即四个标记。

可以提取带入得出 f 与标记的合并式：

提取得 (v,h)\odot (a,b,c,d)\to (\max(a,c+v),\max(b,d+v,h))。

同样可以提取标记之间的合并式：

提取得 (a,b,c,d)\odot (x,y,z,w)\to (\max(x,a+z),\max(y,a+w,b),c+z,\max(c+w,d)。

注意判断 -inf-inf 爆 int。

（三）历史和

历史标记本质上是矩阵，代表了各树上值在操作作用下的互相转移关系，A_{i,j} 表示 i\to j 的贡献。

用 (1,v,h) 表示树上点值 f 的信息。v 为点的值，h 为 v 的历史和。

考虑修改时 f 的转移，并用矩阵表示。矩乘为 (\times ,+) 矩乘。

赋值 x：

由于A_{i,j} 表示 i\to j 的贡献，我们可以得出 1 对 1,\_,\_ 的贡献系数为 1,x,0，剩下同理。

加 x：

更新 t 次历史和：同理地考虑 i\to j 的贡献。

不像历史最值，历史和要求所有位置都要更新（不止当前修改的位置）所以每次要对全局打一个更新历史和的标记。

表示信息的位置只有右上角的 4 个，令它们为 (a,b,c,d)（其实它们代表标记）

可以提取 f 与标记的合并式：

考虑转移矩阵的合并，有：

根据上面两条式子，可以提取 f 与标记，标记与标记之间的合并式。