最近翻了一下自己的U盘,突然发现有一个树上差分的ppt,居然还没有学,因为以前以为这个很高大尚,以为很难.......(其实真的不难)
好吧,入正题
首先得知道差分这个东西吧! 简单差分
在讲树上差分之前，首先需要知道树的以下两个性质：
（1）任意两个节点之间有且只有一条路径。
（2）一个节点只有一个父亲节点（即只有一条返祖边）
可以发现所有树上两点 a，b 的路径可拆为：a--->LCA(a,b),LCA(a,b)--->b(最好去学一下LCA的快速求法(这个我没写,随便上网找了一个感觉比较好的:倍增LCA详讲))
首先一个大前提(一个点的真实权值是一个点子树内所有差分后的权值之和)
自己画一棵树(不想画图了我),找两个点p,q,如果是要在他们的路径上都加一个x的话
你先自己推一下在哪里++,哪里--来维护吧.(注意:一个点的真实权值是一个点子树内所有差分后的权值之和)
好的,
是在p,q上分别++,在LCA(p,q)和fa[LCA(p,q)](LCA(p,q)的爸爸)上--.自己在去手玩一下吧,最后统计出来是对的!
这个其实真的不难把!
总结一下:
1.树上差分主要用于求解一些树上的路径问题
2.它通过利用树的一些性质，用一个差分数组来实现对一条路径的操作，这涉及到路径的 起 终点 与 LCA。
3.一般情况下：一个点的真实权值为其所在子树内所有点的差分数组的值的和
4.树上差分一般不适用于询问和操作嵌套的题目，这时一般用树链剖分解决
几道题:
1.luoguP3128 [USACO15DEC]最大流Max Flow 题解 板子题
2.luoguP3258 [JLOI2014]松鼠的新家 题解 板子题
3.luoguP2680 运输计划 题解 有难度
4.luoguP1600 天天爱跑步 挖个坑
还有,其实所有的树上差分好像都要LCA,我都写的倍增...