树状数组求解逆序对数量详解

树状数组求解逆序对数量详解

引用

CSDN

1.

https://blog.csdn.net/2301_80328768/article/details/138295453

现在，给你一个数组a[]={5,4,2,6,3,1}
那么树状数组是怎么求出逆序对的数量的呢?

首先，给出一个朴素求解逆序对数量的思路:
对于一个数组a[],
使用for循环对其进行遍历,
当遍历到i时,再使用一个for循环从(1->i-1)

for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
        if (a[j] > a[i]) {
            ans++;
        }
    }
}  

那么可以使用树状数组对内层循环进行优化
上述代码可以简单的表述为:

for (int i = 1; i <= n; i++) {
    //循环到i
    //ans+=(从1到i-1)大于i的数量
    //注意上方的(从1到i-1)不是下标
    //    i
    //5 3 4 2 1
    //比如a[i]=4
    //ans+=(1,3)出现的数量
}
for (int i = n; i >= 1; i--) {
    //循环到i
    //ans+=(1到i-1)小于i的数量
    //注意上方的(从1到i-1)不是下标
    //    i
    //5 3 4 2 1
    //比如a[i]=4
    //ans+=(1,3)出现的数量
}  

所以 用树状数组s[x]表示[x-lowbit(x)+1,x]的和
sum(x)表示[1,x]数量和
如果在某个时刻,进入一个新数字6,
需要先调用树状数组的add函数维护:add(6,1)
我们只需要调用树状数组的函数sum(6-1)求出[1,5]的数量即可

接下来展示更详细:

从后向前：
从后来每进来一个数字调用add函数维护sx
比如add(1,1),调用函数时s[1]+1,s[2]+1,s[4]+1,s[8]+1.为什么s[3],s[5]..不加1?
因为s[x]表示[x-lowbit(x)+1,x]的范围 你这个范围内包含1 才会加1
答案加等于sum(a[i]-1),比如来到上图的4,查询(1,3)的数量(因为时从后向前 所以这(1,3)一定在4的后面)构成逆序对

//后
for (int i = n; i >= 1; i--) {
    add(a[i], 1);
    ans += sum(a[i] - 1);
}  

从前往后:
如图 来到3 我们寻找前面比它大的数字 可以用(下标-小于等于a[i]的数字==比他大的数字)

//前
for (int i = 1; i <= n; i++) {
    add(a[i], 1);
    ans += i - sum(a[i]);
}  

最后 离散化 可能数据会很大
例如 999 998 997 996 995
离散 5 4 3 2 1
"大于 等于"是相对的关系 所以离散化没关系 可以减少空间
网上许多离散化特别魔怔 大家用这个就行

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    b[i] = a[i];
}
sort(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
}  

例题
完整代码

//先介绍一下树状数组怎么求逆序对
//如果 从前向后 就是add(a[i],1) ans+=i-sum(a[i])
//如果 从后向前 就是add(a[i],1) ans+=sum(a[i]-1)
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int  N = 500005;
int n, a[N], b[N], s[N];
void add(int x, int k) {
    while (x <= n) {
        s[x] += k, x += x & -x;
    }
}
int sum(int x) {
    int t = 0;
    while (x) {
        t += s[x], x -= x & -x;
    }
    return t;
}
signed main() {
    cin >> n; int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    }
   // //前
   //for (int i = 1; i <= n; i++) {
   //     add(a[i], 1);
   //     ans += i - sum(a[i]);
   //}
    //后
    for (int i = n; i >= 1; i--) {
        add(a[i], 1);
        ans += sum(a[i] - 1);
    }
    cout << ans << endl;
}