参考原文：

二维树状数组

我们先来讲讲怎么去表示。
数组A[][]的树状数组定义为：

C[x][y] = ∑ a[i][j], 其中，
x-lowbit(x) + 1 <= i <= x,
y-lowbit(y) + 1 <= j <= y.

例：举个例子来看看C[][]的组成。
设原始二维数组为：

A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},   
{a21,a22,a23,a24,a25,a26,a27,a28,a29},   
{a31,a32,a33,a34,a35,a36,a37,a38,a39}，   
{a41,a42,a43,a44,a45,a46,a47,a48,a49}};

那么它对应的二维树状数组C[][]呢？

记:
B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,…} 这是第一行的一维树状数组
B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,…} 这是第二行的一维树状数组
B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,…} 这是第三行的一维树状数组
B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,…} 这是第四行的一维树状数组
那么：
C[1][1]=a11,C[1][2]=a11+a12,C[1][3]=a13,C[1][4]=a11+a12+a13+a14,c[1][5]=a15,C[1][6]=a15+a16,…
这是A[][]第一行的一维树状数组

C[2][1]=a11+a21,C[2][2]=a11+a12+a21+a22,C[2][3]=a13+a23,C[2][4]=a11+a12+a13+a14+a21+a22+a23+a24,
C[2][5]=a15+a25,C[2][6]=a15+a16+a25+a26,…
这是A[][]数组第一行与第二行相加后的树状数组

C[3][1]=a31,C[3][2]=a31+a32,C[3][3]=a33,C[3][4]=a31+a32+a33+a34,C[3][5]=a35,C[3][6]=a35+a36,…
这是A[][]第三行的一维树状数组

C[4][1]=a11+a21+a31+a41,C[4][2]=a11+a12+a21+a22+a31+a32+a41+a42,C[4][3]=a13+a23+a33+a43,…
这是A[][]数组第一行+第二行+第三行+第四行后的树状数组

就是每一行都是一个树状数组，以行为元素，整个列也是一个树状数组。
（这句话请记住，这个思想会贯穿始终）
既然如此，我相信代码也很快就出来了，接下来我就来给出代码，并进行简单的解释。

单点修改
1
2
3
4
5
6
7
8
void add(int x,int y,int p){  
    while(x<=n){
        for(int i=y;i<=m;i+=lowbit(i)){
            C[x][i]+=p;
        } 
        x+=lowbit(x);
    }  
}  
这个根据我刚刚说的两个树状数组（那句贯穿始终的话），就很容易理解了。
我们外围循环枚举每一行，内循环在行内进行一维树状数组的单点修改，从而实现二维树状数组的单点修改。

以原点为一个端点的子矩阵和
1
2
3
4
5
6
7
8
9
10
int sum(int x,int y){  
    int result = 0;  
    while(x>0){
        for(int i=y;i>0;i-=lowbit(i)){
            result+=C[x][i];
        }
        x-=lowbit(x);
    }  
    return result;  
}  
以任意两点为左上和右下两个端点的子矩阵和
1
2
3
int ask(int x1,int y1,int x2,int y2){
    return sum(x2,y2)+sum(x1-1,y1-1)-sum(x2-1,y1)-sum(x1,y2-1);
}
逆序对
这个借助例题来讲解
题目
求冒泡排序交换了多少次，分析一下，不难看出就是求逆序对的个数，首先明白逆序对的概念给定i,j满足i < j && a[ i ]>a[ j ]则a[ i ]和a[ j ]就是一对逆序对。
求逆序对的做法，举个例子：
给定序列
9 6 4 8 7
遍历这个数组，每次遇到一个数，就把该数所在的树状数组的位置处的数加一：
1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0
初始数组值为0，代表插入0个数，sum(n)代表小于等于该数的个数，那么大于该数的个数就是i-sum(n)

1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 1
此时插入了一个数，sum(9)=1,1-1=0

1 2 3 4 5 6 7 8 9
0 0 0 0 0 1 0 0 1
sum(6)=1 2-1=1

1 2 3 4 5 6 7 8 9
0 0 0 1 0 1 0 0 1
sum(4)=1 3-1=2

1 2 3 4 5 6 7 8 9
0 0 0 1 0 1 0 1 1
sum(8)=3 4-3=1

1 2 3 4 5 6 7 8 9
0 0 0 1 0 1 1 1 1
sum(7)=3 5-3=2

上面所有的得数相加就得到了最后结果：
0+1+2+1+2=6
这就是思路，思路清楚了就可以做题了，可是这道题数据很大，明显开不了这么大得树状数组，一个简单得离散化就行了，先对树状数组按照值的大小进行排序，新开一个从序号1开始的连续的数组，一一映射到树状数组，最后对序号求逆序对就行了。

建立一个结构体包含val和id， val就是输入的数，id表示输入的顺序。然后按照val从小到大排序，如果val相等，那么就按照id排序。

如果没有逆序的话，肯定id是跟i（表示拍好后的顺序）一直一样的，如果有逆序数，那么有的i和id是不一样的。所以，利用树状数组的特性，我们可以简单的算出逆序数的个数。

如果还是不明白的话举个例子。（输入4个数）

输入：9 -1 18 5

输出 3.

输入之后对应的结构体就会变成这样
val：9 -1 18 5
id： 1 2 3 4
排好序之后就变成了
val ： -1 5 9 18
id： 2 4 1 3
2 4 1 3 的逆序数也是3
之后再利用树状数组的特性就可以解决问题了

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm> 
using namespace std;
const int maxn=500001;
int c[maxn];
struct Node
{
	int v,index;
	bool operator < (const Node &b) const
	{
		return v<b.v; //从小到大排序 
	}
}node[maxn];
int n;
void add(int i)
{
	while(i<=n)
	{
		c[i]++;
		i+=i&(-i);	
	}
}
long long getsum(int i)
{
	long long res=0;
	while(i>0)
	{
		res+=c[i];
		i-=i&(-i);
	}
	return res;
}
 
int main()
{
	while(1){
		cin>>n;
		if(n==0) break;
		int a;
		memset(node,0,sizeof node);
		memset(c,0,sizeof c);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a);
			node[i].index=i;
			node[i].v=a;
		}
		sort(node+1,node+1+n);
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			add(node[i].index);  //离散化结果—— 下标等效于数值
			ans+=i-getsum(node[i].index); //得到之前有多少个比你大的数（逆序对）
		}
		cout<<ans<<endl;
	}
	return 0;
}