DFS序
DFS序
我们在处理一些树上计数问题时，经常由于数据量过大而树形结构的统计操作又十分复杂，所以常常需要将树形结构转换成更加便于查询和修改的线性结构，再结合树状数组或者线段树等高效的查询更新结构来解决问题，这时，为了将树形结构转换成线性结构，我们经常会用到的一个东西就是DFS序。
想要得到DFS序，只需要对树做一次DFS遍历，在遍历过程中记录每个点被遍历到的时间点，这里用一个\(，Orderin，Orderout\)时间戳数组来记录，以下面的树为例：
经过DFS后得到的DFS序为：
| 顶点序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| \(Orderin\) | 4 | 1 | 5 | 2 | 7 | 6 | 3 |
| \(Orderout\) | 4 | 7 | 5 | 5 | 7 | 7 | 3 |
在\(Orderin,Orderout\)数组中\(序号Orderin[x] = 序号\)，所以用树状数组或者线段树维护时，只需要针对序号维护就可，如果要查询某个子树，只需要知道子树根节点\(x\)，然后查询序号\(Orderin[x] - Orderout[x]\)的区间值。
投递华为等公司10个岗位 >