树状数组求逆序对

发表于 | 更新于 | 分类于

树状数组

思想

以当前这个数下标i为标准，遍历前面(0 ~ i - 1)的数，如果大于a[i]则逆序对数 + 1，
然后运用桶排序的思想，用a[j]的值作为下标，出现则记录为 1，运用树状数组维护前a[i]个数的和
然后用 i - sum(a[i]) 即得到前i个数中本应该小于却没有小的数(即逆序对数)
bit数组bit[x]代表从a[x - lowbit(x) + 1] ~ a[x]的和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#define lowbit(x) (x & -x)			//lowbit() 运算，取当前第一个 1 出现的位置 
using namespace std;
const int N = 1e5 + 4;
int bit[N];			//bit数组，用二进制思想维护和
int n, a[N];		//a数组可有可无，bit的创建通过add(location, value)来确定
int sum(int i)			//取和操作 
{
	int s = 0;			//得到前i个元素的和 
		 		//例 : 6 二进制 110, 第一次为自己本身即 	s += bit[6]
					//第二次减去从右往左的第一个1 变为 100 即为4 s += bit[4]
				//第三次再减去1变为 0 退出  即先使用值再减去第一个 1 
	for( ; i ; i -= lowbit(i))	
		s += bit[i];
	return s;
}

void add(int i, int x)			//i为位置，x为增量
{
		//与取和操作相反先对 i进行更新，然后加上第一个1之范围会包含原来这个区间，范围更大，都进行更新
				//区间最大边界要 <= 最大长度 
	
     for( ; i <= n; i += lowbit(i) )		//n为最大限制范围
         bit[i] += x;	
}
int main()
{
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];		//顺序输入 
		add(a[i], 1);		 //这个数值进行更新 
		ans += i - sum(a[i]);		//本应小于却没有小于数的个数即为逆序对个数 
	}
	cout << ans << endl;
	return 0;
}
0%