※本文一切代码未经编译，不保证正确性，如发现问题，欢迎指正！
最简单的树状数组就是这样的：
通过“差分”（就是记录数组中每个元素与前一个元素的差），可以把这个问题转化为问题1。
设原数组为, 设数组，则 ，可以通过求的前缀和查询。
当给区间加上x的时候， 与前一个元素 的差增加了， 与 的差减少了。根据数组的定义，只需给 加上 , 给 减去 即可。
这是最常用的部分，也是用线段树写着最麻烦的部分——但是现在我们有了树状数组！
怎么求呢？我们基于问题2的“差分”思路，考虑一下如何在问题2构建的树状数组中求前缀和：
位置p的前缀和 =
在等式最右侧的式子中， 被用了次，被用了次……那么我们可以写出：
位置p的前缀和 =
位置p的前缀和即： (p + 1) * sum1数组中p的前缀和 - sum2数组中p的前缀和。
区间[l, r]的和即：位置r的前缀和 - 位置l的前缀和。
对于sum1数组的修改同问题2中对d数组的修改。
对于sum2数组的修改也类似，我们给 sum2[l] 加上 l * x，给 sum2[r + 1] 减去 (r + 1) * x。
用这个做区间修改区间求和的题，无论是时间上还是空间上都比带lazy标记的线段树要优。
我们已经学会了对于序列的常用操作，那么我们不由得想到（谁会想到啊喂）……能不能把类似的操作应用到矩阵上呢？这时候我们就要写二维树状数组了！
我们对于一维数组进行差分，是为了使差分数组前缀和等于原数组对应位置的元素。
那么如何对二维数组进行差分呢？可以针对二维前缀和的求法来设计方案。
二维前缀和：
那么我们可以令差分数组 表示 与 的差。
例如下面这个矩阵
对应的差分数组就是
这样给修改差分，造成的效果就是：
那么我们开始写代码吧！
类比之前一维数组的区间修改区间查询，下面这个式子表示的是点(x, y)的二维前缀和：
把这个式子展开，就得到：
那么我们要开四个树状数组，分别维护：
这样就完成了！
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/14393.html