概念：
树状数组的初衷是解决状态压缩空间里的累积频率，现在多用于求前缀和与后缀和(方便计算)，它可以以 O(logN)的时间得到任意前缀和，并同时支持在 O(logN)时间内支持动态单点值的修改。空间复杂度 O(N)。
树状数组的引用：
树状数组最重要的作用便是修改与查询，分为单点修改和区间查询，区间修改和单点查询，区间修改和区间查询。
关于修改(即add，维护数组)的想法：我们一般是挨个维护数组，而树状数组用区间来维护，当我们修改单点时，我们只需修改包含该点的元素，即其父节点！求区间和时也只需将每个区间的父节点相加即可(一个父节点包括一个区间的数)，求区间和时只需S[1,B]-S[1,A-1]即可。
修改时候可以发现是个“爬树”的过程，一路往上更新，直到MAX(树状数组最大容量）！
树状数组的实现：
前面已经讲得很详细了，代码实现倒是一件简单的事了。不过我们需要先解决一个问题：lowbit怎么算？如果一位一位验证的话，会形成额外的时间开销。然而，我们有这样神奇的一个公式：
low(x)=(x)&(−x)
为什么可以这样？我们需要知道，计算机里有符号数一般是以补码的形式存储的。-x相当于x按位取反再加1，会把结尾处原来1000...的形式，变成0111...，再变成1000...；而前面每一位都与原来相反。这时我们再把它和x按位与，得到的结果便是lowbit(x)。
这样就能愉快的写出树状数组(模板)啦：
单点修改and区间查询：
初始化的时候，我们只需要cnt[i]每个点的初始值即可。
//修改
ll add(ll x,ll y)
{
for(ll i=x;i<=n;i+=lowbit(i))
{
cnt[i]+=y;
}
}
//求前n项和
ll query(ll x)
{
ll sum=0;
for(ll i=x;i;i-=lowbit(i)
{
sum+=cnt[i];
}
return aum;
}
//求区间和
return query(B)-query(A-1);模板[1]：
//单点修改，区间查询
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll>a(5e5+5),b(5e5+5);
ll n,k;
ll lowbit(ll x)
{
return x&(-x);
}
void add(ll x,ll y)
{
for(ll i=x;i<=n;i+=lowbit(i))
{
b[i]+=y;
}
}
void query(ll x,ll y)//前缀和相减求区间和
{
ll sum=0;
for(ll i=x-1;i;i-=lowbit(i))
{
sum-=b[i];
}
for(ll i=y;i;i-=lowbit(i))
{
sum+=b[i];
}
cout<<sum<<'\n';
}
void solve()
{
cin>>n>>k;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
add(i,a[i]);//该节点与父节点及右侧2的幂的点都加上该数，利于求区间和
}
ll t,x,y;
while(k--)
{
cin>>t>>x>>y;
if(t==1)
{
add(x,y);//同理
}
else{
query(x,y);//前缀和差
//cout<<query(x,y)<<'\n';
}
}
}
int main()
{
//ll t;cin>>t;
//while(t--)
solve();
}区间修改and单点查询：
此时我们需要的是差分数组，查询单点的时候，只需求该点的前n项和即可(差分数组的前n项和即原数组在该点的值)。
模板[2]：
//区间修改，查询单点
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,m;
ll c[500005],a[500005];
ll lowbit(ll x)
{
return x&(-x);
}
void add(ll x,ll z)
{
for(ll i=x;i<=n;i+=lowbit(i))
{
c[i]+=z;
}
}
ll query(ll x)
{
ll sum=0;
for(ll i=x;i;i-=lowbit(i))//差分前缀和
{
sum+=c[i];
}
return sum;
}
void solve()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
add(i,a[i]-a[i-1]);//差分数组
}
ll t,x,y,z;
while(m--)
{
cin>>t;
if(t==1)
{
cin>>x>>y>>z;
add(x,z);//原本差分数组只用修改一次，但是其含有多级父节点，故需要多次修改
add(y+1,-z);
}
else{
cin>>x;
cout<<query(x)<<'\n';//差分前缀和
}
}
}
int main()
{
//ll t;cin>>t;
//while(t--)
solve();
return 0;
}区间修改and区间查询：
咱们知道a[n]等于差分数组前n项和，如果求一个区间的话，便是这个区间每个数的前n项和。
硬算肯定TLE，手推可得：
核心公式：
n *(c[1]+c[2]+……+c[n])-(0 *c[1]+1 *c[2]+...+(n-1)*c[n])
模板[3]：
// ****n *(c[1]+c[2]+……+c[n])-(0 *c[1]+1 *c[2]+...+(n-1)*c[n])*****
//区间修改,区间查询
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,m;
ll c[100005],a[100005],b[100005];
ll lowbit(ll x)
{
return x&(-x);
}
///
void add(ll x,ll z)
{
for(ll i=x;i<=n;i+=lowbit(i))
{
c[i]+=z;
}
}
///
void added(ll x,ll z)
{
for(ll i=x;i<=n;i+=lowbit(i))
{
b[i]+=z;
}
}
/
ll query(ll x)
{
ll sum=0;
for(ll i=x;i;i-=lowbit(i))
{
sum+=c[i];
}
return sum;
}
/
ll queryed(ll x)
{
ll sum=0;
for(ll i=x;i;i-=lowbit(i))
{
sum+=b[i];
}
return sum;
}
/
void solve()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
{
cin>>a[i];
add(i,a[i]-a[i-1]);//差分数组
added(i,(i-1)*(a[i]-a[i-1]));//待减差分数组，即：(0 *c[1]+1 *c[2]+...+(n-1)*c[n])；
}
ll t,x,y,z;
while(m--)
{
cin>>t;
if(t==1)
{
cin>>x>>y>>z;
add(x,z);//多级父节点，故需要多次修改，为了使用前缀和
add(y+1,-z);
added(x,z*(x-1));
//同理：即 (0 *c[1]+1 *c[2]+...+(n-1)*c[n])；
added(y+1,-z*(y));
}
else{
cin>>x>>y;
ll sum1=0,sum2=0;
sum1=(x-1)*query(x-1)-queryed(x-1);//a[x-1]的前缀和
sum2=y*query(y)-queryed(y);//a[y]的前缀和
//即：*****n *(c[1]+c[2]+……+c[n])-(0 *c[1]+1 *c[2]+...+(n-1)*c[n])*****
cout<<sum2-sum1<<'\n';
}
}
}
int main()
{
//ll t;cin>>t;
//while(t--)
solve();
return 0;
}
