题解 | #数组中的逆序对#

和大家讲解一下树状数组求逆序对的方法

例如：
tree：0 0 0 0 0
x=4:
tree: 0 0 0 0 1
然后对x进行查询read(x)，可以得到x之前插入了多少个数，因为x之前插入的数都比x小，所以用当前插入的数的总数i减去read(x)可以得到当前插入的i个数中有多少个比x大，即x有多个逆序对。
离散化： 如果插入的x很大，每次对x进行查询，时间用的多，且tree的空间不够。这时候需要进行离散化。具体做法是每次输入一个数的同时记录下该数输入的顺序是多少。然后对输入的数进行排序。

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x)&(-x)
const int maxn=1e5;
using namespace std;
ll n,tree[maxn];
struct node
{
	int val;
	int id;
}arr[maxn];
bool cmp(node a,node b)
{
	return a.val<b.val;
}
void update(int k,int a)
{
	while(k<=n)
	{
		tree[k]+=a;
		k+=lowbit(k);
	}
}
ll read(ll k)
{
	ll sum=0;
	while(k)
	{
		sum+=tree[k];
		k-=lowbit(k);
	}
	return sum;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i].val;
		arr[i].id=i;      
	}
	sort(arr+1,arr+n+1,cmp);
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		update(arr[i].id,1);
		ans+=(i-read(arr[i].id));
		//cout<<arr[i].id<<" "; 
	}
	  cout<<ans<<endl;
	return 0;
}