Treap 的操作中有一个 rotate 操作,大概长这样:
void rotate(long long &p,long long d)
{
long long t,v;
if(d==1)
{
t=tree[p].son[0];
v=tree[t].son[1];
tree[p].son[0]=v;
tree[t].son[1]=p;
}
else
{
t=tree[p].son[1];
v=tree[t].son[0];
tree[p].son[1]=v;
tree[t].son[0]=p;
}
pushup(p);
pushup(t);
p=t;
return;
}
其中,进行完一次 rotate 操作后就会进行对 p 和 t 分别进行一次 pushup(pushup操作),但很显然操作时 p 一定是 t 的孩子,也就是说,rotate 结束后需要先更新 p 再更新 t 才能保证正确性。
我的疑惑是,如果把 pushup 的顺序调换,似乎对结果没什么影响(这里指都能 AC,不代表对平衡树内的数据无影响),这与之前“rotate 结束后需要先更新 p 再更新 t 才能保证正确性”的结论相违背,所以是否先更新 t 再更新 p 与先更新 p 再更新 t 本质相同,又或是有影响,但是可以互相抵消导致对最终结果没有影响?