关于可持久化线段树
  • 板块学术版
  • 楼主1kri
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/5/4 22:27
  • 上次更新2023/11/7 03:09:39
查看原帖
关于可持久化线段树
235926
1kri楼主2020/5/4 22:27

区间操作的可持久化。

窝的大佬同学说要改很多东西。

但是我觉得每次pushdownpushdown 的时候直接新建 lsonlsonrsonrson 的副本,并将 nownow 节点的左右儿子先更新后还原就行了。

这是我思路的伪代码段

inline void update(int &now,int pre,int nowl,int nowr,int lt,int rt,int val){
	node prel=hjt[pre].l,prer=hjt[pre].r;
   //pushdown_start
	now=++cnt;
	hjt[now]=hjt[pre];
	if (hjt[now].tag!=0){
		//伪代码:pushdown_hjt[pre]
		hjt[now].l=++cnt;
		hjt[now].l=hjt[pre].l;
		hjt[now].r=++cnt;
		hjt[now].r=hjt[pre].r;
	}
   //pushdown_end;
	/*普通可持久化线段树操作
		ZTQ_ak_ioi
		SLH_ak_ioi
		LHQ_ak_ioi
		MWR_shi_ChaoJi_CaiJi,LG_ZuiCai
	*/
	hjt[pre].l=prel,ht[pre].r=prer;//还原
	return;
}

请问这样的思路正确吗

2020/5/4 22:27
加载中...