MENU

树状数组和逆序对

July 23, 2020 • 算法

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

什么是逆序对呢？

百度百科是这样解释的：

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

作者：NorthCity1984
出处：https://grimoire.cn/algorithm/bit.html
版权：本文《树状数组和逆序对》版权归作者所有
转载：欢迎转载，但未经作者同意，必须保留此段声明；必须在文章中给出原文连接；否则必究法律责任

树状数组逆序对
Last Modified: July 27, 2020
取消回复
Leave a Comment