dfs序

lql1 · 2024-12-21 22:21:50 · 个人记录

DFS序总结

DFS序：ABCDEFG（序列长度为 n）

关于DFS序在树上问题的应用

1. 链上的操作（修改或查询）

点 u 到点 v 之间的这条链，可以转化为：

由于可以转化，下面总结里的链查询都表示点 u 到 root。

2. 点修改，子树查询

• 单点修改，区间求值
• 点修改，链查询

突破口：思考修改一个点会对哪些链产生影响——它子树上的点。

DFS序：相当于子树上的所有点到根节点的距离都多了一个 \Delta。

令 dis[\text{in}[u]] 表示点 u 到根节点 root 的距离。

• 修改：修改区间 [\text{in}[x], \text{out}[x]] 的值。
• 查询：dis[\text{in}[x]]。

3. 子树修改，点查询

• 区间修改，单点查询

4. 子树修改，子树查询

• 区间修改，区间查询

5. 子树修改，链查询

DFS序解法：

突破口：探究这个修改会影响哪些值，以及影响多少？它会影响以 x 为根节点的子树。假设修改了以 x 为根节点的子树，对于子树里的节点 y，其距离增加了：

化简后得到：

• 修改：在第一个数据结构的区间 [\text{in}[x], \text{out}[x]] 加上 \Delta \cdot (\text{dep}[x] - 1)，并开第二个数据结构存储 \Delta，用于表示查询时需要乘以深度的部分；这个 \Delta 也加在区间 [\text{in}[x], \text{out}[x]] 上。
• 查询：

6. 链修改，点查询

突破口：修改一条链会对哪些点产生影响？修改点 u 到 root 这条链会对 u 的所有祖先产生影响。

令差分数组 d[u] 表示：

因此：

• 修改：单点修改 \text{in}[u]（差分思想）。
• 查询：区间查询 [\text{in}[x], \text{out}[x]]（子树查询）。

7. 链修改，子树查询

突破口：修改一条链对子树有何影响？假设现在修改点 u 到 root 这条链，对于 u 的祖先 v，u 对 v 的贡献是：

化简后得到：

需要开两个树状数组进行单点修改与区间查询。