树状数组求逆序对数

前置芝士：树状数组

树状数组求逆序对数

逆序数的定义：对于一个数列$a_n$所有满足$a_i > a_j$ 且 $i < j$的二元组的个数称为逆序数。

做法

假如我们有一列数:

对于一个数$i$，我们把第$i$位++，之后在统计1 ~ i的区间和，这个区间和便是$i$的顺序对，用$i$再减去这个数即为逆序对。

为什么这样能行得通呢，我们回想一下逆序对的定义，$a_i > a_j$ 且 $i < j$的二元组，我们在按原数组顺序插入如的时候，其实已经保证了$i < j$，我们插入又恰恰满足了，$a_i > a_j$。

例如我们有以下元素：

$$2,1,4,7$$

我们从前往后插入进树状数组内，

先插入$2$，第$2$个位置的数据=1。

查询1~2的区间和，为$1$，所以他的顺序对数为$1$，逆序对数为$1-1=0$。

位置	1	2	3	4	5	6	7
树状数组	1
数据	1

再插入$1$，把第$1$个位置的数据=1。

查询1~1的区间和，为$1$，所以他的顺序对数为$1$，逆序对数为$2-1=1$。

位置	1	2	3	4	5	6	7
树状数组	1	1
数据	1	2

再插入$4$，把第$4$个位置的数据=1。

查询1~1的区间和，为$4$，所以他的顺序对数为$3$，逆序对数为$3-3=0$。

位置	1	2	3	4	5	6	7
树状数组	1	1	1
数据	1	2	1

再插入$7$，把第$7$个位置的数据=1。

查询1~1的区间和，为$4$，所以他的顺序对数为$4$，逆序对数为$4-4=0$。

位置	1	2	3	4	5	6	7
树状数组	1	1	1	1
数据	1	2	1	1

代码实现 以洛谷P1908 逆序对 为例

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

#define endl '\n'
#define maxn 500005

struct node
{
    long long data, rk;
    bool operator< (const node &b)const  //供排序用
    {
        if (data == b.data)
            return rk < b.rk;
        return data < b.data;
    }
} c[maxn];

long long n, a[maxn], _rank[maxn];

inline long long lowbit(long long x)
{
    return x & (-x);
}

inline void add(long long pos, long long x)
{
    for (register long long i = pos; i <= n; i += lowbit(i))
        a[i] += x;
}

inline long long sum(long long pos)
{
    long long sum = 0;
    for (register long long i = pos; i >= 1; i -= lowbit(i))
        sum += a[i];
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (register long long i = 1; i <= n; i++) //输入数据
    {
        cin >> c[i].data;  
        c[i].rk = i; //c[i]在数组中的序号
    }

    sort(c + 1, c + n + 1); //排序（离散化）

    for (register long long i = 1; i <= n; i++)
        _rank[c[i].rk] = i; //求相对大小

    /*
    //  1 2 10000
    //  1 2 3
    //上面两个序列在本题是等效的，因为无论第三项是3还是10000，它都大于第一项和第二项

    我们的目标是把原先大的数缩小

    因为排完序的序列和原序列长度相同
    以1为例：
    我们令原先c[1].rk(即最小的数位置)等与1。
    接着我们令原先c[2].rk(即次小的数位置)等与2。
    这便起到缩小数据的作用
    */

    long long ans = 0;
    for (register long long i = 1; i <= n; i++)
    {
        add(_rank[i], 1);
        ans += i - sum(_rank[i]);  //求逆序对
    }
    cout << ans << endl;
    return 0;
}