原题链接 https://www.luogu.org/problemnew/show/P3368
这个题和洛谷P3374树状数组1 有些不同，在普通的树状数组上运用了差分的知识。（由于P3374涉及到一些较为基础的知识，就先不讲了，反正大家都会了QwQ~）；
什么是差分呢？
差分差分，顾名思义就是相差的分数啦 ，其实就是每一项与前一项的差距，通常我们用d数组来表示。
举个例子，假如我们有一个序列：
a=1，a=5，a=6，a=3，a=4；
那么可以计算出每一项的差分：
d=a - a =1 - 0 = 1；（第一项的差分就是原数）
d=a - a =5 - 1 = 4；
d=a - a =6 - 5 = 1；
d=a - a =3 - 6 = -3；
d=a - a =4 - 3 = 1；
有的小盆友就要问了：知道这个差分有啥用嘞？
这是树状数组“区间修改，单点查询”的关键！
考虑一个简单的小问题：知道了d，怎么求a？
It is so easy ！
a = a+ d = a + d + d = a + d + d + d = a + d + d + d + d = d + d + d + d+ d
也就是说，a= d + d + d + ……+ d
这一看不就是差分数组的前缀和嘛？正好我们可以用树状数组来维护前缀和：
void add(int x,int k) //在第x个数上加个k
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=k;
}
int ask(int x) //询问区间[1,x]的和
{
int ans=;
for(int i=x;i;i-=lowbit(i))
ans+=c[i];
return ans;
}
又有小盆友来问了：不是你是用原数组求得差分，再用差分求回去，干啥嘞？只为了用树状数组维护前缀和？直接输出 a [ n ] 不好嘛？
其实这只是为了区间修改方便！
普通（暴力）区间修改思路：
for循环从l~r暴力枚举每个点然后加上某个值，最差的时间复杂度是O（q * n），q是操作次数，这显然会TLE；
但是我们用了差分以后就不一样了，考虑一下区间修改后对差分数组的影响：
原先：
a： 1 5 6 3 4
d： 1 4 1 -3 1
在区间[3,5]上每个数都加上2：
a： 1 5 8 5 6
d： 1 4 3 -3 1
一个很显然的结论：对于修改的区间[ l，r ]，让这个区间内每个数加上x，对于差分数组d其实就是d[ l ] 加上x，d [ r + 1 ] 减去x（不懂的看上面的例子感性理解下）；
所以我们只需要用树状数组维护两次前缀和就好啦！
完整代码如下：
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int read()
{
char ch=getchar();
int a=,x=;
while(ch<''||ch>'')
{
if(ch=='-') x=-x;
ch=getchar();
}
while(ch>=''&&ch<='')
{
a=(a<<)+(a<<)+(ch-'');
ch=getchar();
}
return a*x;
}
int n,m,x,y,k,q;
int a[],d[],c[];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int k) //在第x个数上加个k
{
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=k; //加上lowbit去找它的父亲
}
int ask(int x) //询问区间[1,x]的和
{
int ans=;
for(int i=x;i;i-=lowbit(i)) //区间长度不断缩小
ans+=c[i];
return ans;
}
int main()
{
n=read();m=read(); //n个数，m次操作
for(int i=;i<=n;i++)
{
a[i]=read();
d[i]=a[i]-a[i-]; //算出每一项的差分是多少
add(i,d[i]); //注意这里维护的是差分数组
}
for(int i=;i<=m;i++)
{
q=read();
if(q==)
{
x=read();y=read();k=read(); //[x,y]加上k
add(x,k); //左端点差分+k
add(y+,-k); //右端点的右边的差分-k
}
else
{
x=read();
printf("%d\n",ask(x)); //差分前缀和，就是某一项的值
}
}
return ;
}