树状数组解决逆序对问题c++-爱代码爱编程
文章首发于:My Blog 欢迎大佬们前来逛逛
前言
在算法竞赛中,求逆序对是一个常见的问题。逆序对是指在一个数列中,如果存在 i < j i < j i<j,且 a i > a j a_i > a_j ai>aj,那么 ( i , j ) (i,j) (i,j) 就是一个逆序对。例如,数列 2 , 4 , 1 , 3 , 5 {2, 4, 1, 3, 5} 2,4,1,3,5 中的逆序对有 ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) (1,3), (1,4), (2,3) (1,3),(1,4),(2,3),总共有 3 3 3 个逆序对。求逆序对的个数是一个经典的问题,可以使用多种算法来解决,其中树状数组是一种非常高效的算法。
树状数组
树状数组(Fenwick Tree)是一种高效的数据结构,用于维护数列的前缀和。树状数组的主要优势在于可以快速对数列进行单点更新和区间查询,时间复杂度均为 O ( log n ) O(\log n) O(logn)。因此,可以使用树状数组来计算逆序对的个数。
树状数组求逆序对
假设有一个长度为 n n n 的数列 a a a,现在需要求解它的逆序对个数。可以使用树状数组来实现,具体步骤如下:
- 从后往前遍历数列 a a a,对于每个数 a i a_i ai,使用树状数组查询小于 a i a_i ai 的数的个数 x x x;
- 将 a i a_i ai 加入树状数组,表示 a i a_i ai 已经被处理过;
- 由于 a i a_i ai 比 a i + 1 , a i + 2 , ⋯ , a n a_{i+1}, a_{i+2}, \cdots, a_n ai+1,ai+2,⋯,an 都小,因此逆序对的个数可以加上 x x x,表示这些数与 a i a_i ai 组成了逆序对;
- 重复步骤 1 1 1 到 3 3 3,直到遍历完整个数列;
- 根据树状数组的结果计算逆序对的个数,并输出结果。 具体实现时,需要使用一个数组 c c c 存储树状数组,其中 c i c_i ci 表示第 i i i 个位置存储的数的个数。树状数组的更新操作和查询操作可以使用以下代码实现:
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)
表示
x
x
x 的二进制表示中最低位的
1
1
1 所对应的值,即 lowbit(x) = x & -x
。 最终,根据树状数组的结果计算逆序对的个数,并输出结果。
过程演示:以 5 4 2 6 3 1数组为例,求它的逆序对:
- i=6,此时元素为1,首先查询比 1 小的元素的数量:query(0),sum=0;接着维护树状数组:update(1),c[1]=1,c[2]=1,c[4]=1,c[8]=1
- 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
- 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
- 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
- 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
- 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 来实现快速的更新和查询。希望本文能够对你有所帮助。