树状数组求逆序数（离散化）

树状数组是一种能快速求出前n项和的数据结构，

例如：数组a0，a1，a2，a3，a4，a5....an。

sum（a[4]）求的就是a0+a1+a2+a3+a4。

sum（a[n]-a[4]）求的就是a5+...+an。

时间复杂度为o（nlogn）。

 

离散化  就是把原来的一组数变成另一组数，但是他们的相对大小不变。比如

把       4  6  8  9  2

变成   2  3  4  5  1

他们的逆序数不变

 

下面贴代码：

#include<iostream>
#include<cmath>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=1000000+5;
int b[MAXN],c[MAXN];
int n;
struct node
{
	int num,id;
}a[MAXN];
bool cmp(node a,node b)
{
	return(a.num<b.num);
}
void add(int i)//更新树状数组
{
	while(i<=n)
	{
		c[i]++;
		i+=i&(-i);
	}
}
int sum(int i)//树状数组求和
{
	int totle;
	while(i>0)
	{
		totle+=c[i];
		i-=i&(-i);
	}
	return(totle);
}
int main()
{
	int i,T;
	__int64 ans;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i].num);//记录数据
			a[i].id=i;//记录是第几个输入的
		}
		sort(a+1,a+n+1,cmp);
		b[a[1].id]=1;//最小的那个变成1，次小的那个变成2，以此类推...
		for(i=2;i<=n;i++)
		{
			if(a[i].num!=a[i-1].num)
				b[a[i].id]=i;
			else b[a[i].id]=b[a[i-1].id];
		}
		ans=0;
		for(i=1;i<=n;i++)
		{
			add(b[i]);
			ans+=(__int64)(sum(n)-sum(b[i]));//求到目前为止比这个数大的有多少个
		}
		printf("%I64d\n",ans);
	}
	return(0);
}