参考：算法学习（二）——树状数组求逆序数 、线段树或树状数组求逆序数（附例题）
应用树状数组 || 线段树求逆序数是一种很巧妙的技巧，这个技巧的关键在于如何把原来单纯的求区间和操作转换为 求小于等于a的数的总数 再转换为 求序列里大于a的数的总数，学习这个技巧源于一道题目 poj 3067 Japan （一道需要YY后运用这个技巧求解的题目），此外这个技巧也让我联想到 树状数组区间加/单点求值的技巧（基于区间加法的思维），话不多说，开始正题。
一、什么是逆序数？
在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。一个排列中所有逆序总数叫做这个排列的逆序数。也就是说，对于n个不同的元素，先规定各元素之间有一个标准次序（例如n个 不同的自然数，可规定从小到大为标准次序），于是在这n个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有1个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。
举个栗子：如2431中，21，43，41，31是逆序，逆序数是4。
二、如何用树状数组求逆序数？
1、定义： a[ i ] 储存原始序列（事实上只需要一个变量 a 就ok了）, i 即 出现的顺序；c[ k ] 树状数组 k 为 a[ i ]。
2、步骤：按顺序输入储存原始序列 a[ i ] ， 输入的同时维护 c[ i ] , a[i] 出现 c[ a[i] ] 则加一， add（a[ i ], 1)；所以用数组数组求（1， a[i]) 的区间和的意义就变成了统计小于等于 a[ i ] 的数的个数， 若当前序列总数为 N， 则 N - sum( a ) 就是长度为N的序列中比 a 大的数字的总数了。
3、举个栗子：2431 ans = 0 + 0 + 1 + 3 = 4; 分别是(21, 43, 41, 31)。
| i | a[ i ] | k | c[ 1 ] ~ c[ 4 ] | i - sum( k ) |
| 1 | 2 | 2 | 0 1 0 0 | 1 - 1 = 0 |
| 2 | 4 | 4 | 0 1 0 1 | 2 - 2 = 0 |
| 3 | 3 | 3 | 0 1 1 1 | 3 - 2 = 1 |
| 4 | 1 | 1 | 1 1 1 1 | 4 - 1 = 3 |
4、贴个代码：
///树状数组求逆序数
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int MAXN = ;
int c[MAXN];
int N; int lowbit(int x) ///实现树状数组需要的基本函数
{
return x&(-x);
} void add(int i, int value)
{
while(i <= N)
{
c[i]+=value;
i+=lowbit(i);
}
} int sum(int i)
{
int res = ;
while(i > )
{
res+=c[i];
i-=lowbit(i);
}
return res;
}
int main()
{
while(~scanf("%d", &N))
{
int ans = ;
memset(c, , sizeof(c));
for(int i = ; i <= N; i++)
{
int a;
scanf("%d", &a);
add(a, );
ans+=i-sum(a);
}
printf("%d\n", ans);
}
return ;
}
三、如何用线段树求逆序数
与树状数组原理，只不过实现的区间求和的方式不同罢了
直接贴代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#define L(a) a<<1
#define R(a) (a<<1)|1
const int maxn = ;
int ans[maxn];
struct node{
int num,l,r;
}tree[maxn<<];
int n;
void Build(int m,int l, int r){
tree[m].l=l;
tree[m].r=r;
if(tree[m].l==tree[m].r){
tree[m].num=;
return ;
}
int mid = (tree[m].l+tree[m].r)>>;
Build(L(m),l,mid);
Build(R(m),mid+,r); //并不要回溯， 建立空树
}
void Insert(int m,int l,int r,int x){
if(tree[m].l==l&&tree[m].r==r){
tree[m].num+=x; return ;
}
int mid = (tree[m].l+tree[m].r)>>;
if(r<=mid)
Insert(L(m),l,r,x);
else if(l>mid)
Insert(R(m),l,r,x);
else{
Insert(L(m),l,mid,x);
Insert(R(m),mid+,r,x);
}
tree[m].num=tree[L(m)].num+tree[R(m)].num;
}
int Query(int m,int l,int r){
if(tree[m].l==l&&tree[m].r==r)
return tree[m].num;
int mid = (tree[m].l+tree[m].r)>>;
if(r<=mid)
return Query(L(m),l,r);
if(l>mid)
return Query(R(m),l,r);
return Query(L(m),l,mid)+Query(R(m),mid+,r);
}
int main(){
int a,n,i,t; int k=;
scanf("%d",&n);
memset(tree,,sizeof(tree));
Build(,,n);
for(int i=;i<=n;i++)
{
scanf("%d",&ans[i]);
}
for(int i=;i<=n;i++){
Insert(,ans[i],ans[i],);// 每个位置插入1
k+=(i - Query(,,ans[i]));
}
printf("%d\n",k); return ;
}
四、几道题目
1、HDU 1394
思路：树状数组+暴力（每次a[ i ] 掉到最后的时候 减去比 a[ i ] 小的数, 加上比 a[ i ] 大的数）
Ac Code:
///HDU 1394 树状数组 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std; const int MAXN = ; int N;
int c[MAXN], a[MAXN]; int lowbit(int x)
{
return x&(-x);
} void add(int i, int value)
{
while(i <= N)
{
c[i]+=value;
i+=lowbit(i);
}
} int sum(int i)
{
int res = ;
while(i > )
{
res+=c[i];
i-=lowbit(i);
}
//printf("%d\n" ,res);
return res;
} int main()
{
int cnt = ;
while(~scanf("%d", &N))
{
cnt = ;
memset(c, , sizeof(c));
memset(a, , sizeof(a));
for(int i = ; i <= N; i++)
{
scanf("%d", &a[i]);
a[i]++;
add(a[i], );
cnt+=i-sum(a[i]);
} int ans = cnt;
//printf("%d\n", ans);
for(int i = ; i <= N; i++)
{
a[i]--;
cnt = cnt-a[i]*+N-;
ans = min(ans, cnt);
//printf("%d\n", ans);
}
printf("%d\n", ans);
}
return ;
}