树状数组解决逆序对问题c++

前言

在算法竞赛中，求逆序对是一个常见的问题。逆序对是指在一个数列中，如果存在 ，且 ，那么 就是一个逆序对。例如，数列 中的逆序对有 ，总共有

树状数组

树状数组（Fenwick Tree）是一种高效的数据结构，用于维护数列的前缀和。树状数组的主要优势在于可以快速对数列进行单点更新和区间查询，时间复杂度均为 。因此，可以使用树状数组来计算逆序对的个数。

树状数组求逆序对

假设有一个长度为 的数列 ，现在需要求解它的逆序对个数。可以使用树状数组来实现，具体步骤如下：

1. 从后往前遍历数列 ，对于每个数 ，使用树状数组查询小于 的数的个数 ；
2. 将 加入树状数组，表示
3. 由于 比 都小，因此逆序对的个数可以加上 ，表示这些数与
4. 重复步骤 到 ，直到遍历完整个数列；
5. 根据树状数组的结果计算逆序对的个数，并输出结果。 具体实现时，需要使用一个数组 存储树状数组，其中 表示第

c++Copy code// 更新树状数组
void update(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
}
// 查询树状数组
int query(int x) {
    int res = 0;
    while (x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

其中 lowbit(x) 表示 的二进制表示中最低位的 所对应的值，即 lowbit(x) = x & -x。 最终，根据树状数组的结果计算逆序对的个数，并输出结果。

过程演示：以 5 4 2 6 3 1数组为例，求它的逆序对：

1. i=6，此时元素为1，首先查询比 1 小的元素的数量：query(0)，sum=0；接着维护树状数组：update(1)，c[1]=1，c[2]=1，c[4]=1，c[8]=1
2. i=5，此时元素为3，首先查询比 3 小的元素的数量：query(2)，查询到c[2]=1，sum+=c[2]，sum=1；接着维护树状数组：update(3)，c[3]=1，c[4]=2，c[8]=2
3. i=4，此时元素为6，首先查询比 6 小的元素的数量：query(5)，5可以分解为5和4，因此查询到c[4]=2，c[5]=0，sum+=c[4]，sum=3；接着维护树状数组：update(6)，c[6]=1，c[8]=3
4. i=3，此时元素为2，首先查询比 2 小的元素的数量：query(1)，因此查询到c[1]=1，sum+=c[1]，sum=4；接着维护树状数组：update(2)，c[2]=2，c[4]=3，c[8]=4
5. i=2，此时元素为4，首先查询比 4 小的元素的数量：query(3)，3可以分解为3和2，因此查询到c[3]=1，c[2]=2，sum+=c[3]+=c[2]，sum=7；接着维护树状数组：update(4)，c[4]=4，c[8]=5
6. i=1，此时元素为5，首先查询比 5 小的元素的数量：query(4)，因此查询到c[4]=4，sum+=c[4]，sum=11；接着维护树状数组：update(2)，c[2]=1，c[4]=3，c[8]=4

以下是完整的 C++ 代码实现：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, a[MAXN], c[MAXN];
// 计算 x 的 lowbit
inline int lowbit(int x) { return x & -x; }
// 更新树状数组
void update(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
}
// 查询树状数组
int query(int x) {
    int res = 0;
    while (x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    // 读入数据
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    // 计算逆序对个数
    long long ans = 0;
    for (int i = n; i >= 1; i--) {
        ans += query(a[i] - 1);
        update(a[i], 1);
    }
    // 输出结果
    printf("%lld\n", ans);
    return 0;
}

总结

树状数组是一种高效的数据结构，用于维护数列的前缀和。使用树状数组可以高效地计算逆序对的个数。树状数组的核心思想是利用二进制的特性，通过计算每个数的 lowbit 来实现快速的更新和查询。希望本文能够对你有所帮助。