在网上找了treap和splay的模板,有几个不理解的地方求解答qwq
这是splay的旋转板子:
void update(int x) {
if(x) {
siz[x]=cou[x];
if(son[x][0])siz[x]+=siz[son[x][0]];
if(son[x][1])siz[x]+=siz[son[x][1]];
}
}
这是traep的:
void rotate(int p, int &x)
{
int y=T[x].son[!p];
T[x].size=T[x].size-T[y].size+T[T[y].son[p]].size;
T[x].son[!p]=T[y].son[p];
T[y].size=T[y].size-T[T[y].son[p]].size+T[x].size;
T[y].son[p]=x;
x=y;
}
请问为什么一个点和他的儿子节点信息修改后他们的子树信息不用修改呢?