对于重构树的新建节点,在建主席树的时候只需要将线段树根的编号从上一个版本迁移过来,而不需要进行更新。具体实现方式有很多种,由于我习惯写的 update
函数是带取地址的,所以我就在其中加入特判:
void update(int &p, int pre, int pl, int pr, int pos) {
if (!pos) {p = pre; return;}
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);
}