算法数据结构

离线分治：基于时间 (CDQ分治)

字数统计: 2.8k字   |   阅读时长: 11分
,

摘要: 基于时间的离线分治，逆序对个数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

很多数据结构的问题可以抽象为“维护一系列数据，并对一系列操作一次做出响应”，这些操作可以分为两种：

  1. 查询型操作：统计数据信息。
  2. 修改型操作：更新数据状态。

执行各项操作的顺序是一个要点，我们称其为时间轴。

根据查询响应时间的不同，把解决以上问题的算法分为在线和离线：

  • 在线算法：依次获得每项操作，并在每次查询时立即响应正确的结果，响应查询之后再执行下一个操作。
  • 离线算法：预先知道整个操作序列，经过一系列计算，再批量响应所有查询的结果。

根据两种操作在时间轴上的分布不同，以上数据结构问题可以分为动态和静态：

  • 静态问题：只包含查询操作，或者所有查询操作都在所有修改性操作之后。
  • 动态问题：除了静态问题之外的情况。

基于时间的离线分治算法是一种把动态问题划分为若干个静态子问题，并使用离线算法求解的思路。

本文我们首先介绍基于时间的离线分治算法的原理，这部分主要参考《算法竞赛进阶指南》，并且以力扣 493. 翻转对 为例来实现。

基于时间的离线分治 (CDQ)

对于操作序列中的每个查询，计算其结果等价于计算初始数据以及之前的所有修改对该查询造成的影响。

设共有 $M$ 个操作，对于 $\forall l, r \in [1, M], l \leq r$，定义 $solve(l, r)$ 如下：

对 $\forall k\in [l,r]$ 若第 $k$ 项操作是查询，则计算第 $l, l+1, \cdots, k-1$ 项操作中的修改对它造成的影响，计算方法如下：

  1. 设 $mid = (l + r) / 2$，递归计算 $solve(l, mid)$
  2. 递归计算 $solve(mid + 1, r)$
  3. 计算第 $l, l+1, \cdots, mid$ 项操作中所有“修改”对第 $mid+1,mid+2,\cdots,r$ 项操作中所有查询造成的影响。

下面根据 $k$ 与 $mid$ 的关系来分析，看看以上计算方式为什么就计算了第 $l, l+1, \cdots, k-1$ 项操作中的修改对第 $k$ 项查询造成的影响：

  • 若 $k \leq mid$，则根据定义，$solve(l, mid)$ 已经计算了第 $l, l+1, \cdots, k-1$ 项操作对第 $k$ 项查询的影响。
  • 若 $k > mid$，$solve(l, mid)$ 计算了第 $l, l+1, \cdots, mid$ 项操作中的修改对第 $k$ 项的影响，另一方面 $solve(mid + 1, r)$ 计算了第 $mid + 1, mid + 2, \cdots k - 1$ 项修改对第 $k$ 项查询的影响。

因此 $solve(l, r)$ 计算了 $\forall k \in [l, r]$ 且第 $k$ 项为查询时，第 $l, l+1,\cdots,k-1$ 项操作对第 $k$ 项查询的影响。

可以看出 $solve(l, r)$ 是一个分治的过程，在不考虑初始数据的情况下，$solve(1, M)$ 为原始问题：

  • 分解：当 $l < r$ 时，$mid = (l + r) / 2$，递归地求解 $solve(l, mid), solve(mid + 1, r)$
  • 解决：当 $l=r$ 时，$solve(l, r)$ 只包含一项操作，可以作为递归边界。
  • 合并：计算 $[l, mid]$ 这些操作中的修改对 $[mid+1, r]$ 这些操作中的查询造成的影响。

按照前面的问题定义，以上分治算法的合并过程是静态问题。如下图所示：

该分治算法把一个动态问题划分为 $O(M\log M)$ 个静态问题，原始问题的每个查询的结果由 $O(\log M)$ 个静态问题的结果构成。

如果能在 $O(f(r-l))$ 的时间复杂度内完成 $solve(l, r)$ 合并过程，也就是时间复杂度仅与 $r - l$ 有关，则整个分治算法解决动态问题的时间复杂度仅比解决同类静态问题的时间复杂度多 $O(\log M)$。

这种离线分治算法是基于时间顺序对操作序列进行分治的，也称为 CDQ 分治。

CDQ 分治能够简化问题的关键在于能够对操作序列按照时间分治，让转化后的静态问题不必考虑修改和查询的时间顺序，使其按照其他维度（例如横坐标）排序称为可能。

设计 CDQ 分治算法的要点

在实际问题中，思考如何用 CDQ 分治解决问题，会依次遇到三个难点：

  1. 如何把问题中要考察的元素，以及针对这些元素求的答案统一成操作序列，记其长度为 $M$，执行完操作序列可以得到目标结果。
  2. 在这组操作序列上考虑分治，$solve(l, r)$ 如何定义，使得 $solve(1, M)$ 就是所求答案。
  3. 在 $solve(l, r)$ 的定义下，第 $l, l+1, \cdots, mid$ 项操作中修改的部分对第 $mid + 1, \cdots, r$ 项操作中的查询如何在 $O(f(r - l))$ 之内求出, 即时间复杂度仅与 $r - l$ 有关。

下面我们按照以上框架分析一下逆序对问题，如何解决以上三个问题，设计出 CDQ 分治算法。

逆序对问题

在文章 分治-逆序对个数 中我们通过分治法解决了数组的逆序对个数问题。分治法的框架如下：

1
2
3
4
5
6
7
8
分解: 将原序列 x=a[l..r] 分为 x1=a[l, (l+r)/2], x2=a[(l+r)/2 + 1, r] 两部分

解决: 如果原序列 x 的长度为 1，则直接返回此序列和 0 即可

合并: 左边部分的逆序对个数为 n1, 排序后的序列 y1
      右边部分的逆序对个数为 n2, 排序后的序列 y2
      对 y1, y2 做 2 路归并，归并后的序列为 y，并顺便统计逆序对个数 n3
      返回 y 和 n1 + n2 + n3

下面我们在 CDQ 分治的框架下重新分析这个问题。假设数据长度为 $N$，我们要求整个数组的逆序对个数 $F$。

记 $a[j]$ 对答案 $F$ 的贡献为在 $1 \leq i < j$ 的范围内，$(a[i], a[j])$ 构成多少对逆序对，记其为 $f[j]$，于是：

构造操作序列

记 $B$ 为一个集合，初始时为空集，构造以下两种操作，维护 $B$ 集合：

  • 修改：update(j)，向 $B$ 新增 $a[j]$。记为 $U(j)$。
  • 查询：queray(j)，查询 $b \in B$，$(b, a[j])$ 形成的逆序对个数。记为 $Q(j)$。

基于以上两种操作组装长度为 $M$ 的操作序列，需要注意构造的操作序列要满足 $solve(1, M)$ 正好是我们想要求的结果，也就是 $f[1..N]$。这样在 $solve(1, M)$ 计算完之后，$sum(f)$ 即可得到结果。

构造的操作序列如下，长度为 $2N$：

该操作序列执行完一次，可以得到所求结果。

下面我们在这个操作序列上分治。

CDQ 分治

$solve(l, r)$ 定义如下：对 $\forall k\in [l,r]$ 若第 $k$ 项操作是查询 $Q(j)$，则计算第 $l, l+1, \cdots, k-1$ 项操作中的修改对它造成的影响。也就是操作序列 $[l, k-1]$ 中插入到 $B$ 的元素中与 $a[j]$ 形成逆序对的个数。

前两步还是常规的：$mid = (l + r) / 2$，$solve(l, mid)$，$solve(mid + 1, r)$。

关键是第三步，第 $l, l+1, \cdots, mid$ 项操作中所有“修改”对第 $mid+1,mid+2,\cdots,r$ 项操作中所有查询造成的影响如何求出。

枚举操作序列 $l, l+1, \cdots, mid$ 的所有插入，再枚举操作序列 $mid+1,mid+2,\cdots,r$ 的所有查询，依次计算是一种方法，这样时间复杂度是 $O((r - l)^{2})$。

但如果操作序列 $l, l+1, \cdots, mid$ 和操作序列 $mid+1, \cdots, r$ 均有序，则通过双串单向双指针可以在 $O(r-l)$ 算出来。

要保持两边有序，这正是归并排序的过程。于是我们得到了归并排序求逆序对个数的算法。

题目：493. 翻转对

给定一个数组 nums ，如果 $i < j$ 且 $nums[i] > 2 * nums[j]$ 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

提示：

1
2
给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

示例 1:

输入: [1,3,2,3,1]
输出: 2
示例 2:

输入: [2,4,3,5,1]
输出: 3

算法：基于时间的离线分治 (CDQ)

前面我们详细分析了基于时间的离线分治(CDQ)的算法，并且实现了在并排序过程中求出逆序对。

这里简要CDQ分治的基本思想：

<1> 分：递归处理左边区间[left, mid]和右边区间[mid + 1, right]的问题。

<2> 治：合并两个子问题，同时考虑到[left, mid]内的修改对[mid + 1, right]内的查询产生的影响。用左边的子问题帮助解决右边的子问题。

CDQ分治和普通分治不同的地方在于，普通分治在合并两个子问题的过程中，[left, mid] 内的问题不会对 [mid + 1,right] 内的问题产生影响。

这个算法的基本框架就是归并排序，在子数组已经排好序，在进入归并阶段之前，先统计想要的信息，两个子数组已经有序对统计有很大帮助。

归并阶段就是这个题实现的过程 88. 合并两个有序数组。

代码(c++)

在有序段的归并阶段，归并之前统计需要的信息，即 merge 函数注释中的的统计过程。除此之外与归并排序一模一样，把统计过程的那段代码去掉就是原封不动的归并排序。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        if(n == 1) return 0;
        return _mergesort(nums, 0, n - 1);
    }

private:
    using ll = long long;

    int _mergesort(vector<int>& nums, int left, int right)
    {
        int mid = left + (righ.t - left) / 2;
        int res = 0;
        if(left == right) return 0;
        res += _mergesort(nums, left, mid);
        res += _mergesort(nums, mid + 1, right);
        res += _merge(nums, left, mid + 1, right);
        return res;
    }

    int _merge(vector<int>& nums, int left, int mid, int right)
    {
        // 统计过程
        int i = left, j = mid;
        int res = 0;
        while(i < mid && j <= right)
        {
            if((ll)nums[i] > 2ll * nums[j])
            {
                res += mid - i;
                ++j;
            }
            else
                ++i;
        }

        // 归并过程
        i = left, j = mid;
        int k = 0;
        vector<int> tmp(right - left + 1, 0);
        while(i < mid && j <= right)
        {
            if(nums[i] > nums[j])
            {
                tmp[k] = nums[j];
                ++k;
                ++j;
            }
            else
            {
                tmp[k] = nums[i];
                ++k;
                ++i;
            }
        }
        while(i < mid) tmp[k++] = nums[i++];
        while(j <= right) tmp[k++] = nums[j++];
        for(i = left, k = 0; i <= right; ++i, ++k)
            nums[i] = tmp[k];
        return res;
    }
};
Share