dfs 序平衡树
赛时手搓算法 002
算法功能
一种树上加点并动态维护子树信息的算法
实现两种操作：
- 指定一个节点，添加一个指定编号的子节点；
- 查询以指定节点为根的子树大小、权值和等信息。
算法说明
dfs 序可以快速维护子树信息，我们着重考虑如何处理修改操作。我们可以在 dfs 序序列中将节点 \(i\) 插入到 \(fa[i]\) 的下一个位置，代表 \(i\) 成为 \(fa[i]\) 最靠左的儿子。
例如，我们要将 \(5\) 号节点插入树中。原来的 dfs 序序列 \(id_i\) 为：
插入后，变为
序列插入操作可以使用平衡树 \(O(\log n)\) 实现。然而，在查询时，我们需要知道子树在 dfs 序序列上对应的区间 \([l,r]\)，就能在平衡树上查询子树信息。可是，我们只知道左边界对应的值是根节点的编号 \(id[l]=k\)。对于右边界，我们也只需知道 \(id[r]\) 是多少，然后通过 Splay 平衡树自下而上的旋转，或者通过 FHQ 求出排名然后分裂，就可以将 \([l,r]\) 区间分离出来。
具体的，我们对每个节点 \(i\) 维护 \(nxt[i]\)，满足以 \(i\) 为根的子树对应的 dfs 序区间 \([l,r]\)，有 \(nxt[i]=r+1\)。只要知道 \(nxt[i]\)，我们就能快速求出查询区间的右边界。
手玩数据和样例可以发现一些规律：
- 如果一个节点存在右侧的亲兄弟 \(b_i\)，则 \(nxt[i]=b_i\)；
- 如果不存在，则 \(nxt[i]=nxt[fa[i]]\)；
- 如果节点不存在左侧的亲兄弟，则在 \(nxt\) 上该节点无入度；
- \(nxt[root]=+\infty\)；
又因为链式前向星存边的特性，给同一父节点先后插入多个子节点，这些子节点按插入的先后顺序一定是从右向左排列的。因此后插入的节点不会改变其他节点的 \(nxt\) ，只需要将自己的 \(nxt\) 指向 \(b_i\) 或者 \(nxt[fa[i]]\) 即可，时间复杂度 \(O(1)\)。这样，我们将插入时间复杂度和查询时间复杂度都做到了 \(O(\log n)\)。