Super Fenwick Tree
冈崎梦美
2017-12-14 20:33:48
UPD1:之前推导过程中论证有些笔误，已修改。
UPD2:添加了对于求和公式的注释。（原来的一大堆代码，看起来很诡异……）
---
[线段树模板（1）](https://www.luogu.org/problemnew/show/3372)
题意要求：给定一个序列，支持区间修改和区间查询。
当然，题目名字告诉我们要用线段树。但是线段树很长，容易出现问题，而且跑得稍慢，所以就有dalao开始yy：可不可以让树状数组支持区间修改和查询呢？
## 于是伟大的“超级树状数组”横空出世了。
首先，我们看树状数组是如何支持区间修改的：
设tree[i]=a[i]-a[i-1]（差分），那么容易得到：
***tree[1]+tree[2]+……+tree[i]=a[i]***这个公式
所以，只需要维护tree数组就可以实现区间修改了。
**那么问题来了，如果这样，那么如何实现区间查询呢？**
我们已经推出了一个公式：
```cpp
tree[1]+tree[2]+……tree[i]=a[i]
```
那么，对于1到r的区间和，即为：
```cpp
a[1]+a[2]+……+a[r-1]+a[r]
//用上方公式推导得出
=tree[1]+(tree[1]+tree[2])+……+(tree[1]+……+tree[r])
//根据加法交换律与结合律：
=(tree[1]*(r))+(tree[2]*(r-1))+……(tree[r]*1)
//那么：
=r*(tree[1]+tree[2]+……+tree[r])-(tree[1]*0+tree[2]*1+……+tree[r]*(r-1))
```
看到这里，是不是已经很清晰了呢？
对于a的树状数组(差分)tree，建立一个新的树状数组tree1使得：
`tree1[i]=tree[i]*(i-1)`
之后，x到y的区间和即为：
`(y\*getsum(tree,y)-(x-1)\*getsum(tree,x-1))-(getsum(tree1,y)-getsum(tree1,x-1))`
```
Tips:
因为求区间和满足区间加法，所以Sum(L,R)=Sum(1,R)-Sum(1,L-1)，所以有上述公式。
```
当然，对于更新操作也需要进行一些细微调整，详细的就看代码吧……
```cpp
#include<bits/stdc++.h>
using namespace std;
long long n,m,tree[100005],tree1[100005];//题目要求longlong
inline void add(long long*z,long long x,long long num)
{
while(x<=n)
{
z[x]+=num;
x+=x&(-x);
}
}
inline long long getsum(long long*z,long long x)
{
long long sum=0;
while(x>0)
{
sum+=z[x];
x-=x&(-x);
}
return sum;
}
int main()
{
cin.sync_with_stdio(false);
cin>>n>>m;
long long a,b=0;
for(long long i=1;i<=n;i++)
{
cin>>a;
b=a-b;
add(tree,i,b);
add(tree1,i,(i-1)*b);
b=a;
}
for(long long i=1;i<=m;i++)
{
int t,x,y,z;
cin>>t;
if (t==1)
{
cin>>x>>y>>z;
add(tree,x,z);
add(tree,y+1,-z);
add(tree1,x,z*(x-1));
add(tree1,y+1,-z*y);//此处为核心，联系上方的公式，想一想为什么这么修改。
}
else
{
cin>>x>>y;
cout<<(y*getsum(tree,y)-(x-1)*getsum(tree,x-1))-(getsum(tree1,y)-getsum(tree1,x-1))<<endl;
}
}
return 0;
}
```