基于逆序对计数的合并排序（Merge Sort with Inversion Count）的进阶：高效统计多维数组的“局部逆序”与动态更新

字数 4955 2025-12-11 00:47:54

基于逆序对计数的合并排序（Merge Sort with Inversion Count）的进阶：高效统计多维数组的“局部逆序”与动态更新

题目描述

我们通常用“逆序对”来描述数组的无序程度。假设我们有一个长度为 n 的数组 A。传统定义下，一个逆序对是指一对索引 (i, j)，满足 i < j 且 A[i] > A[j]。这个问题我们已通过归并排序高效解决。

现在，我们引入一个更复杂的概念：“k-局部逆序”。定义如下：对于一对索引 (i, j) 满足 1 ≤ i < j ≤ n，如果满足 A[i] > A[j] 且 j - i ≤ k，则称 (i, j) 为一个“k-局部逆序”，其中 k 是一个给定的正整数（1 ≤ k < n）。换句话说，我们只关心距离不超过 k 的元素之间构成的逆序对。

进阶任务：

静态统计：给定一个数组 A 和参数 k，设计一个算法，高效地计算出数组中“k-局部逆序”的总数量。
动态查询（可选进阶）：如果我们允许对数组进行单点更新操作（如修改某个位置的值），并且需要在此之后能够快速查询当前的“k-局部逆序”总数，如何设计一个数据结构来支持高效的点更新和总数查询？

本题将聚焦于第一个任务（静态统计）的求解。我们将探讨如何基于归并排序的思想，设计一个时间复杂度优于 O(n²) 的算法。

解题过程详解

第一步：理解问题与暴力法

首先，我们明确问题的输入和输出：

输入：一个包含 n 个元素的数组 nums，一个整数 k (1 ≤ k < n)。
输出：数组中“k-局部逆序”的总数。

最直观的方法是暴力枚举所有可能的索引对 (i, j)，检查是否满足 i < j，j - i <= k 且 nums[i] > nums[j]。伪代码如下：

count = 0
for i from 0 to n-2:
    for j from i+1 to min(i+k, n-1): // 确保距离不超过k
        if nums[i] > nums[j]:
            count += 1
return count

时间复杂度：外层循环 O(n)，内层循环最多 O(k)，因此总时间复杂度为 O(n * k)。在最坏情况下 k 接近 n，算法退化为 O(n²)。我们的目标就是优化这个时间复杂度。

第二步：思考与归并排序的关联

经典逆序对统计的核心算法是基于归并排序的分治策略。在归并排序的“合并”步骤中，当我们需要将两个已排序的子数组合并时，可以高效地统计出跨越这两个子数组的逆序对的数量。

具体来说，假设我们有两个已排序的子数组 left 和 right，正在合并。指针 i 指向 left，j 指向 right。如果 left[i] > right[j]，那么由于 left 是已排序的，left 中从 i 开始到末尾的所有元素都会大于 right[j]。这就意味着，right[j] 与 left 中从 i 向后的所有元素都构成了逆序对。我们可以快速累加这个数量。

这个经典算法能统计所有逆序对。现在，我们多了“j - i ≤ k”这个距离限制。这里的 i 和 j 是原始数组中的索引，但在合并时，left 和 right 中的元素是原数组的一段连续子序列。所以，在合并过程中，我们不仅仅要知道 left[i] 大于 right[j]，还需要知道它们在原始数组中的位置差是否 ≤ k。

第三步：关键修改——在合并步骤中引入距离检查

我们需要修改归并排序的合并步骤，使其在统计逆序对时，额外检查原始索引的距离约束。

设计思路：

携带原始索引：在进行归并排序时，我们不能只比较元素的值。我们需要知道每个元素在原数组中的原始位置（索引）。因此，我们可以将元素和它的索引打包在一起，作为一个(value, index)对进行排序。
在合并步骤中统计：当我们比较 left[p] 和 right[q] 时（p, q 分别是左右子数组的指针）：
- 如果 left[p].value > right[q].value，我们需要计算有多少对满足距离约束。
- 由于 left 数组是已排序的，left 中从 p 到末尾的所有元素的 value 都大于 right[q].value。但是，我们还需要检查这些元素的原始索引与 right[q] 的原始索引之差是否 ≤ k。
- 我们不能简单地将整个 left 从 p 到末尾的元素数量都计入。我们需要遍历 left 数组中从 p 开始的部分，只累加那些与 right[q] 的原始索引距离不超过 k 的元素。
如何高效地遍历和检查？因为 left 数组在值上是递增的，但其原始索引是无序的。不过，有一个重要的观察：在合并时，left 和 right 分别来自原数组的左右两半。假设当前合并的区间在原数组中的范围是 [start, end]，mid = (start+end)/2，则 left 包含索引 [start, mid]，right 包含索引 [mid+1, end]。
- 对于 right 中的一个元素 right[q]，其原始索引记为 idx_j。
- 我们需要在 left 中找到所有满足以下条件的元素：
  1. 它们的值大于 right[q].value（由于 left 已按值排序，这部分是连续的，从指针 p 开始）。
  2. 它们的原始索引 idx_i 满足 idx_j - idx_i ≤ k（即 idx_i ≥ idx_j - k）。
- 由于 left 中元素的原始索引范围是 [start, mid]，条件 idx_i ≥ idx_j - k 定义了一个下界。我们需要在 left 的候选部分（从 p 到末尾）中，找到第一个原始索引满足 idx_i ≥ idx_j - k 的元素。从该元素开始，直到 left 末尾的所有元素，都同时满足“值更大”和“距离够近”两个条件。

第四步：算法步骤与实现细节

我们可以通过一个“双指针”或“扫描”技巧在合并过程中高效实现上述检查。

下面是详细的算法步骤：

数据准备：创建一个数组 pairs，其中每个元素是 (nums[i], i)，即值和原始索引的配对。
递归分治：定义函数 mergeSortAndCount(arr, left, right)，对数组 arr 在区间 [left, right] 上进行排序，并返回该区间内的“k-局部逆序”数量。
递归基：如果 left >= right，返回 0。
计算中点：mid = (left + right) // 2。
递归调用：
- inv_count_left = mergeSortAndCount(arr, left, mid)
- inv_count_right = mergeSortAndCount(arr, mid+1, right)
- inv_count_cross = 0 // 初始化跨越左右的逆序对数量
统计跨越左右的“k-局部逆序”：
- 在合并排序之前，我们先进行统计。此时 arr[left...mid] 和 arr[mid+1...right] 分别已按值排好序。
- 我们使用两个指针 p 和 q。p 遍历 left 数组（索引范围 [left, mid]），q 遍历 right 数组（索引范围 [mid+1, right]）。
- 对于每个 q（指向 right 中的元素）：
  - 移动 p 指针，使其指向 left 中第一个值大于 arr[q].value 的元素。由于 left 已按值排序，p 之前的元素都 <= arr[q].value。
  - 现在，left 中从 p 到 mid 的所有元素，在值上都大于 arr[q].value。但它们不一定都满足距离约束。
  - 我们需要在 left[p...mid] 这个区间内，计算有多少个元素的原始索引 arr[i].index 满足：arr[q].index - arr[i].index <= k。
  - 由于 p 是固定的（对于当前的 q），而 arr[q].index 是固定的，条件等价于 arr[i].index >= arr[q].index - k。
  - 我们可以从 p 开始，向右线性扫描 left 数组，直到遇到第一个不满足 arr[i].index >= arr[q].index - k 的元素为止。扫描过的元素数量就是当前 q 元素与左半部分元素构成的、满足条件的逆序对数量。
  - 优化扫描：注意到当我们处理下一个 q'（q' > q）时，arr[q'].index 可能更大，所以 arr[q'].index - k 也可能更大，这意味着对 left 中元素索引的下界要求可能更严格。因此，我们可以在扫描 left 时，在 p 指针的基础上，使用另一个指针 r 来标记当前满足索引条件的最左边界。随着 q 的增加，r 可以单调向右移动，避免重复扫描。这样，对每个 q 的检查时间复杂度是分摊 O(1) 的。
完成合并排序：统计完逆序对后，我们使用标准的归并排序合并步骤，将 arr[left...mid] 和 arr[mid+1...right] 合并成一个按值有序的序列，并写回原数组。
返回总数：返回 inv_count_left + inv_count_right + inv_count_cross。

第五步：复杂度分析

时间复杂度：主流程仍然是归并排序的框架，为 O(n log n)。关键的修改在于合并步骤中的统计部分。我们通过双指针（p 和 r）技巧，确保了对于每个 q，检查满足条件的 left 中元素数量的操作是分摊 O(1) 的。因此，整个算法的时间复杂度依然是 O(n log n)，优于 O(n*k) 的暴力法，尤其当 k 较大时优势明显。
空间复杂度：我们需要一个与原数组同样大小的辅助数组来进行归并操作，因此空间复杂度为 O(n)。存储 (value, index) 对也在此空间内。

第六步：核心步骤示例

假设数组为 [5, 2, 6, 1]，k=2。原始索引为 0,1,2,3。打包后为 [(5,0), (2,1), (6,2), (1,3)]。

在递归到底层合并时，考虑一次跨越左右的合并：

左半部分 left = [(2,1), (5,0)] (已按值排序)
右半部分 right = [(1,3), (6,2)] (已按值排序)
我们需要统计满足 j-i <=2 且值逆序的对。

处理右半部分的第一个元素 (1,3)：

在 left 中找到值大于1的元素起始位置 p，即第一个元素 (2,1)。
检查 left 中从 (2,1) 开始的元素，原始索引是否满足 3 - index <= 2，即 index >= 1。
- (2,1) 的索引是1，满足条件。计数+1。
- (5,0) 的索引是0，不满足条件（3-0=3>2）。停止扫描。
  处理右半部分的第二个元素 (6,2)：
在 left 中找到值大于6的元素起始位置 p。left 中所有值都不大于6，所以没有满足值条件的元素。计数为0。

在此次合并中，跨越左右的、满足k-局部条件的逆序对数量为1（即 (5,0) 和 (1,3) 不满足距离条件，(2,1) 和 (1,3) 满足条件）。

递归向上合并，最终可得到总数。

总结：
本算法巧妙地结合了归并排序的分治特性和“k-局部”这一距离约束。通过携带原始索引，并在合并过程中利用已排序性质和双指针技巧进行高效的范围检查，我们在 O(n log n) 的时间复杂度内解决了问题。这是经典逆序对计数问题的一个非平凡但非常优美的扩展。

基于逆序对计数的合并排序（Merge Sort with Inversion Count）的进阶：高效统计多维数组的“局部逆序”与动态更新题目描述我们通常用“逆序对”来描述数组的无序程度。假设我们有一个长度为 n 的数组 A。传统定义下，一个逆序对是指一对索引 (i, j)，满足 i < j 且 A[ i] > A[ j ]。这个问题我们已通过归并排序高效解决。现在，我们引入一个更复杂的概念：“k-局部逆序”。定义如下：对于一对索引 (i, j) 满足 1 ≤ i < j ≤ n，如果满足 A[ i] > A[ j] 且 j - i ≤ k，则称 (i, j) 为一个“k-局部逆序”，其中 k 是一个给定的正整数（1 ≤ k < n）。换句话说，我们只关心距离不超过 k 的元素之间构成的逆序对。进阶任务：静态统计：给定一个数组 A 和参数 k，设计一个算法，高效地计算出数组中“k-局部逆序”的总数量。动态查询（可选进阶）：如果我们允许对数组进行单点更新操作（如修改某个位置的值），并且需要在此之后能够快速查询当前的“k-局部逆序”总数，如何设计一个数据结构来支持高效的点更新和总数查询？本题将聚焦于第一个任务（静态统计）的求解。我们将探讨如何基于归并排序的思想，设计一个时间复杂度优于 O(n²) 的算法。解题过程详解第一步：理解问题与暴力法首先，我们明确问题的输入和输出：输入：一个包含 n 个元素的数组 nums ，一个整数 k (1 ≤ k < n)。输出：数组中“k-局部逆序”的总数。最直观的方法是暴力枚举所有可能的索引对 (i, j)，检查是否满足 i < j ， j - i <= k 且 nums[i] > nums[j] 。伪代码如下：时间复杂度：外层循环 O(n)，内层循环最多 O(k)，因此总时间复杂度为 O(n * k)。在最坏情况下 k 接近 n，算法退化为 O(n²)。我们的目标就是优化这个时间复杂度。第二步：思考与归并排序的关联经典逆序对统计的核心算法是基于归并排序的分治策略。在归并排序的“合并”步骤中，当我们需要将两个已排序的子数组合并时，可以高效地统计出跨越这两个子数组的逆序对的数量。具体来说，假设我们有两个已排序的子数组 left 和 right ，正在合并。指针 i 指向 left ， j 指向 right 。如果 left[i] > right[j] ，那么由于 left 是已排序的， left 中从 i 开始到末尾的所有元素都会大于 right[j] 。这就意味着， right[j] 与 left 中从 i 向后的所有元素都构成了逆序对。我们可以快速累加这个数量。这个经典算法能统计所有逆序对。现在，我们多了“j - i ≤ k”这个距离限制。这里的 i 和 j 是原始数组中的索引，但在合并时， left 和 right 中的元素是原数组的一段连续子序列。所以，在合并过程中，我们不仅仅要知道 left[i] 大于 right[j] ，还需要知道它们在原始数组中的位置差是否 ≤ k。第三步：关键修改——在合并步骤中引入距离检查我们需要修改归并排序的合并步骤，使其在统计逆序对时，额外检查原始索引的距离约束。设计思路：携带原始索引：在进行归并排序时，我们不能只比较元素的值。我们需要知道每个元素在原数组中的原始位置（索引）。因此，我们可以将元素和它的索引打包在一起，作为一个 (value, index) 对进行排序。在合并步骤中统计：当我们比较 left[p] 和 right[q] 时（p, q 分别是左右子数组的指针）：如果 left[p].value > right[q].value ，我们需要计算有多少对满足距离约束。由于 left 数组是已排序的， left 中从 p 到末尾的所有元素的 value 都大于 right[q].value 。但是，我们还需要检查这些元素的原始索引与 right[q] 的原始索引之差是否 ≤ k。我们不能简单地将整个 left 从 p 到末尾的元素数量都计入。我们需要遍历 left 数组中从 p 开始的部分，只累加那些与 right[q] 的原始索引距离不超过 k 的元素。如何高效地遍历和检查？因为 left 数组在值上是递增的，但其原始索引是无序的。不过，有一个重要的观察：在合并时， left 和 right 分别来自原数组的左右两半。假设当前合并的区间在原数组中的范围是 [start, end] ， mid = (start+end)/2 ，则 left 包含索引 [start, mid] ， right 包含索引 [mid+1, end] 。对于 right 中的一个元素 right[q] ，其原始索引记为 idx_j 。我们需要在 left 中找到所有满足以下条件的元素：它们的值大于 right[q].value （由于 left 已按值排序，这部分是连续的，从指针 p 开始）。它们的原始索引 idx_i 满足 idx_j - idx_i ≤ k （即 idx_i ≥ idx_j - k ）。由于 left 中元素的原始索引范围是 [start, mid] ，条件 idx_i ≥ idx_j - k 定义了一个下界。我们需要在 left 的候选部分（从 p 到末尾）中，找到第一个原始索引满足 idx_i ≥ idx_j - k 的元素。从该元素开始，直到 left 末尾的所有元素，都同时满足“值更大”和“距离够近”两个条件。第四步：算法步骤与实现细节我们可以通过一个“双指针”或“扫描”技巧在合并过程中高效实现上述检查。下面是详细的算法步骤：数据准备：创建一个数组 pairs ，其中每个元素是 (nums[i], i) ，即值和原始索引的配对。递归分治：定义函数 mergeSortAndCount(arr, left, right) ，对数组 arr 在区间 [left, right] 上进行排序，并返回该区间内的“k-局部逆序”数量。递归基：如果 left >= right ，返回 0。计算中点： mid = (left + right) // 2 。递归调用： inv_count_left = mergeSortAndCount(arr, left, mid) inv_count_right = mergeSortAndCount(arr, mid+1, right) inv_count_cross = 0 // 初始化跨越左右的逆序对数量统计跨越左右的“k-局部逆序” ：在合并排序之前，我们先进行统计。此时 arr[left...mid] 和 arr[mid+1...right] 分别已按值排好序。我们使用两个指针 p 和 q 。 p 遍历 left 数组（索引范围 [left, mid] ）， q 遍历 right 数组（索引范围 [mid+1, right] ）。对于每个 q （指向 right 中的元素）：移动 p 指针，使其指向 left 中第一个值大于 arr[q].value 的元素。由于 left 已按值排序， p 之前的元素都 <= arr[q].value 。现在， left 中从 p 到 mid 的所有元素，在值上都大于 arr[q].value 。但它们不一定都满足距离约束。我们需要在 left[p...mid] 这个区间内，计算有多少个元素的原始索引 arr[i].index 满足： arr[q].index - arr[i].index <= k 。由于 p 是固定的（对于当前的 q ），而 arr[q].index 是固定的，条件等价于 arr[i].index >= arr[q].index - k 。我们可以从 p 开始，向右线性扫描 left 数组，直到遇到第一个不满足 arr[i].index >= arr[q].index - k 的元素为止。扫描过的元素数量就是当前 q 元素与左半部分元素构成的、满足条件的逆序对数量。优化扫描：注意到当我们处理下一个 q' （ q' > q ）时， arr[q'].index 可能更大，所以 arr[q'].index - k 也可能更大，这意味着对 left 中元素索引的下界要求可能更严格。因此，我们可以在扫描 left 时，在 p 指针的基础上，使用另一个指针 r 来标记当前满足索引条件的最左边界。随着 q 的增加， r 可以单调向右移动，避免重复扫描。这样，对每个 q 的检查时间复杂度是分摊 O(1) 的。完成合并排序：统计完逆序对后，我们使用标准的归并排序合并步骤，将 arr[left...mid] 和 arr[mid+1...right] 合并成一个按值有序的序列，并写回原数组。返回总数：返回 inv_count_left + inv_count_right + inv_count_cross 。第五步：复杂度分析时间复杂度：主流程仍然是归并排序的框架，为 O(n log n)。关键的修改在于合并步骤中的统计部分。我们通过双指针（ p 和 r ）技巧，确保了对于每个 q ，检查满足条件的 left 中元素数量的操作是分摊 O(1) 的。因此，整个算法的时间复杂度依然是 O(n log n) ，优于 O(n* k) 的暴力法，尤其当 k 较大时优势明显。空间复杂度：我们需要一个与原数组同样大小的辅助数组来进行归并操作，因此空间复杂度为 O(n)。存储 (value, index) 对也在此空间内。第六步：核心步骤示例假设数组为 [5, 2, 6, 1] ，k=2。原始索引为 0,1,2,3。打包后为 [(5,0), (2,1), (6,2), (1,3)] 。在递归到底层合并时，考虑一次跨越左右的合并：左半部分 left = [(2,1), (5,0)] (已按值排序) 右半部分 right = [(1,3), (6,2)] (已按值排序) 我们需要统计满足 j-i <=2 且值逆序的对。处理右半部分的第一个元素 (1,3) ：在 left 中找到值大于1的元素起始位置 p ，即第一个元素 (2,1) 。检查 left 中从 (2,1) 开始的元素，原始索引是否满足 3 - index <= 2 ，即 index >= 1 。 (2,1) 的索引是1，满足条件。计数+1。 (5,0) 的索引是0，不满足条件（3-0=3>2）。停止扫描。处理右半部分的第二个元素 (6,2) ：在 left 中找到值大于6的元素起始位置 p 。 left 中所有值都不大于6，所以没有满足值条件的元素。计数为0。在此次合并中，跨越左右的、满足k-局部条件的逆序对数量为1（即 (5,0) 和 (1,3) 不满足距离条件， (2,1) 和 (1,3) 满足条件）。递归向上合并，最终可得到总数。总结：本算法巧妙地结合了归并排序的分治特性和“k-局部”这一距离约束。通过携带原始索引，并在合并过程中利用已排序性质和双指针技巧进行高效的范围检查，我们在 O(n log n) 的时间复杂度内解决了问题。这是经典逆序对计数问题的一个非平凡但非常优美的扩展。