逆序对——浅谈一维树状数组 & 离散化

小灰灰 2022-04-11 02:43 265阅读 0赞

**计算逆序对问题    BZOJ    1266**

--------------------

**目录**

前言

正文

普通做法

归并排序

树状数组

数组离散化

STL+二分离散化

树状数组求逆序对

--------------------

# **前言** #

也许有许多大佬看到这个标题，就会心生嘲笑，毕竟只是一个小小的逆序对嘛。

当然，这只是逆序对而已。

我只是准备抛砖引玉，介绍一下本蒟蒻的一点点对树状数组的理解而已。

如有不适，可以自行跳过

# 正文 #

**题目描述**

设A\[1..n\]是一个包含N个数的数组。如果在i< j的情况下，有A\[i\] >a\[j\]，则(i,j)就称为A中的一个逆序对。 例如，数组（3，1，4，5，2）的“逆序对”有 ＜3,1＞,＜3,2＞,＜4,2＞,＜<5,2＞ 共4个。

**输入**

第1行：1个整数N表示排序元素的个数。(1≤N≤100000)  第2行：N个用空格分开的整数，每个数小于100000。

**输出**

1行：仅一个数，即序列中包含的逆序对的个数

**样例输入**

3
    1 3 2

**样例输出**

## 普通做法 ##

相信各位大神们对逆序对一定不陌生，所以可以直接跳过，当然，如果是跟我一样的同道中人新手们，可以详见：[https://baike.baidu.com/item/%E9%80%86%E5%BA%8F%E5%AF%B9/11035554][https_baike.baidu.com_item_E9_80_86_E5_BA_8F_E5_AF_B9_11035554]。

可以看出，这道题是可以用暴力双层循环求解的。

#include <cstdio>
    int a[20], n, i, j, ans;
    int main (){
        scanf ("%d", &n);
        for (i = 1; i <= n; i++)
            scanf ("%d", &a[i]);
        for (i = 2; i <= n; i++){
            for (j = 1; j < i; j++){
                if (a[j] > a[i])
                    ans ++;
            }
        }
        printf ("%d\n", ans);
        return 0;
    }

可是可以清楚地看出，这个程序的时间复杂度为O(n^2)的，这未免太大了一点吧。

**因此，这里将引入新的知识点——归并排序。**

## 归并排序 ##

在这里，如果运用了归并排序的思想，那么时间复杂度将会变成O(nlogn)，这下时间就蹭蹭蹭的往下掉了。

详见代码：

#include<cstdio>
    #define MAXN 100000
    using namespace std;
    
    int n, a[MAXN + 5], b[MAXN + 5];
    long long inver;
    
    void merge_array (int l, int r, int mid){
        int x = l, y = l, z = mid + 1;
        while (x <= mid && z <= r){//排序，同时在计算逆序对
            if (a[x] <= a[z]){
                b[y++] = a[x++];
            }
            else{
                inver += mid - x + 1;
                b[y++] = a[z++];
            }
        }
        while (x <= mid)//如果说第一个序列还有元素，就直接插入进去
            b[y++] = a[x++];
        while (z <= r)//同上，即为第二个序列
            b[y++] = a[z++];
        for (int i = l; i <= r; ++i)//将有序的序列再赋值回去
            a[i] = b[i];
    }
    
    void mergesort (int l, int r){//归并排序，将数组二分成单个元素，再进行排序
        if (l >= r)
            return ;
        int mid = (l + r) / 2;
        mergesort (l, mid);
        mergesort (mid + 1, r);
        merge_array (l, r, mid);
    }
    
    template <typename T>//读入优化不解释
    void read (T &x){
        x = 0;
        char c = getchar ();
        while (c < '0' || c > '9')
            c = getchar ();
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
    }
    
    int main (){
        read (n);
        for (int i = 1; i <= n; ++i)
            read (a[i]);
        mergesort (1, n);
        printf ("%lld", inver);
    }

在这里的read函数很简单，其实就跟scanf作用一样，唯一的好处就是可以提高读入的速度，相当于骗分神器。

当然，重点还是mergesort和merge\_array了。

mergesort其实就是将一个统一的数组一分为二，最后分成一个，然后再来进行合并。merge\_array就是合并的sao操作，如果说左边的序列小于右边的序列，就可以直接把这个元素放到临时数组中。否则即相当于产生出了逆序对。

因为如果这个数与另一个数成为了逆序对，那么他就将会跟后面的所有数都能成为逆序对（前提是有序的）。

例如：

3 2

这里可以很清楚的看出将会产生一组逆序对。

我们一起来走一遍：

1、

l = 1, r = 2,mid = 1，分成的序列是3和2。

x = 1,z = 2,a\[x\]大于了a\[z\],那么inver将会等于mid - x + 1，即为1。

然后临时数组将会把a\[z\]装进去。

2、

l = 1, r = 3，不满足循环条件，退出。

把a\[x\]放进去。

3、

把临时数组赋值回a数组中。

在这里，归并算法思想的逆序对就做完了，但是，今天我的主题并不是这个，而是——树状数组！

## 树状数组 ##

逆序对同样也可以用树状数组求解。终于扯到正文了，不知道有没有谁是直接跳到这里的呢

不过如果要用树状数组的话，那么就需要用到**离散化**了。

离散化是程序设计中的一个常用的技巧，它能够有效地降低时间复杂度。

如果有些数据特别大，无法作为数组的下标保存对应的属性，可只需要这些数据的相对属性的话，那么就可以直接进行离散化了。

例如：

![20181205100218153.PNG][]

在这里只需要保存排序后的数组下标（即是第几小的）。

**离散化常见的有两种方式：1、数组离散化    2、STL+二分离散化**

### **数组离散化** ###

可以将需要离散化的数组映射成更小的值（支持为下标），以下使用的是对应的顺序（rank）值。

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    struct node{
        int value, id;
        bool operator < (const node &k)const {
            return value < k.value;
        }
    }a[20];
    int b[20], N;
    
    int main (){
        scanf ("%d", &N);
        for (int i = 1; i <= N; i++){
            scanf ("%d", &a[i].value);
            a[i].id = i;
        }
        sort (a + 1, a + 1 + N);
        for (int i = 1; i <= N; i++){
            b[a[i].id] = i;
        }
        for (int i = 1; i <= N; i++){
            printf ("%d\n", b[i]);
        }
    }

输入：

5
    
    1000 65 32 1200 78

输出：

4
    2
    1
    5
    3

### STL+二分离散化 ###

#include <cstdio>
    #include <algorithm>//sort,unique,lower_bound都需要这个函数
    using namespace std;
    
    int N, a[20], b[20], cnt;
    
    int main (){
        scanf ("%d", &N);
        for (int i = 1; i <= N; i++){
            scanf ("%d", &a[i]);
            b[i] = a[i];
        }
        sort (a + 1, a + 1 + N);
        cnt = unique (a + 1, a + 1 + N) - a - 1;//unique的作用就是排序并去重，返回的是无重复数组的最后一个位置的地址加一
        for (int i = 1; i <= N; i++){
            b[i] = lower_bound (a + 1, a + 1 + N, b[i]) - a;//lower_bound是在a数组中找第一个大于等于b[i]的地址
        }
        for (int i = 1; i <= N; i++){
            printf ("%d\n", b[i]);
        }
    }

如果有不了解unique和lower\_bound的朋友可以点这里：[https://www.cnblogs.com/wangkundentisy/p/9033782.html][https_www.cnblogs.com_wangkundentisy_p_9033782.html]

[https://blog.csdn.net/qq\_41603898/article/details/81603327][https_blog.csdn.net_qq_41603898_article_details_81603327]，这里就不再赘述。

### 树状数组求逆序对 ###

有了离散化，就可以来考虑逆序对了。

其实逆序对实际上就是统计当前元素前有几个比他大的元素个数，累加就OK了。

**演示：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 6][]

注意：这里的sum函数就是计算前缀和，而这个前缀和是把自己也算在里头了的。

**参考代码：**

#include <cstdio>
    #include <algorithm>
    #define MAXN 100000
    #define lowbit(a) a & -a
    using namespace std;
     
    struct node{
        int val, id;
        bool operator < (const node &k)const {
            return val < k.val;
        }
    }s[MAXN + 5];
    int n, b[MAXN + 5], c[MAXN + 5];
    int a[MAXN + 5], num[MAXN + 5];
    long long inver;
     
    template <typename T>
    void read (T &x){
        x = 0;
        char c = getchar ();
        while (c < '0' || c > '9')
            c = getchar ();
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
    }
     
    void upDate (int k){//相当于更改k的值，同时更改k后，他的祖先也会改变，所以一直追溯到祖先都要改变
        for (int i = k; i <= n; i += lowbit(i)){
            c[i] += 1;
        }
    }
     
    long long Sum (int k){//计算前缀和
        long long tot = 0;
        for (int i = k; i >= 1; i -= lowbit (i)){
            tot +=c[i];
        }
        return tot;
    }
     
    int main (){
        read (n);
        //这里有两种去重方法，一种是STL，另一种是数组去重
        /*for (int i = 1; i <= n; ++i){
            read (s[i].val);
            s[i].id = i;
        }
        sort (s + 1, s + 1 + n);
        int cnt = 0;
        for (int i = 1; i <= n; ++i){
            if (s[i].val != s[i - 1].val)
                cnt ++;
            b[s[i].id] = cnt;
        }*/
        for (int i = 1; i <= n; ++i){
            read (a[i]);
            num[i] = a[i];
        }
        sort (num + 1, num + 1 + n);
        int cnt = unique (num + 1, num + 1 + n) - num - 1;
        for (int i = 1; i <= n; ++i){
            a[i] = lower_bound (num + 1, num + 1 + cnt, a[i]) - num;
        }
        for (int i = 1; i <= n; ++i){
            upDate (a[i]);
            inver += i - Sum (a[i]);
        }
        printf ("%lld",inver);
    }

[https_baike.baidu.com_item_E9_80_86_E5_BA_8F_E5_AF_B9_11035554]: https://baike.baidu.com/item/%E9%80%86%E5%BA%8F%E5%AF%B9/11035554
[20181205100218153.PNG]: /images/20220411/846cc4d7657a404d8022820ae7f3e114.png
[https_www.cnblogs.com_wangkundentisy_p_9033782.html]: https://www.cnblogs.com/wangkundentisy/p/9033782.html
[https_blog.csdn.net_qq_41603898_article_details_81603327]: https://blog.csdn.net/qq_41603898/article/details/81603327
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220411/42e89175f41b4a0fa4f86713e3c774fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220411/b5781d88f6904acf9accd586b32d37e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220411/7456f2a1638c4a71bc8ae6720a330c24.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 3]: /images/20220411/9e47026d437244708691afcca211a091.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 4]: /images/20220411/969e7846912d449b8847b69a3b5507cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 5]: /images/20220411/2327bbed3d5b45058207a243e8dfee0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 6]: /images/20220411/4592c71c1718465e874d58b931eb2b27.png