标签:树链剖分

2 篇文章

树链剖分算法解析
本文部分内容参考自 这篇博客 (写的很好 Orz ,建议大家也去看一下) 树链剖分是什么?用来做什么? 有一棵树,求解以下问题: 1. 将从 x 到 y 的路径上的每个结点权值增加 z 2. 求从 x 到 y 的路径上的每个结点的权值和/权值最大值/权值最小值 对于问题 1,我们可以用树上差分来求解。 对于问题 2,我们可以用类似前缀和的方法,预处…