首先在这里提一下,逆序对一般有两种解法,一种是归并排序,另一种就是本篇博客要讲的树状数组
什么是逆序对呢?
百度百科是这样解释的:
对于一个包含N个非负整数的数组A[1..n],如果有i < j,且A[ i ]>A[ j ],则称(A[ i] ,A[ j] )为数组A中的一个逆序对
用人话来说就是:数组中排在后面的值比前面的值小,就可以组成一组逆序对,比如 1 2 4 3
,4和3就可以组成一组逆序对
逆序对个数就是逆序对的总数,比如:
1 2 3 4 4 5
这个数组中,逆序对个数为05 4 3 2 1
这个数组中,逆序对的个数就是 4 + 3 + 2 + 1 = 10
什么是树状数组呢?
树状数组(binary Indexed Tree),是一种动态且高效的数据结构,主要用来解决 洛谷P3374 这种类型的题,效率比使用传统数组(O(n^2^))更高(O(logn))
我们这里只说区间查询,单点更新的树状数组,其他的我以后再更新
在树状数组中,有一个重要的概念:lowbit,这是用来求一个数的二进制数末尾连续的0的个数的函数,实现起来也很简单
lowbit函数
int lowbit(int x)
{
return x & (-x);
}
lowbit另一种写法不讲了
树状数组怎么工作的我不想讲,详细的请看:视频原地址我这里只提供我验证以后没问题的代码
树状数组单点更新函数
void update(int i, int k)
{
// 向位置为i的数组加k
// 值得注意的是,这里是不会改变原数组的值的
while (i <= n)
{
bit[i] += k;
i += lowbit(i);
}
}
树状数组的区间求和函数
int sum(int i)
{
// 这个函数是求从
// 第一个位置到第 i 个未知的总和
int res = 0;
while (i > 0)
{
res += bit[i];
i -= lowbit(i);
}
return res;
}
下面我们来看看刚才的例题: 洛谷P3374
AC代码
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-07-23 18:58:53
* @Website: https://grimoire.cn
* @Mr.Sen All rights reserved
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int bit[MAXN], a[MAXN], n, m;
int lowbit(int x)
{
return x & (-x);
}
int sum(int i)
{
// 这个函数是求从
// 第一个位置到第 i 个未知的总和
int res = 0;
while (i > 0)
{
res += bit[i];
i -= lowbit(i);
}
return res;
}
void update(int i, int k)
{
// 向位置为i的数组加k
// 值得注意的是,这里是不会改变原数组的值的
while (i <= n)
{
bit[i] += k;
i += lowbit(i);
}
}
int main()
{
ios::sync_with_stdio(false);
// 取消同步,加速cin读入速度
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
// scanf("%d", &a[i]);
update(i, a[i]);
// 读入数据后立即更新bit数组
}
for (int i = 1; i <= m; i++)
{
int type;
cin >> type;
if (type == 1)
{
int x, k;
cin >> x >> k;
update(x, k);
// 将第x个数加上k
}
else
{
int x, y, ans;
cin >> x >> y;
ans = sum(y) - sum(x - 1);
// 计算 x -> y 区间的值大小
// 因为sum(y)里面已经包括了一次x的值,所以是x-1
cout << ans << endl;
}
}
return 0;
}
// 截止2020年7月23日,本代码正常通过该题
接下来我们来看看怎么用树状数组解决逆序对问题
树状数组解逆序对
例题:洛谷P1908
这题是一道求逆序对的模板题,但是在17年左右数据加强后,80%的题解已经无法正常通过该题了,对此在这里对洛谷官方表示诚挚的(cao)感(ni)谢(ma)
如果按照题目没有修改之前,这题可以这样过:
/*
* @Author: Mr.Sen
* @LastEditTime: 2020-07-23 11:06:05
* @Website: https://grimoire.cn
* @Mr.Sen All rights reserved
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int bit[MAXN], n, arr[MAXN];
int lowbit(int x)
{
return x & (-x);
}
void add(int i, int k)
{
while (i <= n)
{
bit[i] += k;
i += lowbit(i);
}
}
int sum(int i)
{
int res = 0;
while (i > 0)
{
res += bit[i];
i -= lowbit(i);
}
return res;
}
void solve() {
int ans = 0;
for (int i = 0; i < n; i++)
{
ans += i - sum(arr[i]);
// 数据加强后,这里出现了问题
// arr[i]已经达到了1e9,这里100亿%会爆re
add(arr[i], 1);
}
cout << ans << endl;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> arr[i];
}
solve();
return 0;
}
// 截止2020年7月23日,本代码无法通过该题!!!
我们看到题目中的数据最大已经达到了1e9,所以我们首先考虑离散化
那么问题来了,什么是离散化呢?
我举一个栗子:
1 4 2 3 7
在这个数组中,我们知道他的逆序对是0 + 0 + 1 + 1 + 0 = 2
,我们尝试对他进行离散化
数组 | 1 | 4 | 2 | 3 | 7 |
---|---|---|---|---|---|
下标 | 1 | 2 | 3 | 4 | 5 |
我们对这个数组进行排序
数组 | 7 | 4 | 3 | 2 | 1 |
---|---|---|---|---|---|
下标 | 5 | 2 | 4 | 3 | 1 |
一直到上面,就是离散化的过程了
Tips:离散化有什么好处?
- 离散化可以在不改变数组逆序对个数的情况下,减少程序所需的空间
比如有如下数据:
5
1 5 6 111111111111 4
如果不进行离散化,那么所需要开的数组是C语言所不能承受的(12位还是11位来着?C语言最大也就7位还是8位)但是进行离散化之后,就只需要开到10就可以了(为什么开到12位请自己翻看上面的无法过题的代码)
然后现在我们来查看一下下标的逆序对0 + 1 + 1 + 2 + 4 = 9
我们取出每一个加数0 1 1 2 4
,可以发现一个规律:
1 - 0 - 1 = 0
2 - 1 - 1 = 0
3 - 1 - 1 = 1
4 - 2 - 1 = 1
5 - 4 - 1 = 0
看一看右边的加和,是不是就是原数组的加数?是不是感觉很神奇?
我们把他抽象成公式,是不是就有i - ans[i] -1
(ans[i]就是大于 i 的值的数的个数)
离散化处理完了,接下来的就是如何计算逆序对的问题了
如何计算逆序对
理论是开两个数组 ans 和 bit
我们还是使用上述的数据1 4 2 3 7
这个地方这么说应该不太严谨,应该是引用的排序后的下标才对,也就是5 2 4 3 1,毕竟是离散化以后的数据,对吧
首先我们读入了数据5,就更新位置5(在位置1加1),然后在数据5对应的位置计算总和并减去1,得到在该位置之前,比该位置大的数据的个数
bit | 1 | ||||
---|---|---|---|---|---|
ans | 0 |
然后我们读入下一个数2,更新位置2,然后在数据2对应的位置计算总和
bit | 1 | 1 | |||
---|---|---|---|---|---|
ans | 0 | 0 |
依次运行下去,有:
bit | 1 | 1 | 1 | ||
---|---|---|---|---|---|
ans | 0 | 1 | 0 |
bit | 1 | 1 | 1 | 1 | |
---|---|---|---|---|---|
ans | 0 | 1 | 1 | 0 |
bit | 1 | 1 | 1 | 1 | 1 |
---|---|---|---|---|---|
ans | 0 | 0 | 1 | 1 | 0 |
在我们的不懈努力下,我们终于求出了ans数组,ans[i] 表示的就是 第 i 个元素能和前面多少个元素组成逆序对(在他前面有多少个值比他大)
那么,新的问题来了,如果我要求有多少个值比他小呢?
哈哈,我们前面已经得出了结论,直接拉过来用就行:i - ans[i] -1
利用这个公式处理一下ans数组,得到的就是比当前位置的值小的个数了
题目:
代码:
#include <bits/stdc++.h>
using namespace std;
long long n;
const long long MAXN = 1e6 + 10;
long long bit[MAXN];
struct node
{
long long val, index;
} a[MAXN];
bool cmp(node a, node b)
{
if (a.val != b.val)
return a.val > b.val;
return a.index > b.index;
// 对数据降序排列
}
long long lowbit(long long x)
{
return x & (-x);
}
void update(long long i, long long k)
{
while (i <= n)
{
bit[i] += k;
i += lowbit(i);
}
}
long long sum(long long i)
{
long long res = 0;
while (i > 0)
{
res += bit[i];
i -= lowbit(i);
}
return res;
}
int main()
{
scanf("%d", &n);
for (long long i = 1; i <= n; ++i)
{
scanf("%d", &a[i].val);
a[i].index = i;
// 对数据进行离散化处理
}
sort(a + 1, a + 1 + n, cmp);
long long ret = 0;
for (long long i = 1; i <= n; ++i)
{
update(a[i].index, 1);
ret += sum(a[i].index) - 1;
// 更新答案数组
// 答案数组储存的是比当前值大的数的数量
}
cout << ret << endl;
return 0;
}
// 截止2020年7月23日正常通过
题目
代码:
#include <bits/stdc++.h>
using namespace std;
long long n;
const long long MAXN = 1e6 + 10;
long long bit[MAXN], ans[MAXN];
struct node
{
long long val, index;
} a[MAXN];
// bool cmp(node a, node b)
// {
// if (a.val != b.val)
// return a.val > b.val;
// return a.index > b.index;
// // 对数据降序排列
// }
bool cmp(node s1, node s2)
{
return s1.val > s2.val;
}
long long lowbit(long long x)
{
return x & (-x);
}
void update(long long i, long long k)
{
while (i <= n)
{
bit[i] += k;
i += lowbit(i);
}
}
long long sum(long long i)
{
long long res = 0;
while (i > 0)
{
res += bit[i];
i -= lowbit(i);
}
return res;
}
int main()
{
scanf("%d", &n);
for (long long i = 1; i <= n; ++i)
{
scanf("%d", &a[i].val);
a[i].index = i;
// 对数据进行离散化处理
}
sort(a + 1, a + 1 + n, cmp);
long long ret = 0;
for (long long i = 1; i <= n; ++i)
{
update(a[i].index, 1);
ans[a[i].index] = sum(a[i].index) - 1;
// 更新答案数组
// 答案数组储存的是比当前值大的数的数量
}
for (long long i = 1; i <= n; ++i)
{
cout << i - ans[i] - 1 << " ";
}
return 0;
}
// 注意!!!本题不知道是直接水过去的还是怎么回事,本题没有添加去重操作,而是修改了比较函数,比较不严谨
// 后续笔者可能会修改这份代码
更新:代码是没有问题的,题目要求的都是不如自己的,所以ans数组应该保存的是除了自己以外,大于等于自己的,所以两份代码的cmp函数不一样,当然你也可以尝试使用去重的方法来处理,这都随你
出处:https://grimoire.cn/algorithm/bit.html
版权:本文《树状数组和逆序对》版权归作者所有
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任