可持久化线段树

可持久化线段树

可持久化数据结构总是可以保留每一个历史版本，并且支持操作的不可变特性
部分可持久化 所有版本都可以访问，但是只有最新版本可以修改
完全可持久化 所有版本都既可以访问又可以修改,支持将两个历史版本合并

主席树&可持久化线段树
主席树全称:可持久化权值线段树
函数式线段树:是指使用函数式编程思想的线段树,函数式线段树是[完全可持久化]的

先上动态开点:

//动态开点线段树模板 就是不用x*2与x*2+1记录左右儿子，直接用cnt记录编号以及对应l、r，减少4倍空间的超大消耗
#include<bits/stdc++.h>
#define ls a[o].l
#define rs a[o].r
using namespace std;

const int N=15000010;

int read() {

	int x=0,f=1;
	char ch=getchar();
	while(ch<48||ch>57) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>=48&&ch<=57) {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x*f;

}

struct Dyk {

	int l,r;

} a[N];

int sum[N],tag[N],cnt=0,root;

void push_up(int o) {
	sum[o]=sum[ls]+sum[rs];
}

void push_down(int o,int l,int r) {

	if(tag[o]!=-1) {

		int mid=(l+r)>>1;
		if(!ls) ls=++cnt;
		if(!rs) rs=++cnt;
		sum[ls]=tag[o]*(mid-l+1);
		sum[rs]=tag[o]*(r-mid);
		tag[ls]=tag[o];
		tag[rs]=tag[o];
		tag[o]=-1;

	}

}

void update(int &o,int l,int r,int x,int y,int k) {

	if(o==0) o=++cnt;
	if(x<=l&&r<=y) {
		sum[o]=(r-l+1)*k;
		tag[o]=k;
		return ;
	}

	push_down(o,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) update(ls,l,mid,x,y,k);
	if(y>mid)  update(rs,mid+1,r,x,y,k);
	push_up(o);

}

int query(int o,int l,int r,int x,int y) {
	
	int ans=0;  
	if(o==0) return 0;
	if(l==x&&r==y) return sum[o];
	int mid=(l+r)>>1;
	if(y<=mid) ans+=query(ls,l,mid,x,y);
	if(x>mid) ans+=query(rs,mid+1,r,x,y);
	return ans;
	
}


int n,q;

int main() {

	n=read();
	q=read();
	memset(tag,-1,sizeof(tag));
	update(root,1,n,1,n,0);
	for(int i=1; i<=q; i++) {

		int x=read(),y=read(),k=read();
		update(root,1,n,x,y,2-k);
		printf("%d\n",n-sum[1]);

	}

	return 0;
}

······