线段树知识整合

本文最后更新于：2024年3月7日 下午

线段树是常用的用来维护 区间信息 的数据结构。

线段树可以在 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
（基础的入门操作就不说了

动态开点线段树

一般的线段树我们需要开四倍空间，但是某些时候空间限制无法直接开这么大的空间，这时需要动态开点来节省空间。
动态开点指的是在建树时只建立所需区间的部分，这样空间复杂度会降低到 。
实现的话需要记录左右儿子的id，需要用新点时候开。
代码大概是这样：

1
2
3
4
5
6
7
8
inline void update(int &now,int l,int r,int x){
    if(!now)now=++kl;//if "now" is a new point,create it.
    if(l==r){return;}//Do whatever you want
    int mid=(l+r)>>1;
    if(x<=mid)update(lc[now],l,mid,x,val);
    else update(rc[now],mid+1,r,x,val);
    pushup(now);// upload it's elements.
}

很简单，并且用处很大。

动态开点的合并代码：

1
2
3
4
5
6
7
8
9
int merge(int x,int y)
{
    if(!x)return y;//if anynode isn't exist,return the other.
    if(!y)return x;
    sum[x]+=sum[y];//add the other node's information into this node
    lc[x]=merge(lc[x],lc[y]);
    rc[x]=merge(rc[x],rc[y]);
    return x;//only return one ,and it means delate the otherone
}

主席树

可以理解为很多棵线段树，假如每棵线段树都建一棵完整的树呢么会有空间问题，假如有一些部分相同，我们建树的时候就可以直接使用这部分，这需要用到动态开点的手法。
实际上就是每次动态开点的时候连接到之前版本的节点上。
一般用的主席树就是大概是这样：例题,常规的历史版本咨询。
这是源码：

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
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
    int data=0,w=1;char ch=0;
    while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar();
    return data*w;
}
int a[MAXN*20],n,m,rt[MAXN*20],lc[MAXN*20],rc[MAXN*20],val[MAXN*20],kl=0;
inline void build(int &now,int l,int r)
{
    now=++kl;//开点
    if(l==r){val[now]=a[l];return;}
    int mid=(l+r)>>1;
    build(lc[now],l,mid);build(rc[now],mid+1,r);
}
inline void insert(int &now,int pre,int l,int r,int x,int v)
{
    now=++kl;
    lc[now]=lc[pre];rc[now]=rc[pre];val[now]=val[pre];
    if(l==r){val[now]=v;return;}
    int mid=(l+r)>>1;
    if(x<=mid)insert(lc[now],lc[pre],l,mid,x,v);
    else insert(rc[now],rc[pre],mid+1,r,x,v);
}
inline int query(int &now,int l,int r,int x)
{
    if(l==r)return val[now];
    int mid=(l+r)>>1;
    if(x<=mid)return query(lc[now],l,mid,x);
    else return query(rc[now],mid+1,r,x);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    build(rt[0],1,n);
    for(int i=1,jkl,pre,l;i<=m;i++)
	{
        pre=read(),jkl=read(),l=read();
        if(jkl==1)
		{
            int v=read();
            insert(rt[i],rt[pre],1,n,l,v);//保存修改后的版本
        }
		else 
		{
            printf("%d\n",query(rt[pre],1,n,l));
			rt[i]=rt[pre];
        }
    }
    return 0;
}

假如要做区间第k大，可以把每棵线段树变为权值线段树，然后按照数列顺序插入主席树，求[l,r]区间的第k大就是同时在l和r这两个版本的书上找，类似前缀和的思想，找到相差k的子树再搞就行了。
（不过这个我一般都是用树状数组来搞的，比主席树好写多了，就不写主席树写法了。

一些奇怪的用法

后面的不太清楚到底是一种新算法还只是思路的延申，就记录下来充作小点。

差分主席树？（雾

这中写法我没找到确切的算法介绍，是在看2020icpc沈阳j时看他人代码发现的，感觉是一种奇怪的主席树写法，但是和以前碰到的主席树用法不太一样。又感觉像是把差分数组建成了一颗树，觉得很妙，记了下来。
这道题题意大体是这样：给你一个初始为0的序列，一个操作是将区间[l,r]的所有值为v的数加一，另一个操作是询问区间[l,r]的最值。
以下是算法详解（具体看源码）
这个算法也是建立了多棵树，第i棵树的[l,r]区间数的个数减去第i-1棵树的[l,r]区间数的个数表示第值为i的数的存在情况，最开始每棵树都是包含区间[1,n]的完整的线段树，然后当我们执行一次修改操作（将[l,r]的所有值为v的数加一）时，找到第v棵树，第v-1棵树所代表的区间，然后取差。假如差为0代表这个区间无v直接返回，假如有则新建节点接到第v棵树上（负责把第v棵树的这个区间“归零”）。
很显然，我们构造的这个区间在不同树之间是一个严格不减的“区间序列”（就是呢个意思，你懂. . .），每次操作相当于把第i棵树这个区间清零，以及让i+1这颗树加上第i棵树的答案。（由差分易得：将一个数加到后面的呢个数上只需要把这个数在差分序列里对应的呢个数变为前一项即可。）
用差分的一个好处就是可以在查询的时候用二分来找到一个区间的最大的v，由于我们建立的这个“差分主席树”的性质，假如一个区间最大值为v，呢么v以后的区间和不变并且v以前的区间和单调不减。（我最开始想用单纯的主席树搞的，但是就是卡在了查询这一步。加了差分这一性质就让这题可做了。）
以下是源码（看的呢份源码写的多了很多不必要的东西. .. 可读性很差，便删改了以下（可能是比赛代码加了些保全？））

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
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x; i<=y; ++i)
#define mid (l+r>>1)
using namespace std;
const int N=500005,M=20000005;
int n,q,ql,qr,tp,x,root[N],ls[M],rs[M],sonnum[M],tot;
   
inline int read()
{
    char ch;
    while(!isdigit(ch=getchar()));
    int x=ch-48;
    while(isdigit(ch=getchar())) x=x*10+ch-48;
    return x;
}
   
void build(int l,int r,int &rt)
{
    if(!rt) rt=++tot;
    if(l==r) {sonnum[rt]=1; return;}
    build(l,mid,ls[rt]);
    build(mid+1,r,rs[rt]);
    sonnum[rt]=sonnum[ls[rt]]+sonnum[rs[rt]];
}
   
int query(int l,int r,int rt)//求该树该区间的节点个数
{
    if(ql<=l && r<=qr) return sonnum[rt];
    if(qr<=mid) return query(l,mid,ls[rt]);
    if(ql>mid) return query(mid+1,r,rs[rt]);
    return query(l,mid,ls[rt])+query(mid+1,r,rs[rt]);
}
   
void ins(int l,int r,int &rt,int lastrt)
{
    if(sonnum[rt]-sonnum[lastrt]<=0) return;
    if(ql<=l && r<=qr) {rt=lastrt; return;}
    ++tot,ls[tot]=ls[rt],rs[tot]=rs[rt],rt=tot;
    if(ql<=mid) ins(l,mid,ls[rt],ls[lastrt]);
    if(mid<qr) ins(mid+1,r,rs[rt],rs[lastrt]);
    sonnum[rt]=sonnum[ls[rt]]+sonnum[rs[rt]];
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    n=read(),q=read();
    build(1,n,root[0]);
    rep(i,1,q) root[i]=root[0];
    rep(i,1,q)
    {
        int tp=read();ql=read(),qr=read();
        if(tp==1)
        {
            x=read();
            int lastroot=x?root[x-1]:0;
            ins(1,n,root[x],lastroot);
        }
        else
        {
            int l=0,r=q;
            while(l<=r)
            {
                int L=mid?query(1,n,root[mid-1]):0;
                int R=r>=0?query(1,n,root[r]):0;
                if(R-L) l=mid+1; else r=mid-1;
            }
            printf("%d\n",l-1);
        }
    }
    return 0;
}

线段树辅助建图

老算法了，整合一下
快速跳转