树上差分是我很久以前学的东西了……其实也不久，就大半年。
当时觉得很巧妙，但是没有思考为什么会得到这个思路。结果时间一长，现在忘了怎么做树上差分了。
小推了一下，原来很简单。看来以前我还是太菜了。
先看看序列上的情况。定义差分序列为
或：
把
可以说，差分是前缀和的逆运算。
肯定要把树上差分和序列上差分联系起来。不过该如何做减法呢？我不知道。
可以联系到前缀和。定义前缀和有两种思路。
一种思路是定义前缀和为当前节点到根节点的路径的和，可以理解为深度。这样做的意义是明确的：一个点到祖先的路径是个序列，很好联想到前缀和。
类比序列上问题，前缀和就是：
那么根据上面的规则，差分就是：
很简单朴实。前缀和可以拿来求路径和，差分可以修改一个子树。
另一种思路是定义前缀和为当前节点为根的子树内的权值和。这么做的意义好像不怎么明确，似乎只能拿来求一颗子树的补树。
前缀和形式：
那么差分就自然地推出了：
发现差分可以拿来修改一条路径。这个还是挺有用的。
写完发现一个有趣的事实：两种方式的效果是完全相反的。一个前缀和求路径，一个求子树；一个差分改子树，一个差分改路径。