警示后人:关于构建主席树
查看原帖
警示后人:关于构建主席树
732906
4BboIkm7h楼主2025/2/7 22:24

对于重构树的新建节点,在建主席树的时候只需要将线段树根的编号从上一个版本迁移过来,而不需要进行更新。具体实现方式有很多种,由于我习惯写的 update 函数是带取地址的,所以我就在其中加入特判:

void update(int &p, int pre, int pl, int pr, int pos) {
	if (!pos) {p = pre; return;}
  //传入的pos如果为0就说明这是重构树新建出来的节点
	p = ++cnt;
	t[p] = {t[pre].sum + 1, ls(pre), rs(pre)};
	if (pl == pr) return;
	if (pos <= mid) update(ls(p), ls(pre), pl, mid, pos);
	else update(rs(p), rs(pre), mid + 1, pr, pos);
}
2025/2/7 22:24
加载中...