Super Fenwick Tree

· · 题解

UPD1:之前推导过程中论证有些笔误，已修改。

UPD2:添加了对于求和公式的注释。（原来的一大堆代码，看起来很诡异……）

线段树模板（1）

题意要求：给定一个序列，支持区间修改和区间查询。

当然，题目名字告诉我们要用线段树。但是线段树很长，容易出现问题，而且跑得稍慢，所以就有dalao开始yy：可不可以让树状数组支持区间修改和查询呢？

于是伟大的“超级树状数组”横空出世了。

首先，我们看树状数组是如何支持区间修改的：

设tree[i]=a[i]-a[i-1]（差分），那么容易得到：

tree[1]+tree[2]+……+tree[i]=a[i]这个公式

所以，只需要维护tree数组就可以实现区间修改了。

那么问题来了，如果这样，那么如何实现区间查询呢？

我们已经推出了一个公式：

tree[1]+tree[2]+……tree[i]=a[i]

那么，对于1到r的区间和，即为：

 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)，所以有上述公式。

当然，对于更新操作也需要进行一些细微调整，详细的就看代码吧……

#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;
}