可以发现，与传统的线段树不同的地方就是左右儿子的编号。

传统线段树的 \(i\) 节点的左儿子是 \(i\times2\)，右儿子是 \(i\times2+1\)，而动态开点线段树的 \(i\) 节点的左右儿子的则是储存为 \(tre_i.ls,tre_i.rs\)，先用先开先存。

zkw 线段树

与朴素线段树的区别

朴素的线段树都是递归形式的，占用栈空间大，常数大。zkw 线段树则是循环形式，常数小，代码短。

朴素的线段树是找到根节点，然后向下递归维护。zkw 线段树则是先找叶节点，然后上浮维护到根节点。

对于朴素的线段树（如最上边的图），叶节点是很难确定的。但如果我们要维护的是一棵满二叉树，找到叶节点就很容易了。

如下图：

（同样是直接从网上找的）

这样的线段树在节点上就会有一些奇妙的性质：

• 共有 n 个叶节点，代表区间 [x,x] 的叶节点对应的编号就是 n+x。

• 若某节点的编号为 i，则其父亲的编号为 \(\lfloor\dfrac{i}{2}\rfloor\)，左儿子的编号为 \(2\times i\)，右儿子的编号为 \(2\times i+1\)。

• 若两个节点分别为 i,j，且 i,j 是兄弟节点（即父节点相同），那么 \(i\oplus j=1\)。

• 除根节点外，编号为偶数的节点为其父节点的左儿子，编号为奇数的节点是其父节点的右儿子。

建树比较简单。

我们需要将原序列的值赋到叶节点上，首先要保证叶节点能够容纳下原序列。

将叶节点赋值之后，便和朴素的线段树一样，将点权 pushup。

然后是区间修改和区间查询。

如果要维护区间 [i,j] 这个闭区间，要转化为维护(i-1,j+1) 这个开区间。

如果当前节点是正好是区间左端点，而且是其父节点的左儿子，那么他的兄弟就是要维护的区间的一部分。同理，如果当前节点是正好是区间右端点，而且是其父节点的右儿子，那么他的兄弟也是要维护的区间的一部分。

如果我满足条件，就维护我的兄弟和我的父亲

当两个节点是兄弟节点时，也就是循环结束的时候。这时再将父节点到根节点这段维护了，就是 zkw 线段树的全过程了。

在上浮过程中，懒标上传比较困难，所以选择标记永久化。

比较难讲，看了网上好多 zkw 的讲解，都有些朦胧。

可以根据代码理解，依旧是 P3372：

#include
#define int long long
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=1e5+7;
int n,q,m=1,op,l,r,v;
struct zkw_sgt{
	int le,ri;
	int val,tag;
}tre[inf<<2];
void build()
{
	while(m<=n)m<<=1;
	for(int i=m+1;i<=m+n;i++)
		tre[i].val=re();
	for(int i=m-1;i>0;i--)
		tre[i].val=tre[i<<1].val+tre[i<<1|1].val;
}
void update(int i,int j,int k)
{
	int ltag=0,rtag=0,len=1;
	while(i^j^1)
	{
		if(i&1^1)tre[i^1].tag+=k,ltag+=len;
		if(j&1)tre[j^1].tag+=k,rtag+=len;
		tre[i>>1].val+=k*ltag;
		tre[j>>1].val+=k*rtag;
		i>>=1,j>>=1,len<<=1;
	}
	int tag=ltag+rtag;i>>=1;
	while(i)
	{
		tre[i].val+=k*tag;
		i>>=1;
	}
}
int ask(int i,int j)
{
	int ltag=0,rtag=0,len=1,ans=0;
	while(i^j^1)
	{
		if(i&1^1)ans+=tre[i^1].val+tre[i^1].tag*len,ltag+=len;
		if(j&1)ans+=tre[j^1].val+tre[j^1].tag*len,rtag+=len;
		if(tre[i>>1].tag)ans+=tre[i>>1].tag*ltag;
		if(tre[j>>1].tag)ans+=tre[j>>1].tag*rtag;
		i>>=1,j>>=1,len<<=1;
	}
	int tag=ltag+rtag;i>>=1;
	while(i)
	{
		if(tre[i].tag)ans+=tre[i].tag*tag;
		i>>=1;
	}
	return ans;
}
signed main()
{
	n=re();q=re();
	build();
	for(int i=1;i<=q;i++)
	{
		op=re(),l=re(),r=re();
		if(op==1)v=re(),update(l+m-1,r+m+1,v);
		else wr(ask(l+m-1,r+m+1)),putchar('\n');
	}
	return 0;
}

拆位线段树

模板

首先明确，\((a+b)\oplus c\ne (a\oplus c)+(b\oplus c)\)。

那么这个题直接用线段树维护区间和显然是行不通的。将区间求和转化成多个单点求和甚至比暴力还慢。

对于牵扯到异或运算的，有两种解决措施：

• 异或前缀和

• 拆位

对于这个题来说，\(a_i\le10^6\)，大概只需要拆 20 位左右。

然后用 20 棵线段树维护每一位。再结合左移和右移完成对输入数据和输出结果的处理。

代码如下：

#include
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(long long s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=1e5+7;
int n,m,a[inf];
struct a_tree{
	int le,ri,siz;
	int val,tag;
}tre[20][inf<<2];
void build(int k,int i,int l,int r)
{
	tre[k][i].le=l,tre[k][i].ri=r;tre[k][i].siz=r-l+1;
	if(l==r)
	{
		tre[k][i].val=(a[l]>>k)&1;
		return;
	}
	int mid=(l+r)>>1;
	build(k,i<<1,l,mid);
	build(k,i<<1|1,mid+1,r);
	tre[k][i].val=tre[k][i<<1].val+tre[k][i<<1|1].val;
}
void pushdown(int k,int i)
{
	tre[k][i<<1].val=tre[k][i<<1].siz-tre[k][i<<1].val;
	tre[k][i<<1|1].val=tre[k][i<<1|1].siz-tre[k][i<<1|1].val;
	tre[k][i<<1].tag^=1;tre[k][i<<1|1].tag^=1;
	tre[k][i].tag=0;
}
void update(int k,int i,int l,int r)
{
	if(l<=tre[k][i].le&&tre[k][i].ri<=r)
	{
		tre[k][i].val=tre[k][i].siz-tre[k][i].val;
		tre[k][i].tag^=1;
		return;
	}
	if(tre[k][i].tag)pushdown(k,i);
	int mid=(tre[k][i].le+tre[k][i].ri)>>1;
	if(l<=mid)update(k,i<<1,l,r);
	if(mid>1,ans=0;
	if(l<=mid)ans+=ask(k,i<<1,l,r);
	if(mid>i)&1;
				if(v)update(i,1,l,r);
			}
		}
	}
	return 0;
}

可持久化线段树

例题

可持久化线段树模板

主席树模板

关于可持久化

能够保留每一个历史版本的数据结构。

那么可持久化线段树就是能保留历史版本的线段树。

原谅我之前一直叫它可持续化线段树 。

思路

拿 模板 1 来讲，

因为要保留历史版本。

那么如果对于每次的的修改和查询均新生成一棵线段树的话……

一棵线段树需要 \(4\times n\) 的空间， \(m\) 次操作代表了 \(m\) 棵线段树，空间复杂度 \(O(4mn)\) ……

所以不能直接暴力。

可持久化线段树的基本思想就是动态开点。

当对一个叶节点进行修改之后，你会发现整棵树上修改的点会形成一条链，那我们就将这条链维护出来，也就是下图的红色节点（图片来自 OI wiki ）。

这时，我们就不能简单地 “ i<<1 是 i 的左儿子， i<<1|1 是 i 的右儿子” 了，动态开点会导致可持久化线段树不满足线段树的性质，所以我们要将每个节点的左右儿子记录下来。

1. 建树

   建树过程与普通线段树相比，只是加点方式不同，而且有了返回值，以便于回溯时将自己的编号传给父节点。

   代码实现：

int build(int i,int le,int ri)
{
	i=++cnt;
	if(le==ri)
	{
		tre[i].val=a[le];
		return i;
	}
	int mid=(le+ri)>>1;
	tre[i].lsn=build(tre[i].lsn,le,mid);
	tre[i].rsn=build(tre[i].rsn,mid+1,ri);
	return i;
}

2. 修改

   在修改的过程中，我们先新建一个节点，赋给它对应的历史节点的信息（包括左右子节点和权值），同样在回溯的过程中将编号传给父亲。

   还有，每新建一棵线段树，都要将根节点记录下来，就是历史版本。

   代码实现：

int change(int i,int id,int key,int le,int ri)
{
	tre[++cnt]=tre[i];
	i=cnt;
	if(le==ri)
	{
		tre[i].val=key;
		return i;
	}
	int mid=(le+ri)>>1;
	if(id<=mid)tre[i].lsn=change(tre[i].lsn,id,key,le,mid);
	else tre[i].rsn=change(tre[i].rsn,id,key,mid+1,ri);
	return i;
}

3. 查询

   查询就和普通线段树基本一样了，由于新版本和历史版本完全相同，所以直接赋过去就可。

   代码实现：

long long ask(int i,int id,int le,int ri)
{
	if(le==ri)
		return tre[i].val;
	int mid=(le+ri)>>1;
	if(id<=mid)return ask(tre[i].lsn,id,le,mid);
	else return ask(tre[i].rsn,id,mid+1,ri);
}

还记得那首诗嘛？

一年 OI 一场空，不开 long long 见祖宗。

可持久化线段树码量不大，和普通线段树差不多。再加上本人有 不严重的 压行习惯。

坑点

1. 空间

   线段树对的空间的需求极大，典型的空间换时间，所以数组千万不要开太大，可持续化线段树开到原数组大小的 23 被就好了，否则就会无情的 Runtime Error. 和 Memory Limit Exceeded. 。

2. 还是空间

   可能有和我一样将每个节点代表的区间左右端点存入结构体中。但是，可持续化线段树的结构体中不要存，千万不要存。不做题永远不知道第二个点多毒瘤。

Code

#include
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(long long s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=1e6+7;
struct long_tree{
	int lsn,rsn;
	long long val;
}tre[inf*23];
int n,m,cnt;
int a[inf],root[inf];
int v,op,id,k;
int build(int i,int le,int ri)
{
	i=++cnt;
	if(le==ri)
	{
		tre[i].val=a[le];
		return i;
	}
	int mid=(le+ri)>>1;
	tre[i].lsn=build(tre[i].lsn,le,mid);
	tre[i].rsn=build(tre[i].rsn,mid+1,ri);
	return i;
}
int change(int i,int id,int key,int le,int ri)
{
	tre[++cnt]=tre[i];
	i=cnt;
	if(le==ri)
	{
		tre[i].val=key;
		return i;
	}
	int mid=(le+ri)>>1;
	if(id<=mid)tre[i].lsn=change(tre[i].lsn,id,key,le,mid);
	else tre[i].rsn=change(tre[i].rsn,id,key,mid+1,ri);
	return i;
}
long long ask(int i,int id,int le,int ri)
{
	if(le==ri)
		return tre[i].val;
	int mid=(le+ri)>>1;
	if(id<=mid)return ask(tre[i].lsn,id,le,mid);
	else return ask(tre[i].rsn,id,mid+1,ri);
}
int main()
{
	n=re();m=re();
	for(int i=1;i<=n;i++)
		a[i]=re();
	root[0]=build(0,1,n);
	for(int i=1;i<=m;i++)
	{
		v=re();op=re();id=re();
		if(op==1)k=re(),root[i]=change(root[v],id,k,1,n);
		else wr(ask(root[v],id,1,n)),putchar('\n'),root[i]=root[v];
	}
	return 0;
}

主席树

线段树可以加可持久化，权值线段树也可以。

主席树，全名 可持久化权值线段树 。

引入

那么看一下 模板 2 。

给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。

好像就是把区间从 \(1\sim n\) 扩展到了 \(l\sim r\) 。

于是我们就从权值线段树扩展到了可持续化权值线段树。

思路

• STL 暴力。

可以看一下 这个题

我们就用这个题不让用的 nth_element 。

这个东西可以直接在 \(O(n)\) 的时间内求区间最小值。

我们找一个临时数组 ls 存 a[l]~a[r] ，然后就用 nth_element 苟到了 50 分。

就像酱紫：

#include
#include
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=2e5+7;
int n,m,l,r,k;
int a[inf],ls[inf];
int main()
{
	n=re();m=re();
	for(int i=1;i<=n;i++)
		a[i]=re();
	for(int ii=1;ii<=m;ii++)
	{
		l=re();r=re();k=re()-1;
		int i=l,j=0;
		while(i<=r)
			ls[j]=a[i],i++,j++;
		nth_element(ls,ls+k,ls+j);
		wr(ls[k]);putchar('\n');
	}
	return 0;
}

• 正解

结合前缀和，用权值线段树维护 \(1\sim i\) 。

查询时再结合差分查询 \((1\sim r)-(1\sim (l-1))\) 。

将整个数组排序，去重，然后对于原来的每个点，建 1 到值域的主席树。

如果值域太大但实际上数很少时，可以考虑离散化，但显然这个题不需要。

最后对每个询问进行查询。

Code

此题比上述的可持久化线段树还短。

#include
#include
using namespace std;
int re()
{
	int s=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=s*10+ch-48,ch=getchar();
	return s*f;
}
void wr(int s)
{
	if(s<0)putchar('-'),s=-s;
	if(s>9)wr(s/10);
	putchar(s%10+48);
}
const int inf=2e5+7;
struct long_tree{
	int lsn,rsn;
	int sum;
}tre[inf<<5];
int n,m,cnt;
int a[inf],b[inf];
int root[inf];
int l,r,k;
int add(int i,int le,int ri,int key)
{
	tre[++cnt]=tre[i];
	i=cnt;tre[i].sum++;
	if(le==ri)return i;
	int mid=(le+ri)>>1;
	if(key<=b[mid])tre[i].lsn=add(tre[i].lsn,le,mid,key);
	else tre[i].rsn=add(tre[i].rsn,mid+1,ri,key);
	return i;
}
int ask(int i,int j,int le,int ri,int k)
{
	if(le==ri)return le;
	int mid=(le+ri)>>1,
		ans=tre[tre[j].lsn].sum-tre[tre[i].lsn].sum;
	if(k<=ans)return ask(tre[i].lsn,tre[j].lsn,le,mid,k);
	else return ask(tre[i].rsn,tre[j].rsn,mid+1,ri,k-ans);
}
int main()
{
	n=re();m=re();
	for(int i=1;i<=n;i++)
		a[i]=b[i]=re();
	sort(b+1,b+n+1);
	int num=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)
		root[i]=add(root[i-1],1,num,a[i]);
	for(int i=1;i<=m;i++)
	{
		l=re(),r=re(),k=re();
		wr(b[ask(root[l-1],root[r],1,num,k)]);
		putchar('\n');
	}
	return 0;
}

扫描线

P5490 扫描线

线段树套线段树

P3810 陌上花开