线性区间操作

区间操作分类

  • 修改区间值，询问元素值。（差分数组）
  • 修改元素值，访问区间值。（树状数组和线段树）
  • 修改元素值，查询最大最小值。（线段树）

1 数组中的逆序对

问题描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

问题分析

策略选择

  • 数据结构：线性数组、树状数组
  • 算法思想：用树状数组解决逆序数问题，也是一个经典的做法。树状数组是一种实现了高效查询「前缀和」与「单点更新」操作的数据结构，

算法设计

具体的做法是：

  • 先离散化，将所有的数组元素映射到 0、1、2、3… ，这是为了节约树状数组的空间；

  • 从后向前扫描，边统计边往树状数组里面添加元素，这个过程是「动态的」，需要动手计算才能明白思想。

  • 我们可以看出它第i−1 位的前缀和表示「有多少个数比 i 小」。那么我们可以从后往前遍历序列a，记当前遍历到的元素为 $a_i$，我们把$a_i$对应的桶的值自增 1，把 i - 1位置的前缀和加入到答案中算贡献。

  • 我们显然可以用数组来实现这个桶，可问题是如果$a_i$中有很大的元素，比如 10^9我们就要开一个大小为 10^9的桶，内存中是存不下的。这个桶数组中很多位置是0，有效位置是稀疏的，我们要想一个办法让有效的位置全聚集到一起，减少无效位置的出现，这个时候我们就需要用到一个方法——离散化。

  • 离散化一个序列的前提是我们只关心这个序列里面元素的相对大小，而不关心绝对大小（即只关心元素在序列中的排名）；离散化的目的是让原来分布零散的值聚集到一起，减少空间浪费。那么如何获得元素排名呢，我们可以对原序列排序后去重，对于每一个$a_i$通过二分查找的方式计算排名作为离散化之后的值。当然这里也可以不去重，不影响排名。

算法分析

  • 时间复杂度为 O(n \log n)
  • 空间复杂度为 O(n)O(n)

算法实现

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
40
41
42
43
44
45
46
47
48
49
class BIT {
private:
    vector<int> tree;
    int n;

public:
    BIT(int _n): n(_n), tree(_n + 1) {}

    static int lowbit(int x) {
        return x & (-x);
    }

    int query(int x) {
        int ret = 0;
        while (x) {
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }

    void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }
};

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        int n = nums.size();
        vector<int> tmp = nums;
        // 离散化
        sort(tmp.begin(), tmp.end());
        for (int& num: nums) {
            num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;
        }
        // 树状数组统计逆序对
        BIT bit(n);
        int ans = 0;
        for (int i = n - 1; i >= 0; --i) {
            ans += bit.query(nums[i] - 1);
            bit.update(nums[i]);
        }
        return ans;
    }
};

2 区间覆盖问题

问题描述

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。

如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。

已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数x 被覆盖了。

 

示例 1：

1
2
3
4
5
6
输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出：true
解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。

问题分析

  • 区间覆盖问题

策略选择

  • 数据结构：数组
  • 算法选择：线性区间操作

算法设计

  • 遍历 \textit{ranges}ranges 中的所有区间 [l, r][l,r]，将区间内每个整数的 \textit{cnt}cnt 值加上 11。遍历结束后，检查 [\textit{left},\textit{right}][left,right] 内的每个整数的 \textit{cnt}cnt 值是否均大于 00，是则返回 \texttt{true}true，否则返回 \texttt{false}false。
  • 在维护完差分数组 \textit{diff}diff 后，我们遍历 \textit{diff}diff 求前缀和得出覆盖每个整数的区间数量。下标 ii 对应的被覆盖区间数量即为初始数量 00 加上 [1, i][1,i] 闭区间的变化量之和。在计算被覆盖区间数量的同时，我们可以一并判断 [\textit{left}, \textit{right}][left,right] 闭区间内的所有整数是否都被覆盖。

算法分析

  • 时间复杂度：O(n + l)
  • 空间复杂度：O(l)

算法实现

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
class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        // 一种差分数组的方法。
        vector<int> vec(right-left+2,0);
        for(auto k:ranges){
            if(k[0]>right || k[1]<left)continue;

            if(k[0]<left){
                vec[left-left]++;
            }
            else{
                vec[k[0]-left]++;
            }

            if(k[1]>right){
                vec[right-left+1]--;
            }
            else{
                vec[k[1]-left+1]--;
            }
        }
        
        int m = 0;
        for(int a =left;a<=right;a++){
            m+=vec[a-left];
            if(m<=0){
                return false;
            }
        }
        return true;

    }
};