Eternity

Until The End

线段树合并 & 线段树分裂

发表于 更新于 分类于 ，
本文字数： 12k 阅读时长 ≈ 11 分钟

“勇而无畏之人，在于面对不可掘凿的基土之时，开辟直达深渊的幽径。”

动态开点线段树

这种东西其实在很久以前就见识过了，不过那是一种动态开店线段树的变种，名为主席树，也就是可持久化线段树。但实际上，动态开点也可以用在普通线段树上。

首先，我们知道，一棵完全线段树的结点个数为 $4n$ ，那么其使用的空间复杂度也就是 $\mathcal O(4n)$ ，如果 $n$ 大的离谱的话，就可能会存在 $\textcolor{Blue}{\text{Memory Limit Exceeded}}$ 的情况，而我们又会发现，如果 $\mathcal O(4n)$ 的空间中，并不是每一个结点都被用到了的话，我们就没有必要去建立，而在需要使用的时候再去动态开点，这样的话，空间复杂度甚至能够小到 $\mathcal O(\log n)$ （只开了一条链），并达到了相同的效果（唯一的缺点就是有些难写，有些难调）。

再次重复，因为是动态开点，所以父子关系不再满足二倍，所以直接存储子结点编号。

示例写法

线段树一

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
const int MAXN=1e5+10;
int N,Q,Idx,Rt;
struct ST
{
    int lc,rc;
    ll val,tag,siz;
}Tr[MAXN<<2];
inline void pushUp(int p)
{
    Tr[p].val=Tr[Tr[p].lc].val+Tr[Tr[p].rc].val;
}
inline void pushDown(int p)
{
    if(Tr[p].tag)
    {
        if(Tr[p].lc) Tr[Tr[p].lc].val+=Tr[Tr[p].lc].siz*Tr[p].tag,Tr[Tr[p].lc].tag+=Tr[p].tag;
        if(Tr[p].rc) Tr[Tr[p].rc].val+=Tr[Tr[p].rc].siz*Tr[p].tag,Tr[Tr[p].rc].tag+=Tr[p].tag;
        Tr[p].tag=0;
    }
}
void modifyAdd(int &p,int l,int r,int ql,int qr,ll k)
{
    if(!p) p=++Idx;
    Tr[p].siz=r-l+1;
    if(ql<=l&&r<=qr)
    {
        Tr[p].val+=Tr[p].siz*k;
        Tr[p].tag+=k;
        return ;
    }
    pushDown(p);
    int mid=(l+r)>>1;
    if(ql<=mid) modifyAdd(Tr[p].lc,l,mid,ql,qr,k);
    if(mid<qr) modifyAdd(Tr[p].rc,mid+1,r,ql,qr,k);
    pushUp(p);
}
ll querySum(int p,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr) return Tr[p].val;
    int mid=(l+r)>>1;
    ll res=0;
    pushDown(p);
    if(ql<=mid) res+=querySum(Tr[p].lc,l,mid,ql,qr);
    if(mid<qr) res+=querySum(Tr[p].rc,mid+1,r,ql,qr);
    return res;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,Q);
    for(int i=1;i<=N;++i)
    {
        ll x;
        read(x),modifyAdd(Rt,1,N,i,i,x);
    }
    for(int opt,ql,qr;Q--;)
    {
        read(opt,ql,qr);
        if(opt==1)
        {
            ll qx;read(qx);
            modifyAdd(Rt,1,N,ql,qr,qx);
        }
        else write(querySum(Rt,1,N,ql,qr),'\n');
    }
    return 0;
}
/*
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
*/

然后你就会发现在这种近乎开满的情况下，动态开点和完全线段树在时间，空间，码量上都差别不大，甚至还要难写一点。但是，如果是对于一些比较特殊的区间问题，动态开点将会派上大用场。

线段树合并

顾名思义，把两棵线段树合并在一起，和 $\text{Fhq-Treap}$ 不同，这里的合并，仅仅指权值合并，表示区间是相同的。即对于区间 $[l,r]$ ，合并之后的权值就是 $Tr[p1].val+Tr[p2].val$ ，但这两棵线段树表示的依然是 $[l,r]$ 区间。

结果会发现，如果是完全线段树的话，我们递归合并不如直接扫一遍线段树数组来合并。所以说，线段树合并在完全线段树的运用下就是毫无作用的，这也是为什么在这篇文章的前面我们会介绍动态开点线段树，因为线段树合并一般都用在动态开点上（且用于值域类线段树），时间复杂度在 $\log$ 级别的。

离线破结式合并

假设现在有两棵动态开点线段树，记为 $Tr_a,Tr_b$ ，离线破结式合并的优点在于不需要申请额外的空间，直接把 $Tr_b$ 粘贴到 $Tr_a$ 上，但是，这样的合并会破坏掉 $Tr_b$ 的结构，从而影响之后的操作，仅支持离线操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int merge(int p1,int p2,int l,int r)
{
    if(!p1) return p2;
    if(!p2) return p1;
    if(l==r)
    {
        Tr[p1].cnt+=Tr[p2].cnt;
        Tr[p1].val=l;
        return p1;
    }
    int mid=(l+r)>>1;
    Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    pushUp(p1);
    return p1;
}

在线动态开点式合并

顾名思义，对于合并 $Tr_a,Tr_b$ ，我们视作是新建一棵线段树 $Tr_c$ ，但是记录的信息就是 $Tr_a$ 和 $Tr_b$ 的信息之和。这样做的优点就是可以支持在线操作和可持久化（回溯操作），而缺点也是显然的，那就是空间爆炸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int merge(int p1,int p2,int l,int r)
{
    if(!p1) return p2;
    if(!p2) return p1;
    int rt=++Idx;
    if(l==r)
    {
        Tr[rt].cnt=Tr[p1].cnt+Tr[p2].cnt;
        Tr[rt].val=l;
        return rt;
    }
    int mid=(l+r)>>1;
    Tr[rt].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),Tr[rt].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    pushUp(rt);
    return rt;
}

例题

P3605

其实我觉得这道题更适合练手一些。毕竟不涉及其它操作，而且线段树存储的参数也只有一个。

需要注意的是，动态开点线段树一般会搭配离散化来使用，而且其空间一般而言都需要到 $\mathcal O(n\log n)$ 甚至更多，一般而言，就开 MAXN<<4 或者 MAXN<<5 就差不多。否则会 $\textcolor{darkblue}{\text{Time Limit Exceeded}}$ 和 $\textcolor{Purple}{\text{Runtime Error}}$ 双倍快乐。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
const int MAXN=1e5+10;
int N,Nums[MAXN],Val[MAXN],Idx,M,Rt[MAXN];
struct ST
{
    int lc,rc,val;
}Tr[MAXN<<5];
inline void pushUp(int p)
{
    Tr[p].val=Tr[Tr[p].lc].val+Tr[Tr[p].rc].val;
}
void modifyX(int &p,int x,int l,int r)
{
    if(!p) p=++Idx;
    if(l==r)
    {
        ++Tr[p].val;
        return ;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modifyX(Tr[p].lc,x,l,mid);
    else modifyX(Tr[p].rc,x,mid+1,r);
    pushUp(p);
}
int querySum(int p,int l,int r,int ql,int qr)
{
    if(ql>qr) return 0;
    if(ql<=l&&r<=qr) return Tr[p].val;
    int mid=(l+r)>>1,res=0;
    if(ql<=mid) res+=querySum(Tr[p].lc,l,mid,ql,qr);
    if(mid<qr) res+=querySum(Tr[p].rc,mid+1,r,ql,qr);
    return res;
}
int merge(int p1,int p2,int l,int r)
{
    if(!p1) return p2;
    if(!p2) return p1;
    if(l==r)
    {
        Tr[p1].val+=Tr[p2].val;
        return p1;
    }
    int mid=(l+r)>>1;
    Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),
    Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    pushUp(p1);return p1;
}
struct G
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total,ans[MAXN];
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
void dfsTree(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Rt[x]=merge(Rt[x],Rt[v],1,M);
    }
    ans[x]=querySum(Rt[x],1,M,Val[x]+1,M);
    modifyX(Rt[x],Val[x],1,M);
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);Idx=N;
    for(int i=1;i<=N;++i) read(Val[i]),Nums[i]=Val[i],Rt[i]=i;
    std::sort(Nums+1,Nums+1+N);
    M=std::unique(Nums+1,Nums+N+1)-Nums-1;
    for(int i=1;i<=N;++i) Val[i]=std::lower_bound(Nums+1,Nums+M+1,Val[i])-Nums;
    for(int i=2,fa;i<=N;++i)
    {
        read(fa);
        addEdge(fa,i);
    }
    dfsTree(1,-1);
    for(int i=1;i<=N;++i) write(ans[i],'\n');
    return 0;
}
/*
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
*/

CF600E

对于每一个结点建立一棵动态开点权值线段树，然后维护当前结点（肯定只有一种颜色）的答案和，然后从叶结点向上合并并更新答案即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
const int MAXN=1e5+10,MAXTREE=3e6+10;
int N,Idx,MaxCol;
struct ST
{
    int lc,rc;
    ll val,cnt,ans;
}Tr[MAXTREE];
int Col[MAXN],Rt[MAXN];
ll ans[MAXN];
inline void extend(int a,int b)
{
    Tr[a].val=Tr[b].val,Tr[a].cnt=Tr[b].cnt,Tr[a].ans=Tr[b].ans;
}
inline void pushUp(int p)
{
    if(Tr[Tr[p].lc].cnt>Tr[Tr[p].rc].cnt) extend(p,Tr[p].lc);
    else if(Tr[Tr[p].lc].cnt<Tr[Tr[p].rc].cnt) extend(p,Tr[p].rc);
    else extend(p,Tr[p].lc),Tr[p].ans+=Tr[Tr[p].rc].ans;
}
int modifyCol(int p,int c,int l,int r)
{
    if(!p) p=++Idx;
    if(l==r)
    {
        Tr[p].val=l,++Tr[p].cnt,Tr[p].ans=l;
        return p;
    }
    int mid=(l+r)>>1;
    if(c<=mid) Tr[p].lc=modifyCol(Tr[p].lc,c,l,mid);
    else Tr[p].rc=modifyCol(Tr[p].rc,c,mid+1,r);
    pushUp(p);
    return p;
}
int merge(int p1,int p2,int l,int r)
{
    if(!p1) return p2;
    if(!p2) return p1;
    if(l==r)
    {
        Tr[p1].cnt+=Tr[p2].cnt;
        Tr[p1].val=Tr[p1].ans=l;
        return p1;
    }
    int mid=(l+r)>>1;
    Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    pushUp(p1);
    return p1;
}
struct G
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=(G){Head[u],v};Head[u]=Total;
    Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
void dfsTree(int x,int last)
{
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Rt[x]=merge(Rt[x],Rt[v],1,MaxCol);
    }
    Rt[x]=modifyCol(Rt[x],Col[x],1,MaxCol);
    ans[x]=Tr[Rt[x]].ans;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);Idx=N;
    for(int i=1;i<=N;++i) read(Col[i]),Rt[i]=i,checkMax(MaxCol,Col[i]);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);addEdge(u,v);
    }
    dfsTree(1,-1);
    for(int i=1;i<=N;++i) write(ans[i],' ');
    return 0;
}
/*
4
1 2 3 4
1 2
2 3
2 4
*/

雨天的尾巴

名副其实的线段树合并模板题。

单独写了一篇博客

P3521

有些思考难度，至少我没有做出来。

因为读入是按照递归读入的，所以也考虑在读入的时候处理子树，并最后递归得到答案。考虑当前子树对整棵树的影响，记录 $spa$ 表示当前左右子树不交换得到的逆序对数，$spb$ 表示当前子树交换的逆序对数，最后统计较小值即可。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int MAXN=1e6+10;
int N,Idx;
struct ST
{
    int lc,rc;
    ll val;
}Tr[MAXN<<5];
int Rt[MAXN],Lvs;
ll spa,spb,ans;
void modifyX(int &p,int l,int r,ll x)
{
    if(!p) p=++Idx;
    ++Tr[p].val;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) modifyX(Tr[p].lc,l,mid,x);
    else modifyX(Tr[p].rc,mid+1,r,x);
}
int merge(int p1,int p2,int l,int r)
{
    if(!p1) return p2;
    if(!p2) return p1;
    Tr[p1].val+=Tr[p2].val;
    if(l==r) return p1;
    int mid=(l+r)>>1;
    spa+=1ll*(Tr[Tr[p1].rc].val*Tr[Tr[p2].lc].val),
    spb+=1ll*(Tr[Tr[p1].lc].val*Tr[Tr[p2].rc].val);
    Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc,l,mid),
    Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc,mid+1,r);
    return p1;
}
void solve(int &p)
{
    int x;read(x);
    if(x)
    {
        p=++Lvs;
        modifyX(Rt[Lvs],1,N,x);
        return ;
    }
    int lc,rc;
    solve(lc),solve(rc);
    spa=spb=0;
    merge(Rt[lc],Rt[rc],1,N);
    ans+=std::min(spa,spb),p=lc;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    int p;solve(p);
    write(ans);
    return 0;
}
/*
3
0
0
3
1
2
*/

线段树分裂

顾名思义，当维护整棵线段树十分困难的时候，考虑拆分成多棵线段树分别维护，形式上线段树合并的逆操作。

可以联想 $\text{Fhq-Treap}$ 的写法中也有 $\text{merge}$ 和 $\text{split}$ 操作，也可以大致猜到线段树分裂的方式。

子树大小分裂 / 排名分裂

一般而言，线段树分裂使用的范围也是动态开点值域线段树，所以呢，分裂形式与 $\text{Fhq-Treap}$ 一致，分成 $[1,k-1][k,N]$ 两部分，俗称按权值分裂，或者排名分裂。

首先说按排名分裂，即分裂出第 $k$ 个之后的数（可重），这里设原来的线段树为 $p_1$ ，分裂出的线段树为 $p_2$ 。

1
2
3
4
5
6
7
8
9
10
void split(int p1,int &p2,int k)
{
    if(!p1) return ;
    p2=newNode();
    ll v=Tr[Tr[p1].lc].val;
    if(v<k) split(Tr[p1].rc,Tr[p2].rc,k-v);
    else std::swap(Tr[p1].rc,Tr[p2].rc);
    if(v>k) split(Tr[p1].lc,Tr[p2].lc,k);
    Tr[p2].val=Tr[p1].val-k,Tr[p1].val=k;
}

这个思路类似于查找区间第 $k$ 小值，可以类比理解。

例题

P5494

一个一个分析操作，第一个操作，就是按权值分裂两次并合并第一三个，对于如何把排名分裂转换为权值分裂，我们可以用到操作 $3$ ，首先查找 $[1,x-1]$ 的个数，就知道了 $x$ 的排名了，同理。

注意：不！要！把！下！标！打！错！了！

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
const int MAXN=1e6+10;
int N,Q;
struct SegmentTree
{
    int Rt[MAXN],Idx=0,Coll=1;
    int pool[MAXN],popCnt=0;
    struct ST
    {
        int lc,rc,val;
    }Tr[MAXN<<5];
    inline int newNode()
    {
        return popCnt?pool[popCnt--]:++Idx;
    }
    inline void del(int p)
    {
        pool[++popCnt]=p;
        Tr[p].lc=Tr[p].rc=Tr[p].val=0;
    }
    int merge(int p1,int p2)
    {
        if(!p1||!p2) return p1+p2;
        Tr[p1].val+=Tr[p2].val;
        Tr[p1].lc=merge(Tr[p1].lc,Tr[p2].lc),
        Tr[p1].rc=merge(Tr[p1].rc,Tr[p2].rc);
        del(p2);
        return p1;
    }
    void split(int p1,int &p2,int k)
    {
        if(!p1) return ;
        p2=newNode();
        int v=Tr[Tr[p1].lc].val;
        if(v<k) split(Tr[p1].rc,Tr[p2].rc,k-v);
        else std::swap(Tr[p1].rc,Tr[p2].rc);
        if(v>k) split(Tr[p1].lc,Tr[p2].lc,k);
        Tr[p2].val=Tr[p1].val-k;Tr[p1].val=k;
    }
    void modifyX(int &p,int l,int r,int v,int k)
    {
        if(!p) p=newNode();
        Tr[p].val+=k;
        if(l==r) return ;
        int mid=(l+r)>>1;
        if(v<=mid) modifyX(Tr[p].lc,l,mid,v,k);
        else modifyX(Tr[p].rc,mid+1,r,v,k);
    }
    int queryCnt(int p,int l,int r,int ql,int qr)
    {
        if(qr<l||r<ql) return 0;
        if(ql<=l&&r<=qr) return Tr[p].val;
        int mid=(l+r)>>1;
        return queryCnt(Tr[p].lc,l,mid,ql,qr)+queryCnt(Tr[p].rc,mid+1,r,ql,qr);
    }
    int queryKth(int p,int l,int r,int k)
    {
        if(l==r) return l;
        int mid=(l+r)>>1;
        if(Tr[Tr[p].lc].val>=k) return queryKth(Tr[p].lc,l,mid,k);
        else return queryKth(Tr[p].rc,mid+1,r,k-Tr[Tr[p].lc].val);
    }
    inline void move()
    {
        int p,x,y,Extra=0;read(p,x,y);
        int q1=queryCnt(Rt[p],1,N,1,y),q2=queryCnt(Rt[p],1,N,x,y);
        split(Rt[p],Rt[++Coll],q1-q2);
        split(Rt[Coll],Extra,q2);
        Rt[p]=merge(Rt[p],Extra);
    }
    inline void merge()
    {
        int p,t;read(p,t);
        Rt[p]=merge(Rt[p],Rt[t]);
    }
    inline void modifyX()
    {
        int x,p,q;read(p,x,q);
        modifyX(Rt[p],1,N,q,x);
    }
    inline int queryCnt()
    {
        int p,x,y;read(p,x,y);
        return queryCnt(Rt[p],1,N,x,y);
    }
    inline int queryKth()
    {
        int p,k;read(p,k);
        if(Tr[Rt[p]].val<k) return -1;
        return queryKth(Rt[p],1,N,k);
    }
    inline void insert(int x,int v)
    {
        modifyX(Rt[1],1,N,x,v);
    }
}Tree;
signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N,Q);
    for(int i=1,x;i<=N;++i) read(x),Tree.insert(i,x);
    for(int opt;Q--;)
    {
        read(opt);
        switch(opt)
        {
            case 0:Tree.move();break;
            case 1:Tree.merge();break;
            case 2:Tree.modifyX();break;
            case 3:write(Tree.queryCnt(),'\n');break;
            case 4:write(Tree.queryKth(),'\n');break;
        }
    }
    return 0;
}
/*
5 12
0 0 0 0 0
2 1 1 1
2 1 1 2
2 1 1 3
3 1 1 3
4 1 2
2 1 1 4
2 1 1 5
0 1 2 4
2 2 1 4
3 2 2 4
1 1 2
4 1 3
*/

P2824

这道题有一个简化版 $\text{CF558E A Simple Task}$ ，但如果用线段树分裂的话，就会变成加强版，这个我们之后再提。

相关文章