树状数组的一系列操作
1、树状数组求逆序对
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,a[maxn],b[maxn],c[maxn],s[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]++;
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),s[i]=a[i];
sort(a+1,a+n+1);
int sum=unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;i++)
{
int pos=lower_bound(a+1,a+sum+1,s[i])-a;
b[i]=pos;
}
int ans=0;
for(int i=n;i>=1;i--)
{
ans+=getsum(b[i]);
add(b[i]+1);
}
cout<<ans;
return 0;
}2、树状数组区间修改
这里由于涉及到区间修改，所以我们要引入差分的思想。
差分数组c[]：我们设sigma(c，i)表示c数组的前i项和，调用一次的复杂度是log2(i)
设原数组是a[n]，差分数组c[n]，c[i]=a[i]-a[i-1]，那么明显地a[i]=sigma(c,i)，如果想要修改a[i]到a[j]，只需令c[i]+=v,c[j+1]-=v
明白了上面的原理以后，就可以直接看代码了
/*区间修改+单点查询*/
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=500010;
int n,m,a[maxn],c[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=y;
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
int x,y,z,k;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
add(i,a[i]-a[i-1]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&k);
if(k==1)
{
scanf("%d%d%d",&x,&y,&z);
add(x,z);add(y+1,-z);
}
else
{
scanf("%d",&x);
printf("%d
",getsum(x));
}
}
return 0;
}/*单点修改+区间查询*/
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=500010;
int n,m,c[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=y;
}
int getsum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
int x,y,k;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
add(i,x);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&k);
if(k==1)
{
scanf("%d%d",&x,&y);
add(x,y);
}
else
{
scanf("%d%d",&x,&y);
printf("%d
",getsum(y)-getsum(x-1));
}
}
return 0;
}注意：
树状数组c[]始终是前缀和数组，即：getsum(i)始终得到的是点i的前缀和。
区间修改是将树状数组变成了差分数组，所以getsum(i)得到的是差分前缀和，由上面的推导，i的差分前缀和，就是点i的值，所以getsum(i)是单点查询，即：getsum(i)==a[i]
单点修改不需要差分，所以树状数组维护的就是x的前缀和，即getsum(x)==a[1]+a[2]+……+a[x]，此时getsum()函数变成了区间查询函数
举个例子：x~y的区间和==getsum(y)-getsum(x-1)
拓展：
（两个差分数组还原了前缀和数组orz~~）
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=200010;
int n,m,s[maxn],t[maxn],r[maxn];
int lowbit(int x)
{
return x&(-x);
}
void add1(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
t[i]+=y;
}
void add2(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
r[i]+=y;
}
int find1(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=t[i];
return ans;
}
int find2(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
ans+=r[i];
return ans;
}
int getsum(int x)
{
int ans=0;
ans=s[x]+(x+1)*find1(x)-find2(x);
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
s[i]=s[i-1]+x;
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x,y,z,w;
scanf("%d",&w);
if(w==1)
{
scanf("%d%d%d",&x,&y,&z);
add1(x,z);add1(y+1,-z);
add2(x,x*z);add2(y+1,(y+1)*(-z));
}
else
{
scanf("%d%d",&x,&y);
printf("%d
",getsum(y)-getsum(x-1));
}
}
return 0;
}