MENU

树状数组和逆序对

July 23, 2020 • Read: 72 • 算法

首先在这里提一下,逆序对一般有两种解法,一种是归并排序,另一种就是本篇博客要讲的树状数组

什么是逆序对呢?

百度百科是这样解释的:

对于一个包含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这个数组中,逆序对个数为0
5 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,我们尝试对他进行离散化

数组14237
下标12345

我们对这个数组进行排序

数组74321
下标52431

一直到上面,就是离散化的过程了

Tips:离散化有什么好处?

  1. 离散化可以在不改变数组逆序对个数的情况下,减少程序所需的空间

比如有如下数据:

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 11
ans 0 10
bit 1111
ans 0110
bit11111
ans00110

在我们的不懈努力下,我们终于求出了ans数组,ans[i] 表示的就是 第 i 个元素能和前面多少个元素组成逆序对(在他前面有多少个值比他大)

那么,新的问题来了,如果我要求有多少个值比他小呢?

哈哈,我们前面已经得出了结论,直接拉过来用就行:i - ans[i] -1

利用这个公式处理一下ans数组,得到的就是比当前位置的值小的个数了

题目:

洛谷P1908

代码:

#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日正常通过

题目

洛谷P1428

代码:

#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函数不一样,当然你也可以尝试使用去重的方法来处理,这都随你

Last Modified: July 27, 2020
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment

5 Comments
  1. 听说这里在测试邮箱,我也来试试

    1. @Mr.Sen你看看能收到么

  2. 大佬好厉害

    1. @城北陈还行吧,我测试一下邮箱

    2. @城北陈好像没发过去。我再测一下