我们相距十万光年

晨露正葱茏,来日胜景定无穷

03/18
21:46
Luogu

Luogu P3384 树链剖分

传送门:https://www.luogu.org/problem/show?pid=3384

终于Accepted了!!

分割线 -> 2017年03月25日 -> 补充上一些Thoughts

这是一棵树,不同的重链已经用不同粗细的红边连好。

假设我们让以3为根节点的子树所有节点+3。这里我们要多记录一点信息: end[i]代表以i开头的重链结尾的编号。

我们知道,3号节点所属的重链的开头是1号,通过end[1]得知重链结尾是9号,id[9]  =  6。所以我们用线段树对区间id[3] ~ id[9]进行修改操作(+3),也就是区间[3, 6]。

操作完我们发现,3号的儿子(先行记录,第一个DFS或第二个都可以)有7个(包括3号自己),我们刚刚处理的节点个数是id[9]-id[6] + 1 = 4个,这里是说明我们还没有处理完。我们要处理的下一条重链的top号就是我们现在处理的重链的end+1。然后我们可以直接处理7所在的重链:区间id[top[7]] ~ id[end[top[7]]] -> 注意end[]的定义是代表[以i开头]重链结尾的编号,也就是区间[7, 7]。

为什么会这样?因为我们第二次的DFS先搜重儿子,保证重链上id的连续,但是之后搜索轻儿子们保证轻儿子开头的重链紧紧连在当前重链最后一个节点id的后面。然后处理完7后,剩下的儿子数是7 – 4(第一次) – (id[7] – id[7] + 1)(这一次的) = 2。说明还没处理完,于是从end[top[7]] + 1开始继续处理,也就是8号开头的重链。然后往复这样,直到没有儿子可以处理了。

对于4号操作:求以x为根节点的子树内所有节点值之和。就是3号操作的逆操作,我们只需要把更新改为求和就好了。

总结一下。

3号操作直接修改区间id[root] ~ id[root] + son[id[root]]  (+1)

4号操作就是取出区间id[root] ~ id[root] + son[id[root]]  (+1)的和

另外,一颗子树在线段树里对应着一段连续的区间,那区间的end可以用begin+begin的儿子数来计算。