标记永久化与线段树合并

· · 个人记录

0. 前置知识

  1. 对线段树有一定了解

  2. 了解啥是线段树合并/主席树

  3. 都不用很熟练

OK? Then, let's go !

1. 标记永久化

区间修改好鬼畜啊 qwq 用线段树/分块就得学习懒标记的思想，用树状数组就得使用奇怪的差分技巧，区间查询又麻烦得要命

而且区间改一用到二维区间上……大办要玩脱，要么维护麻烦常数大（或者干脆还没办法维护），要么方法巧妙难想

想写四分树？抱歉复杂度错的单次 O(n) [ 注：n 是边长规模 ]

标记永久化就是处理区间问题的一个思想，能维护一些高维区间信息

但是作用有限哦 qwq 高维就不会让你轻易瞎搞了

(1) 那么啥是标记永久化

跟懒标记思想类似，在区间上打上标记，表示这个区间受到了 balabala 的修改

可是懒标记就相对来说可“累”了，为什么呢，因为懒标记有 pushdown 操作

现在某个标记在线段树上的区间结点 A，我访问到了 A，同时想访问 A 的儿子(们)

为了使得儿子(们)也受到了这个标记的影响，标记就得很费劲地通过懒标记下放转移到儿子上，再计算对儿子的影响。如此看来，懒标记总是跑来跑去的，是不是有些累呢？

不过现在懒标记学聪明了 （更懒了），它们决定待在结点上不动，还能保证答案不出问题

先来定义一些东西吧，data 指的是一个结点真正要维护的信息，LT 指的是修改的标记

const int MAXN=1e5;

struct SegTree
{
    int data,LT;
}node[(MAXN<<2)+5];

先来看看修改

  1. 修改区间完全覆盖线段树区间时 不对 data 进行修改 只是单纯地对 LT 进行累加

  2. 修改区间不完全覆盖线段树区间时 计算重合部分对 data 的影响 不改变 LT

然后是查询

  1. 但凡访问到任意一个结点，计算此结点 LT 对查询的影响

  2. 查询区间完全覆盖线段树区间时，对答案增加 data

这就是永久化后懒标记们的策略

这么做并不会出错，粗略一分析，被查询区间覆盖的线段树区间头顶上所有的 LT 的影响都已经被计算过了，也就是完全覆盖到它的修改对它的影响已经被考虑到了

而没有完全覆盖到它的修改，都以修改 data 的方式被考虑到了

而整个过程，LT 一直在度假

不过标记永久化的一部分局限性已经能在此看出来了，当修改操作与查询信息不兼容时就要崩溃

比如区间赋值+区间和查询，因为在对没有被完全覆盖的结点的 data 进行修改时，并不知道产生了多少改变。但是懒标记就能轻松解决。标记永久化的局限性是由于不完全覆盖区间的未知信息造成的，不过在某些情况下使它起死回生 [ 懒那么一下太难了]

(2) 例题

【模板】线段树 1

首先是最简单的板子题的标记永久化写法

#include<bits/stdc++.h>
#define Lson (now<<1)
#define Rson (now<<1|1)
using namespace std;

typedef long long ll;

const int MAXN=1e5;

int n,m;
ll sum[(MAXN<<2)+5],LT[(MAXN<<2)+5];

void Build(int now,int L,int R)
{
    if(L==R) {scanf("%lld",&sum[now]);return;}
    int mid=(L+R)>>1;
    Build(Lson,L    ,mid);
    Build(Rson,mid+1,R  );
    sum[now]=sum[Lson]+sum[Rson];
}

void Plus(int now,int L,int R,int QL,int QR,ll v)
{
    if(QL<=L && R<=QR) {LT[now]+=v;return;}
    sum[now]+=(QR-QL+1)*v;
    int mid=(L+R)>>1;
    if(QR<=mid) Plus(Lson,L,mid,QL,QR,v);
    else if(QL>mid) Plus(Rson,mid+1,R,QL,QR,v);
    else Plus(Lson,L,mid,QL,mid,v),Plus(Rson,mid+1,R,mid+1,QR,v);
}

ll GetSum(int now,int L,int R,int QL,int QR)
{
    ll cnt=(QR-QL+1)*LT[now];
    if(QL<=L && R<=QR) return sum[now]+cnt;
    int mid=(L+R)>>1;
    if(QR<=mid) cnt+=GetSum(Lson,L,mid,QL,QR);
    else if(QL>mid) cnt+=GetSum(Rson,mid+1,R,QL,QR);
    else cnt+=GetSum(Lson,L,mid,QL,mid)+GetSum(Rson,mid+1,R,mid+1,QR);
    return cnt;
}

int main()
{
    scanf("%d %d",&n,&m);
    Build(1,1,n);
    ll k;
    for(int opt,x,y;m--;)
    {
        scanf("%d %d %d",&opt,&x,&y);
        if(opt==1)
        {
            scanf("%lld",&k);
            Plus(1,1,n,x,y,k);
        }
        else printf("%lld\n",GetSum(1,1,n,x,y));
    }
    return 0;
}

全程没有 pushdown 没有 pushup，没有完全覆盖关系时重合部分的影响以乘法来完成

[POI2006]TET-Tetris 3D

强制在线二区间赋值区间最大值查询

经典的树套树标记永久化。由于是二维的，我们选择用一棵线段树维护 Y轴区间，而对于每个 Y轴区间，我们再开线段树维护 X轴的区间。

第一维线段树每个结点要开两个第二维的线段树，一个称为标记树，一个称为数据树（怎么叫他们随便啦，这里就这么叫了），简称 LT_Tree 和 data_Tree，定义跟之前类似

区间赋值时对第一维没有完全覆盖关系的 data_Tree 进行区间取 max（第二维就随便用不用标记永久化了），完全覆盖时对 LT_Tree 区间取 max

区间查询最大值时，对于路过的每一个 LT_Tree 进行区间最大值查询对答案进行更新。完全覆盖时还要再跟 data_Tree 做答案更新，复杂度 O(n \log^2 n)

但是这是有局限性的，赋值操作得满足 单调不降 才能保证没有错误，因为这样会让区间 max 值单调不降，使得区间赋值得以转换为区间取 max

#include<bits/stdc++.h>
#define Lson (now<<1)
#define Rson (now<<1|1)
#define mid ((L+R)>>1)
using namespace std;

const int Size=1e3;

int D,S,n;

struct SegTree
{
    int maxn[(Size<<2)+5],LT[(Size<<2)+5];
    int cnt;
    void Assis(int now,int L,int R,int QL,int QR,int val)
    {
        if(QR<L || R<QL) return;
        maxn[now]=max(maxn[now],val);
        if(QL<=L && R<=QR) {LT[now]=max(LT[now],val);return;}
        Assis(Lson,L    ,mid,QL,QR,val);
        Assis(Rson,mid+1,R  ,QL,QR,val);
    }
    void Ask(int now,int L,int R,int QL,int QR)
    {
        if(QR<L || R<QL) return;
        if(maxn[now]<=cnt) return;
        if(QL<=L && R<=QR) {cnt=maxn[now];return;}
        cnt=max(cnt,LT[now]);
        Ask(Lson,L    ,mid,QL,QR);
        Ask(Rson,mid+1,R  ,QL,QR);
    }
    int GetMax(int QL,int QR)
    {
        cnt=0;
        Ask(1,1,D,QL,QR);
        return cnt;
    }
};

struct ToT
{
    SegTree maxn[(Size<<2)+5],LT[(Size<<2)+5];
    int ans;
    void Assis(int now,int L,int R,int QU,int QD,int QL,int QR,int val)
    {
        if(QD<L || R<QU) return;
        maxn[now].Assis(1,1,D,QL,QR,val);
        if(QU<=L && R<=QD)
        {
            LT[now].Assis(1,1,D,QL,QR,val);
            return;
        }
        Assis(Lson,L    ,mid,QU,QD,QL,QR,val);
        Assis(Rson,mid+1,R  ,QU,QD,QL,QR,val);
    }
    void Ask(int now,int L,int R,int QU,int QD,int QL,int QR)
    {
        if(QD<L || R<QU) return;
        int cnt=maxn[now].GetMax(QL,QR);
        if(cnt<=ans) return;
        if(QU<=L && R<=QD) {ans=cnt;return;}
        ans=max(ans,LT[now].GetMax(QL,QR));
        Ask(Lson,L    ,mid,QU,QD,QL,QR);
        Ask(Rson,mid+1,R  ,QU,QD,QL,QR);
    }
    int GetMax(int QU,int QD,int QL,int QR)
    {
        ans=0;
        Ask(1,1,S,QU,QD,QL,QR);
        return ans;
    }
}mapn;

int main()
{
    scanf("%d %d %d",&D,&S,&n);
    for(int d,s,w,x,y,temp;n--;)
    {
        scanf("%d %d %d %d %d",&d,&s,&w,&x,&y);
        temp=mapn.GetMax(y+1,y+s,x+1,x+d);
        mapn.Assis(1,1,S,y+1,y+s,x+1,x+d,temp+w);
    }
    printf("%d\n",mapn.GetMax(1,S,1,D));
    return 0;
}

目前标记永久化先告一段落

2. 线段树合并

(1) 遍历整棵树的线段树合并

学过线段树和并/主席树的同学肯定有一种感觉：这不就是一堆线段树之间作加加减减的运算吗？

确实如此。在这里，我们定义一下同样为护区间 [1,n] 的线段树的运算：

  1. 线段树 A+B ，指的是 A 各个结点上的信息与相对应的 B 各个结点上的信息相加所得的线段树

  3. 线段树 A 与数 B 做乘法运算 A \times B 或 B \times A ，指的是 A 各个结点上的信息乘以 B 后所得的线段树

这样进行若干线性运算得到的线段树称为线段树的线性组合好中二啊

咳咳，怎么叫都行啦 qwq

那么正常的线段树合并其实是进行了若干线段树的加法：遍历两棵树 A、B 然后把 B 的值加到 A 上。但是这么做复杂度是很大的，用动态开点进行剪枝可以证明做许多题的时候，一次合并均摊下来是 O(\log n) 的

(2) 例题1

这里列几道题吧：

【模板】线段树合并

天天爱跑步

[HNOI2012]永无乡

[USACO17JAN]Promotion Counting P

[POI2011]ROT-Tree Rotations

[湖南集训]谈笑风生 注意合并与单点修改的顺序！实在不行新开结点

[APIO2012]派遣

大多题还都挺板的吧

(3) 均摊在查询里的线段树合并

还有一种合并适用于数量较小的线段树临时进行线性组合，那就是经典的主席树——静态区间 K 小值了

【模板】主席树

线段树 A-B 时，不用把整棵树都遍历一遍，询问到一个结点时计算对应的 A-B 上的值就行了

假设有 m 棵树进行线性组合，在线性组合上进行一次查询的复杂度为 O(m \log n) ，一般来说做题时 O(m)=O(\log n) 复杂度是可以接受的

(4) 例题2

Dynamic Ranking

这里是线段树套线段树+线段树合并的做法

第一维维护数列上的区间，第二维维护值域。假如要把位置 x 上的树由 A 改为 B，执行

Plus(1,1,n,1,1e9,x,A,-1);
Plus(1,1,n,1,1e9,x,B,+1);

就行啦

可以先离散化一下值域，如果想做到真正的在线，可以像我一样写，然后动态开点

对于查询 [L,R] 的 k 小值，在 [L,R] 里所有线段树的和线段树上做线段树二分就行了，复杂度 O(n \log^2 n) 注意卡常

Count on Tree

题意：树的路径上 k 小值

设这条路径上的数组的值域线段树为 A

正解就是直接用主席树做树上前缀和，再在 A=Tree_x+Tree_y-2Tree_{LCA(x,y)}+node_{LCA(x,y)} 上做线段树二分，复杂度 O(n \log n)

还有一种树剖+线段树合并的做法

设剖整棵树时遍历 x 的时间戳为 DFN_x ，剖出来的链靠近根的一端为 Head

还是要用主席树做一下前缀和，只不过是把每个结点按 DFN 排序得到的

对于每条路径上链，将 Tree_{DFN_{x}}-Tree_{DFN_{Head}-1} 加入到 A 中

特殊地，当 x,y 处在同一条链时，假设 DFN_x \geq DFN_y ，把 Tree_{DFN_x}-Tree_{DFN_y-1} 加入到 A 中

然后在 A 中线段树二分，由于链的个数是 O(\log n) 的，相当于是 O(\log n) 棵线段树组合，总复杂度 O(n \log^2 n)

3. 标记永久化+线段树合并

知识点都讲完了，直接上题吧

上帝造题的七分钟

听说线段树套线段树被卡空间了

二维区间加区间和查询

第一维线段树维护 Y轴区间，第二维 LT_Tree data_Tree 维护 X轴区间

修改时，对于没有完全覆盖的 Y轴区间，在 data_Tree [L,R] 区间加 公共长度乘以修改值；对于完全覆盖的 Y轴区间，在 LT_Tree [L,R] 区间加修改值

查询时，对于每个经过的 Y轴区间，对答案加上 LT_Tree [L,R] 的 公共长度乘以区间和；再对于完全覆盖的 Y轴区间，对答案加上 data_Tree [L,R] 的区间和

以上操作是基于线段树合并的简化版，本质上是把每棵线段树应有的系数分配到了各结点上

复杂度 O(n \log^2 n)

[ZJOI2013]K大树查询

还是一样的想法喽，获得 [L,R] 所有集合对应的值域线段树，然后在它们的和线段树 A 上二分

设没有完全覆盖时操作区间与线段树上区间的公共部分长度为 l

对于修改操作，在没有完全覆盖的区间上，在 data_Tree 的位置 c 上单点加上 l；对于完全覆盖的区间，在 LT_Tree 的位置 c 上单点加 1

对于查询操作，对于一路上经过的区间， A+=LT\_Tree \times l ；再在完全覆盖的区间上， A+=data\_Tree

然后你就获得了线段树 A

愉快地二分吧！qwq

[ 本篇文章到此结束，感谢各位阅读！ ]