【学习笔记】线段树详解（全）

【学习笔记】线段树详解（全）

和三个同学一起搞了接近两个月的线段树，头都要炸了T_T，趁心态尚未凉之前赶快把东西记下来。。。

【目录】

一：【基础姿势】

(piao) 一下隔壁大佬的文章QAQ: (Silent)_(EAG)

基础题走起：

高档题走起：

二：【懒标记】

见隔壁：(Silent)_(EAG)

基础题走起：

高档题走起：

三：【扫~描~线~】

见隔壁：(IC)_(QQQ)

四：【权值线段树】

 QAQ:以前似乎在某个地方看到过一个叫做做权值树状数组的东西唉QWQ
  DL:其实他们都是一样的思想，只是不同的实现方式而已
 
 QAQ:可是XX在写过无数区间作业的题后，发现无论是哪一类，树状数组都比线段树快不止三倍唉QWQ
  DL:*****

权值线段树是什么？

权值线段树，顾名思义是一颗线段树。
但它和普通线段树略有不同： 普通线段树维护的是一段区间的数值的总和或最大值等等...... 而权值线段树维护的是一定范围内某个数值出现的次数。实际上它和之前的权值树状数组是一样的原理。（求逆序对也可用权值线段树实现 ）

它有什么用？

按照定义，我们可以用它对于权值进行计数，感觉有点像数位(dp)吧，求一定范围内符合要求的数的个数。权值线段树的(“)范围(”)是不定的，而(“)要求(”)一般是：在给定的数值范围内。

举个栗子：
有一个数列： (a(1,1,2,3,3,4,4,4,4,5)) 对其维护一个计数的权值线段树，树的大小就是数列的值域 ([mins～maxs])，即 ([1～5])。

红色为编号，黑色为区间，蓝色为计数

如图，在数列中：
数值 (1) 出现了 (2) 次
数值 (2) 出现了 (1) 次
数值 (3) 出现了 (2) 次
数值 (4) 出现了 (4) 次
数值 (5) 出现了 (1) 次

重要应用：

在此基础上，它还有一个很重要的作用 ：
查询某区间内第 (k) 小或第 (k) 大的值。

引理：

如果在值域范围内 (() 即 ([mins～maxs]) ())中发现有某个位置 (x)，数列中存在这个数 (x)，且使得数值范围在区间 ([mins～x]) 内的数一共有 (k) 个，那么 (x) 就是第 (k) 小的数。
反之亦然：
如果在值域范围内 (() 即 ([mins～maxs]) ())中发现有某个位置 (x)，数列中存在这个数 (x)，且使得数值范围在区间 ([x～maxs]) 内的数一共有 (k) 个，那么 (x) 就是第 (k) 大的数。

【分析】

以查询第 (k) 小为例

我们可以用一种二分的思想，当需要在某个值域范围 ([l～r]) 内查找第 (k) 小时，先计算出数值在 ([l～mid]) 以内的数的个数 (tmp)，再将其与 (k) 进行比较：

  • 如果 (tmp geqslant k)，则说明第 (k) 小的数应存在于 ([l～mid]) 这个范围。
  • 如果 (tmp leqslant k)，则说明第 (k) 小的数应存在于 ([mid+1～r]) 这个范围，而实际上就等价于在 ([mid+1～r]) 中找到第 (k-tmp) 小的数。

【Code】

#define Re register int
#define pl tree[p].PL
#define pr tree[p].PR
inline int ask(Re p,Re L,Re R,Re k){//查询第k小
    if(L==R)return L;//边界叶节点 
    Re tmp=tree[pl].g;//计算左子树(数值范围在L~mid的数)共有多少个数字 
    if(tmp>=k)return ask(pl,L,mid,k);
//左子树已经超过k个，说明第k小在左子树里面 
    else return ask(pr,mid+1,R,k-tmp);
//左子树不足k个数字，应该在右子树中找到第(k-tmp)小
}

五：【动态开点】

什么是动态开点？

动态开点用法较固定，目的也很明确：节省空间。
它的实质其实就是在空间不够的情况下，把不需要的节点变成虚点。

有什么用？

求解逆序对时可以用权值树状数组，那么如果尝试用权值线段树做的话会出现什么后果呢？

肯定是可解的。但是，由于值域大多都是 (inf) 级别的数字，况且某些比较毒瘤的在线操作还没法离散化，于是在使用权值线段树时，一般都会伴随着动态开点的使用。

如何使用？

这里引用一下一位大佬的比喻： 开局一个根，枝叶全靠给。

当要用到(一般只有修改)某个节点的信息时，就手动开一个新的节点，给它一个点的空间包括各种节点信息。而在查询中如果发现进入的节点不存在(还没开发过)，那么直接返回，不需要在查询时新建节点。

【空间复杂度】

(Q*log(inf))。其中 (Q) 为修改次数。

【Code】

（基本框架）

int cnt;
inline void sakura(Re &p,Re L,Re R,Re ???){//【???修改】
    if(!p)p=++cnt,tree[p].?=???;
//发现进入了一个空节点,新建一个节点，赋予它编号,记录基本信息 
    if(L==R){tree[p].?=???;return;}
//达到叶子节点，记录一些特殊的信息，并返回 
    Re tmp=???;//可能会在在递归之前进行一些计算来方便判断 
    if(???)sakura(pl,L,mid,???);//递归进入左子树 
    if(???)sakura(pr,mid+1,R,???);//递归进入右子树 
    tree[p].?=???;//回溯后更新信息 
}

六：【线段树合并】

什么是线段树合并？

简单来说就是将两棵线段树合并起来，并累加它们的信息。

有什么用？

线段树合并一般用于对树上信息的统计，例如：对一棵树的所有叶子节点都开一个线段树，统计信息时，将所有的儿子节点的线段树合并起来，得到父亲节点的线段树，再用其去合并统计祖先的信息。

【时间复杂度】

如果一棵线段树的所有节点都不为空（动态开点会使得虚点的存在），离散化后值域为 (n)，递归一棵线段树树的时间复杂度达到最大： (O(logn))。如果总共 (n) 棵树的所有节点都不为空，那么需要合并 (n-1) 次， 总时间复杂度达到最大： (O(n*logn))。

【Code】

inline int merge(Re p,Re q){//【线段树合并】 
    if(!p)return q;if(!q)return p;
    //当需要合并的点的其中一个编号为0时 (即为空)，返回另一个编号 
    tr[p].g+=tr[q].g,p;//把q合并到p上面去 
    pl=merge(pl,tr[q].lp);//合并左子树，并记录p点的左子树编号
    pr=merge(pr,tr[q].rp);//合并右子树，并记录p点的右子树编号
    return p;
}

基础题走起：

高档题走起：

七：【可持续化线段树—静态主席树】

来看一道经典的例题 【模板】可持久化线段树 (1) (主席树) ([3834]) (/) (K)-(th) (Number) ([P3834]) ([POJ2104]) ([SP3946])

【题目大意】

给定一个长为 (n) 的数列以及 (Q) 个查询，每次查询输入两个整数 (l),(r)，输出数列中 (l) ~ (r) 第 (K) 小的数。

【 分析】

此题有三个关键点：

  1. 求一棵数列中的第 (K) 大或第 (K) 小的数。
    解决方案：权值线段树

  2. 如果仅仅是这样，则非常好办，给出的询问是一段区间。一段长为 (n) 的数列中共有 (n(n-1)/2) 个不同的区间，如果给每个区间都开一个权值线段树，后果是：(TLE) (+) (MLE) (+) 初始化建树无从入手。
    解决方案：前缀和
    （对于原数列的每个位置都建立一个权值线段树，(p[i]) 表示第 (i) 个位置上的树的根节点编号，用 (tree[pt[i]]) 表示从第 (1) 个到第 (i) 个数这个区间中共 (i) 个数所维护成的一棵权值线段树。(message[pt[i]]=sum_{j=1}^i message[pt[j]])）

  3. 可内存还是远远不够，即使是使用了【动态开点】 (+) 离散化，值域由 (inf) 降为 (N)，每一棵权值线段树的节点数降为 (N*2)，节点，但一共有 (N) 棵树，(N*N*2) 动辄就是几十万兆内存。（做一个简单的计算：
    (200000*200000*2*4*3/1024/1024 hickapprox 305175.78125 Mb)）
    解决方案：可持续化
    由于第 (i) 棵树 (tree[pt[i]]) 与第 (i-1) 棵树 (tree[pt[i-1]]) 只有 (logn) 个节点不一样，于是只需要对第 (i-1) 棵树进行一次单点修改将 (a[i]) 加入，就变成了第 (i) 棵树。因此我们可以由已经建好第 (i-1) 棵树迅速建立起第 (i) 棵树，这也就是主席树思想的精髓所在。
    说具体点，就是让第 (i) 棵树与第 (i-1) 棵树公用一些节点（因为在这些没有发生改变的部分，它们的信息是完全相同的），在递归过程建树中，如果发现要进行【单点修改】操作的是左子树，那就让新树的右子树编号指向旧树的右子树编号（即 (tree[pt[i]].pr=tree[pt[i-1]].pr) ）然后递归进入左子树的建立，反之亦然。
    但第 (1) 棵树需要由第 (0) 棵树变化而来，当有特殊需要时，要提起把第 (0) 棵树建立完整，而道题不需要，因为第 (0) 棵树本来就为空，所以不用管。

【时间复杂度】

每次建树的过程都接近于【单点修改】， 为 (O(logn)) ,所以初始化建树的过程为 (O(nlogn)) 。

单次询问采用权值线段树中的【查询第 (k) 小】，为 (O(logn))。

总共 (Q) 次询问，为 (O(Qlogn)) 。

总时间复杂度： (O((n+Q)logn))

【空间复杂度】

如果要建立完整的第 (0) 棵树，会占用 (n*2) 个节点，每棵新树的建立都要新建 (logn) 个节点，一共有 (nlogn)。

总空间复杂度：((logn+2)*n)

【Code】

#include<algorithm>
#include<cstdio>
#define mid (L+R>>1)
#define pl tr[p].lp
#define pr tr[p].rp
#define Re register int
#define F(a,b) for(i=a;i<=b;++i)
using namespace std;
const int N=1e5+3;
int x,y,z,i,n,m,k,t,fu,cnt,a[N],b[N],pt[N];//pt[i]表示离散化后i这个位置所对应的权值树根的编号 
struct QAQ{int g,lp,rp;}tr[N<<5];//权值树，保守开一个32*N
inline void in(Re &x){//【快读】自己动手,丰衣足食... 
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();x=fu?-x:x;
}
inline int creat(Re pp,Re x,Re L,Re R){
//把上一棵权值树pp(即pt[a[i-1]])复制过来
//并在递归复制途中对x(即a[i]离散化后的位置)这个点同步进行单修操作 
    Re p=++cnt;pl=tr[pp].lp,pr=tr[pp].rp,tr[p].g=tr[pp].g+1;
    //新开一个点，并把上一个的数据复制进来，并使tr[].g++ 
    if(L==R)return p;//到达边界: L==R(即x这个位置) 
    if(x<=mid)pl=creat(tr[pp].lp,x,L,mid);//递归进入条件:单修
    else pr=creat(tr[pp].rp,x,mid+1,R);//注意tr[pp]要同时递归至左(右)子树 
    return p;
}
inline int ask(Re p,Re pp,Re L,Re R,Re k){
//查询。p为查询区间左端点的权值树根编号，pp为查询区间右端点的权值树根编号 
    if(L==R)return b[R];//边界：L==R
    Re tmp=tr[tr[pp].lp].g-tr[pl].g;//用前缀和思想计算出左子树共有多少个数字 
    if(tmp>=k)return ask(pl,tr[pp].lp,L,mid,k);//左子树已经超过k个，说明第k小在左子树里面 
    else return ask(pr,tr[pp].rp,mid+1,R,k-tmp);//左子树不足k个，应该在右子树中找第(k-tmp)小
}
int main(){
    in(n),in(k); 
    F(1,n)in(a[i]),b[i]=a[i];//复制进b[]并离散去重 
    sort(b+1,b+n+1);//【离散化】
    m=unique(b+1,b+n+1)-b-1;//【去重】 
    F(1,n)pt[i]=creat(pt[i-1],lower_bound(b+1,b+m+1,a[i])-b,1,m);
    //找出当前这个位置按权值排序后的位置x，进入建树 
    while(k--)in(x),in(y),in(z),printf("%d
",ask(pt[x-1],pt[y],1,m,z));//注意是【y】-【x-1】 
}

基础题走起：

八：【可持续化线段树—动态主席树(岂可修)】

一样的，先上例题： (Dynamic) (Rankings) ([P2617]) ([ZOJ2112]) ([BZOJ1901])

【题目大意】

在【静态主席树】的基础上加了一个【单点修改】的操作。

【分析】

回想一下，在刚刚静态线段树中用到了前缀和的思想：对于原数列的每个位置都建立一个权值线段树，用 (tree[pt[i]]) 表示从第 (1) 个到第 (i) 个数这个区间中共 (i) 个数所维护成的一棵权值线段树。

它维护的是每个位置前面的一整个大区间，而如果对某个位置 (i) 上的数进行了修改，那么从 (i) 这个位置开始以后所有的位置上存的信息都要改变（因为位置 (i) 后面的所有位置上所存的信息都包含了 (i) 的信息）。 那么一次【单点修改】的时间复杂度就是接近于 (O(nlogn)) 的，显然不能吗，满足要求。

解决方案：树（树状数组）套树

【树状数组】每一个位置 (i) 上的数据 (C[i]) 维护的信息是： (message[i]=sum_{j=i-lowbit(i)+1}^i message[j])

而【静态主席树】每一个位置 (tree[pt[i]]) 上的数据 (C[i]) 维护的是： (message[pt[i]]=sum_{j=1}^i message[pt[j]])

【树状数组】：查询 (O(logn))，修改 (O(logn))
【静态主席树 (+) 暴力】：查询 (O(logn))，修改 (O(nlogn))

实际上静态主席树慢就慢在维护的前缀和范围实在是太大了，尤其是最后一个位置，直接就是 ([1) ～ (N]) 的范围。既然如此，为什么不可以把范围缩小一点呢？如果让其维护和树状数组一样的区间，虽然查询第 (k) 小上面加了一个 (O(logn))，可【单点修改】却降下了一个 (O(logn)) ，于是整个问题的时间复杂度就降了下来，可以完美解决了。

【时间复杂度】

每次查询递归 (logn) 层，每层最多需要对 (max(lowbit(i)) hickapprox logn) 个节点进行修改，为 (O(log^2n))。

同理，【单点修改】也应该是 (O(log^2n))。

一共 (Q) 次操作，为 (O(Qlog^2n))

初始化建树是 (n) 次【单点修改】，为 (nlog^2n)

总时间复杂度为：(O((n+Q)log^2n))

【空间复杂度】

有 (Q) 次操作，如果每次操作都是【单点修改】且每次都是改的一个与之前都不同的数，那么离散化的值域为 (Q+n)。

如果要建立完整的第 (0) 棵树，会占用 (n*2) 个节点，每棵新树的建立都要新建 (log^2(Q+n)) 个节点，一共有 (nlog^2(Q+n))。

(Q) 次操作，有 (Qlog^2(Q+n))

总空间复杂度：((Q+n)*log^2(Q+n))

数据规模：

(1 leqslant N,Q leqslant 1e5)

(200000*21*21*4*3/1024/1024)

算下来大概是 (1009MB)，而跑下来实际是大约 (154.14Mb)

所以不用慌张，因为实际空间一定是远远小于理论空间的，出题人再怎么良心也不会故意弄一个卡极限的 (1000Mb) 数据出来，况且这一类毒瘤题空间限制都大得惊人。

这是洛谷的时空限制：

【Code】

#include<algorithm>
#include<cstring>
#include<cstdio>
#define mid (L+R>>1)
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
using namespace std;
const int N=2e5+3;char opt[N];
int x,y,z,n,m,T,t,fu,cnt,tl,tr,a[N],b[N],pt[N],C[N],ptl[20],ptr[20];
//ptl,ptr千万不要开N,否则memset的时候会TLE到怀疑人生 
struct QAQ{int g,lp,rp;}tree[N*400];//本应是441左右,开小一点也无所谓，因为根本用不到 
struct O_O{int l,r,k;}Q[N];//储存Q次查询的内容，方便离散化 
struct T_T{int i,x;}c[N];//离散化数组 
inline void in(int &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=fu?-x:x;
}
inline int ask_(Re L,Re R,Re k){
    if(L==R)return b[R];//注意：返回的值需要用到的是哪一个映射数组不能搞错 
    Re tmp=0;
    F(i,1,tl)tmp-=tree[tree[ptl[i]].lp].g;//计算左子树信息 
    F(i,1,tr)tmp+=tree[tree[ptr[i]].lp].g;//计算左子树信息 
    if(tmp>=k){
    	F(i,1,tl)ptl[i]=tree[ptl[i]].lp;//更新ptl,ptr所指向的节点编号 
    	F(i,1,tr)ptr[i]=tree[ptr[i]].lp;
    	return ask_(L,mid,k);
    }
    else{
    	F(i,1,tl)ptl[i]=tree[ptl[i]].rp;
    	F(i,1,tr)ptr[i]=tree[ptr[i]].rp;
    	return ask_(mid+1,R,k-tmp);
    }
}
inline int ask(Re L,Re R,Re k){//查询第k小 
    memset(ptl,0,sizeof(ptl));//万恶的memset 
    memset(ptr,0,sizeof(ptr));//数组开太大会疯狂抢时间复杂度 
    tl=tr=0;
    for(Re i=L-1;i;i-=i&-i)ptl[++tl]=pt[i];//先把所有要更新的位置的线段树根节点记录下来 
    for(Re i=R;i;i-=i&-i)ptr[++tr]=pt[i];//方便后面递归更新信息 
    return ask_(1,m,k);
}
inline void change(Re &p,Re L,Re R,Re w,Re v){
    if(!p)p=++cnt;tree[p].g+=v;
    if(L==R)return;
    if(w<=mid)change(tree[p].lp,L,mid,w,v);
    else change(tree[p].rp,mid+1,R,w,v);
}
inline void add(Re x,Re v){//【单点修改】
    Re w=lower_bound(b+1,b+m+1,a[x])-b;//注意函数传进来的参数和这里各种映射数组的调用不要搞错 
    for(Re i=x;i<=n;i+=i&-i)change(pt[i],1,m,w,v);//树状数组思想更新信息 
}
int main(){
//  printf("%lf
",(sizeof(tree))/1024.0/1024.0);
//  printf("%lf
",(sizeof(tree)+sizeof(Q)+sizeof(c)+sizeof(a)+sizeof(b)+sizeof(pt)+sizeof(C))/1024.0/1024.0);
    in(n),in(T),m=n;
    F(i,1,n)in(a[i]),b[i]=a[i];
    F(i,1,T){
    	scanf(" %c",&opt[i]);
    	if(opt[i]=='Q')in(Q[i].l),in(Q[i].r),in(Q[i].k);
    	else in(c[i].i),in(c[i].x),b[++m]=c[i].x;
    }
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    F(i,1,n)add(i,1);//初始化建树 
    F(i,1,T){
    	if(opt[i]=='Q')printf("%d
",ask(Q[i].l,Q[i].r,Q[i].k));
    	else add(c[i].i,-1),a[c[i].i]=c[i].x,add(c[i].i,1);
//先让这个位置上原来的数减少一个，再把新数加一个，就达到了替换的目的 
    }
}

高档题走起：

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Xing-Ling/p/10886957.html