树状数组的区间修改

我一直都没意识到树状数组的用途，树状数组最普通的用法是，单点修改+区间查询，但是今日做洛谷的（树链剖分模板题时，发现不对）他要进行的是区间修改，刚好看的一个大佬写的题解是用树状数组做的，但是用树状数组做的话（按照我的理解应该是O(nlogn)这样的话时间复杂度可以到O(n^2logn)必超时间，然后，就发现了一个新的方法。
首先设一个差分数组：

则应有：

所以有:

将上面的狮子展开：

在级数绝对收敛的情况下：

              
	\begin{split}
           \sum_{i=1}^{n}  a\left [ i \right ] &= \sum_{j=1}^{n}(c[1]+c[2]+...+c[j])\\ 
                     &   = n*c[1]+(n-1)*c[2]+...+c[n]\\
&=n*\sum_{j=1}^{n}c[j]-\sum_{j=1}^{n}(j-1)*c[j]  

	\end{split}
	//贴一段latex的代码
1
2
3
4
5
6
7
8

所以可以看到，在这种方法下，如果设置两个数组，一个里面存的是差分(c1)，另一个存的是（i-1)c[i] (c2),则对这两个数组分别构建树状数组，则对于区间查询就可以达到O(logn)的复杂度
比如现在要对[l,r]之内的区间加x
操作应该是：
add(c1,l,x);add(c1,r+1,-x);
add(c2,l,(l-1)(x));add(c2,r+1,r*(-x));
然后求和的时候
a=getsum(c,l-1),b=getsum(c,r)
c=getsum(c2,l-1),d=getsum(c2,r)
res1=(l-1)a-c;
res2=rb-d
return res2-res1;
参考文章：
https://blog.csdn.net/blue_kid/article/details/78428244