模板：
int n;
int tree[LEN]; int lowbit(int x){
return x&-x;
} void update(int i,int d){//index,delta
while(i<=n){
tree[i]+=d;
i+=lowbit(i);
}
} int getsum(int i){
int ans=;
while(i>){
ans+=tree[i];
i-=lowbit(i);
}
return ans;
}
示意图：
大佬代码：
//树状数组
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAX 500010
int c[MAX];
int aa[MAX];
int n;
typedef struct nano{
int val;
int order;
}node;
node in[MAX];
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int val)
{
while(x<=n){
c[x]+=val;
x+=lowbit(x);
}
}
int sum(int x)
{
int s=;
while(x>=)
{
s+=c[x];
x-=lowbit(x);
}
return s;//一开始竟然忘记写了这个语句，还以为树状数组写错了呢
}
bool cmp(node a,node b){
return a.val<b.val;
}
int main(int argc, char *argv[])
{
//freopen("2299.in", "r", stdin);
while(scanf("%d",&n)==&&n){
for(int i=;i<=n;++i)
{
scanf("%d",&in[i].val);
in[i].order=i;
}
sort(in+,in+n+,cmp);
for(int i=;i<=n;++i)
aa[in[i].order]=i;//离散化到小范围来
memset(c,,sizeof(c));
long long ans=;
for(int i=;i<=n;++i)
{
update(aa[i], );
ans+=(i-sum(aa[i]));
}
printf("%lld\n",ans);
}
return ;
}
大佬代码理解：
首先用结构体ｎｏｄｅ：{ｖａｌ，ｏｒｄｅｒ} 来存输入信息，用sort(in+1,in+n+1,cmp); 来根据ｖａｌ值进行排序，通过代码
for(int i=;i<=n;++i)
aa[in[i].order]=i;
构造数组ａａ，ａａ表示第ｉ个数排第ａａ［ｉ］位。（代码理解：ｉ表示原本的索引，in[i].order表示排序后的索引）
逆序数计算：
for(int i=;i<=n;++i)
{
update(aa[i], );
ans+=(i-sum(aa[i]));
}
ａｎｓ增量： 索引ｉ之前比他大的数。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x7f7f7f7f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define CT continue;
#define PF printf
#define SC scanf
const int mod=;
const int N=1e6+;
int n,m,c[N],pre[N],sum[N],a[N],ans[N]; struct node{
int l,r,pos;
}ne[N]; int lowbit(int i)
{
return i&(-i);
} void add(int p,int u)
{
while(p<=n)
{
c[p]^=u;
p+=lowbit(p);
}
} int query(int u)
{
int res=;
while(u>=)
{
res^=c[u];
u-=lowbit(u);
}
return res;
} bool cmp(node a,node b)
{
return a.r<b.r;
} map<int,int> mp;
int main()
{
while(~scanf("%d",&n))
{
MM(sum,);MM(pre,);MM(c,);
mp.clear();
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-]^a[i];
if(mp[a[i]]) pre[i]=mp[a[i]];
mp[a[i]]=i;
}
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&ne[i].l,&ne[i].r);
ne[i].pos=i;
}
sort(ne+,ne+m+,cmp);
int i=;
for(int k=;k<=m;k++)
{
for(;i<=ne[k].r;i++)
{
if(pre[i]) add(pre[i],a[i]);
add(i,a[i]);
}
ans[ne[k].pos]=(query(ne[k].r)^query(ne[k].l-)^sum[ne[k].r]^sum[ne[k].l-]);
}
for(int i=;i<=m;i++) printf("%d\n",ans[i]);
}
return ;
}
3.模板编写训练1：P3368 【模板】树状数组 1
代码：
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <map> #define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 500010
#define MAX 1<<30
#define V vector<int>
#define ll long long using namespace std; inline int read(){
int s=,w=;
char ch=getchar();
while(ch<=''||ch>''){if(ch=='-')w=-;ch=getchar();}
while(ch>=''&&ch<='') s=s*+ch-'',ch=getchar();
return s*w;
} inline ll max(ll a,ll b){
return a>b?a:b;
} ll N;
ll tree[LEN]; int lowbit(int x){
return -x&x;
} ll getsum(int p){
ll sum=;
while(p>){
sum+=tree[p];
p-=lowbit(p);
}
return sum;
} void update(int p,ll v){
while(p<=N){
tree[p]+=v;
p+=lowbit(p);
}
} int main(){
// freopen("D:\\CbWorkspace\\ACM数据结构\\树状数组\\模板1.txt","r",stdin);
int m,i,t,op;
int a,b;
scanf("%d%d",&N,&m);
for(i=;i<=N;i++){
I("%d",&t);
update(i,t);
}
for(i=;i<=m;i++){
I("%d%d%d",&op,&a,&b);
switch(op){
case :
update(a,b);
break;
case :
printf("%lld\n",getsum(b)-getsum(a-));
break;
}
}
return ;
}
4.模板编写训练1：P3368 【模板】树状数组 2
代码：
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <map> #define I scanf
#define OL puts
#define O printf
#define F(a,b,c) for(a=b;a<c;a++)
#define FF(a,b) for(a=0;a<b;a++)
#define FG(a,b) for(a=b-1;a>=0;a--)
#define LEN 500010
#define MAX 1<<30
#define V vector<int>
#define ll long long using namespace std; inline int read(){
int s=,w=;
char ch=getchar();
while(ch<=''||ch>''){if(ch=='-')w=-;ch=getchar();}
while(ch>=''&&ch<='') s=s*+ch-'',ch=getchar();
return s*w;
} inline ll max(ll a,ll b){
return a>b?a:b;
} ll N;
ll tree[LEN]; int lowbit(int x){
return -x&x;
} ll getsum(int p){
ll sum=;
while(p>){
sum+=tree[p];
p-=lowbit(p);
}
return sum;
} void update(int p,ll v){
while(p<=N){
tree[p]+=v;
p+=lowbit(p);
}
} int main(){
// freopen("D:\\CbWorkspace\\ACM数据结构\\树状数组\\模板2.txt","r",stdin);
int m,i,t,op,pre=;
int a,b,c;
scanf("%d%d",&N,&m);
for(i=;i<=N;i++){
I("%d",&t);
update(i,t-pre);
pre=t;
}
for(i=;i<=m;i++){
I("%d",&op);
switch(op){
case :
I("%d%d%d",&a,&b,&c);
update(a,c);
update(b+,-c);
break;
case :
I("%d",&a);
printf("%lld\n",getsum(a));
break;
}
}
return ;
}
注：使用差分数组