数据结构之线段树

经验分享区
1

上周讲了搜索和线段树。
搜索的话看这个，老师讲了剪枝，IDDFS，A*，IDA*。
好下面讲线段树。
模版请自行学习（别问为什么，因为这是预习内容）。
好下面看第一个知识：动态开店点。
动态开点就是在你要用到的时候去开辟新的节点，具体的我们下面会说。
然后我们学习可持久化线段树数组（可持久化线段树2没学会，qwq）。
废话不说看题。
单点线段树不需要懒标记，所以就三个函数，我们一个一个看。
1. 建线段树。

void build(int &x,int l,int r)//建树 
{
	x=++cnt;//开辟一个新的节点（这里就是用到动态开点）
	if(l==r)
	{
		tree[x].val=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(tree[x].l,l,mid);
	build(tree[x].r,mid+1,r);
}

2. 修改。

void update(int &x,int l,int r,int k,int t)//修改 
{
	cnt++;//开点
	tree[cnt]=tree[x];//新增点时要把之前的版本传过去 
	x=cnt;
	if(l==r)
	{
		tree[x].val=k;
		return;
	}
	int mid=(l+r)/2;
	if(t<=mid) update(tree[x].l,l,mid,k,t);
	else update(tree[x].r,mid+1,r,k,t);
}

最后是查询

int query(int x,int l,int r,int t)//查询 
{
	if(l==r) return tree[x].val;
	int mid=(l+r)/2;
	if(t<=mid) return query(tree[x].l,l,mid,t);
	else return query(tree[x].r,mid+1,r,t);
}

应该还是比较简单的，实在不懂可以看看题解。
下面我们看线段树合并。
前置知识：LCA和树上差分，不会的去我发的帖子里学习。
这里我们先预处理 LCA 。
然后树上差分，这里 x,y 是两个点， p 是粮食类型：

update(rt[x],1,100000,p,1);
update(rt[y],1,100000,p,1);
update(rt[t],1,100000,p,-1);
update(rt[fa[t][0]],1,100000,p,-1);

然后合并线段树。

void dfs_merge(int x,int father)
{
	for(auto i:v[x])
	{
		if(i==father) continue;
		dfs_merge(i,x);
		rt[x]=merge(rt[x],rt[i],1,100000);//让它和它儿子合并
	}
	ans[x]=tree[rt[x]].pos;
	if(!tree[rt[x]].val) ans[x]=0;
}

那如何合并呢？

int merge(int x,int y,int l,int r)
{
	if(!x||!y) return x+y;//如果有一个是空那么直接合并
	if(l==r)
	{
		tree[x].val+=tree[y].val;
		return x;
	}
	int mid=(l+r)/2;
	tree[x].l=merge(tree[x].l,tree[y].l,l,mid);//合并左边
	tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);//合并右边
	push_up(x);
	return x;
}

这样看着是不是觉得有点暴力，其实不然，为什么呢（我也不知道）。
我们最后看看push_up。
如果有一边是空那么直接修改。
如果都不是空我们就要看哪个大了。

void push_up(int x)
{
	if(!tree[x].l)
	{
		tree[x].val=tree[tree[x].r].val;
		tree[x].pos=tree[tree[x].r].pos;
		return;
	}
	if(!tree[x].r)
	{
		tree[x].val=tree[tree[x].l].val;
		tree[x].pos=tree[tree[x].l].pos;
		return;
	}
	if(tree[tree[x].l].val>=tree[tree[x].r].val)
	{
		tree[x].val=tree[tree[x].l].val;
		tree[x].pos=tree[tree[x].l].pos;
		return;
	}
	tree[x].val=tree[tree[x].r].val;
	tree[x].pos=tree[tree[x].r].pos;
}

可能讲得不太好，不懂的自己可以上网搜索。

1 个赞