归并分治精讲：逆序对的多种面孔

摘要

归并排序的”合并”阶段不只是在排序——它还可以在两个有序段合并时，同步统计”跨越两段的配对数量”。这是一类极重要的算法模式，能将看似需要 $O (n^{2})$ 暴力枚举的统计问题降到 $O (n lo g n)$ 。本文通过三道由易到难的 LeetCode 题目，深度剖析这一模式：LeetCode 315（统计后面更小的元素数目）、LeetCode 493（翻转对），以及 LeetCode 327（区间和的个数）。每道题不只给答案，而是推导为什么归并能解决这个问题，以及为什么暴力或其他方式不够好。

第 1 章归并合并阶段的隐藏能力

1.1 回顾：归并排序的合并阶段

在标准归并排序中，合并阶段的逻辑如下：

左段 L = [1, 3, 5]
右段 R = [2, 4, 6]

合并过程：
i=0, j=0: L[0]=1 < R[0]=2, 取 1
i=1, j=0: L[1]=3 > R[0]=2, 取 2
i=1, j=1: L[1]=3 < R[1]=4, 取 3
...

这个过程里，每次从右段取元素时（即 L[i] > R[j]），说明右段的当前元素比左段的 L[i], L[i+1], ..., L[m] 都小（因为左段有序，L[i] 已经是左段中最小的未处理元素）。换句话说，从右段取 R[j] 的那一刻，R[j] 和左段剩余所有元素都构成了”右小于左”的配对。

这个观察是后续所有”归并统计”问题的核心：利用归并过程中两段的有序性，在 $O (1)$ 的代价内统计出跨越左右两段的所有配对数量。

1.2 逆序对的原始形式

逆序对（Inversion）的定义：在数组中，如果 $i < j$ 且 $a [i] > a [j]$ ，则 $(i, j)$ 是一个逆序对。

逆序对的数量衡量了数组”有多乱”：完全有序时逆序对为 0，完全逆序（降序排列）时逆序对为 $(2 n) = \frac{n ( n - 1 )}{2}$ ，这是最大值。

暴力解法：枚举所有 $(i, j)$ 对， $O (n^{2})$ 。对于 $n = 1 0^{5}$ ，暴力需要 $1 0^{10}$ 次操作，远超时间限制。

归并分治解法：在归并排序的合并阶段，当从右段取元素 $R [j]$ 时，左段剩余元素 $L [i], L [i + 1], ..., L [m - 1]$ 共 $m - i$ 个都与 $R [j]$ 构成逆序对（左段下标 < 右段下标，且值更大）。累加所有合并步骤中的统计，即得总逆序对数量。

复杂度：归并排序本身 $O (n lo g n)$ ，统计操作只在合并步骤中进行，每次 $O (1)$ ，总计 $O (n lo g n)$ ，整体 $O (n lo g n)$ 。

第 2 章 LeetCode 315：统计后面更小的元素数目

2.1 题目

LeetCode 315 - Count of Smaller Numbers After Self（困难）

给你一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质：counts[i] 的值是 nums[i] 右侧且比 nums[i] 小的元素的数量。

输入: nums = [5, 2, 6, 1]
输出: [2, 1, 1, 0]
解释:
  5 右边比 5 小的元素有：2, 1 → counts[0] = 2
  2 右边比 2 小的元素有：1   → counts[1] = 1
  6 右边比 6 小的元素有：1   → counts[2] = 1
  1 右边没有更小的元素      → counts[3] = 0

2.2 为什么这是”逆序对”的变形

将问题等价转化：对每个 nums[i]，统计满足 i < j 且 nums[i] > nums[j] 的 j 的数量。这正是以 nums[i] 为左端点的逆序对数量。

与原始逆序对问题的区别在于：原始问题只要总数，这道题要求每个元素各自的逆序对数量（per-element count）。

2.3 核心难点：元素在归并中会被移动

在归并排序过程中，元素会不断地被搬移，原始的下标关系会被打乱。如果我们只是统计某段中的总逆序对数量（原始问题），不需要关心哪个元素贡献了多少。但这道题要求 per-element 的统计，所以我们必须追踪每个元素的原始下标。

解决方案：不直接排序 nums，而是排序一个存储 (值, 原始下标) 的配对数组。合并时，当从右段取元素 R[j] 时，左段剩余元素 L[i], ..., L[m-1] 的原始下标对应的 counts 各自加 1。

但”各自加 1”看起来需要 $O (m - i)$ 的时间，这会让总复杂度退化到 $O (n^{2})$ 。

更聪明的做法：不在合并时逐个更新，而是记录”合并过程中，右段某个元素 $R [j]$ 在某一步从右段取出时，左段还剩多少个元素”——这个数字就是 $R [j]$ 对应的原始下标应该累加的值。

但等等，问题是左段的元素 L[i] 被取出时，它不知道右段之后还有多少个元素会”排在它前面”。

换个视角：统计的是”每个 L[i] 对应的逆序对”。当 R[j] 从右段取出时（即 R[j] < L[i]），这意味着 R[j] 最终会排在 L[i] 的前面，但 R[j] 的原始下标比 L[i] 大——所以 (L[i].index, R[j].index) 是一个逆序对，counts[L[i].index]++。

但用 counts[L[i].index]++，每次只增加当前左段指针 L[i] 的计数，而不是左段所有剩余元素的计数——这是错误的，因为 L[i+1], ..., L[m-1] 也与 R[j] 形成逆序对，它们也需要加 1。

正确做法 1（懒惰统计）：换个统计方向——不在合并时更新 left-side 元素的 counts，而是统计每个右段元素在多少次合并中”插队”到了左段元素前面。

具体地，维护一个计数器 rightCount，记录到目前为止从右段取了多少个元素。每次从左段取元素 L[i] 时，counts[L[i].index] += rightCount（表示右段已经有 rightCount 个元素排在了 L[i] 的前面，而它们的原始下标都比 L[i] 大，所以都是 L[i] 的逆序对）。

// 合并过程（简化版）
// left[], right[] 是两个有序的 (值, 原始下标) 数组
// counts[] 是结果数组
void merge(int[][] left, int[][] right, int[] counts) {
    int i = 0, j = 0, k = 0;
    int rightCount = 0;  // 到目前为止从 right 取了多少个元素
    int[] merged = new int[left.length + right.length][2];
 
    while (i < left.length && j < right.length) {
        if (left[i][0] <= right[j][0]) {
            // 从左段取元素：右段已经有 rightCount 个元素排在它前面
            // 这些元素的原始下标都比 left[i][1] 大，且值更小，所以是逆序对
            counts[left[i][1]] += rightCount;
            merged[k++] = left[i++];
        } else {
            // 从右段取元素：记录右段已取出的数量
            rightCount++;
            merged[k++] = right[j++];
        }
    }
 
    // 处理左段剩余元素：右段已经全部取完，rightCount 不再增加
    while (i < left.length) {
        counts[left[i][1]] += rightCount;
        merged[k++] = left[i++];
    }
    while (j < right.length) {
        merged[k++] = right[j++];
    }
}

2.4 完整实现

class Solution {
    private int[] counts;   // 结果数组
    private int[][] pairs;  // 存储 (值, 原始下标) 的数组
 
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        counts = new int[n];
        pairs = new int[n][2];
 
        // 初始化：pairs[i] = (nums[i], i)
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = i;
        }
 
        // 归并排序，过程中填充 counts
        mergeSort(pairs, 0, n - 1);
 
        // 将 counts 数组转为 List
        List<Integer> result = new ArrayList<>();
        for (int c : counts) result.add(c);
        return result;
    }
 
    private void mergeSort(int[][] arr, int left, int right) {
        if (left >= right) return;
 
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
 
    private void merge(int[][] arr, int left, int mid, int right) {
        int[][] temp = new int[right - left + 1][2];
        int i = left, j = mid + 1, k = 0;
        int rightCount = 0;  // 到目前为止从右段 [mid+1, right] 取出的元素数量
 
        while (i <= mid && j <= right) {
            if (arr[i][0] <= arr[j][0]) {
                // 从左段取：当前左段元素在原始数组中的位置 arr[i][1]
                // 已有 rightCount 个右段元素（原始下标更大）排在它前面（值更小）
                counts[arr[i][1]] += rightCount;
                temp[k++] = arr[i++];
            } else {
                // 从右段取：记录取出数量
                rightCount++;
                temp[k++] = arr[j++];
            }
        }
 
        // 左段剩余：右段已全部排完，rightCount 固定
        while (i <= mid) {
            counts[arr[i][1]] += rightCount;
            temp[k++] = arr[i++];
        }
 
        // 右段剩余
        while (j <= right) {
            temp[k++] = arr[j++];
        }
 
        // 将合并结果写回原数组
        for (int t = 0; t < temp.length; t++) {
            arr[left + t] = temp[t];
        }
    }
}

复杂度分析：

时间： $O (n lo g n)$ ，与归并排序相同，统计操作不增加渐近复杂度
空间： $O (n)$ ，临时数组

2.5 正确性验证

以 nums = [5, 2, 6, 1] 为例：

初始 pairs = [(5,0), (2,1), (6,2), (1,3)]

第一轮归并（left: [(5,0), (2,1)]，合并为有序段）：

i=0, j=1：(5,0) vs (2,1)，取 (2,1)，rightCount=1
i=0，左段剩余：counts[0] += 1 = 1，取 (5,0)
合并结果：[(2,1), (5,0)]

第一轮归并（right: [(6,2), (1,3)]）：

i=0, j=1：(6,2) vs (1,3)，取 (1,3)，rightCount=1
i=0，左段剩余：counts[2] += 1 = 1，取 (6,2)
合并结果：[(1,3), (6,2)]

第二轮归并（[(2,1),(5,0)] 和 [(1,3),(6,2)]）：

(2,1) vs (1,3)：取 (1,3)，rightCount=1
(2,1) vs (6,2)：取 (2,1)，counts[1] += 1 = 1
(5,0) vs (6,2)：取 (5,0)，counts[0] += 1 = 2
右段剩余 (6,2)，counts[2] 不再增加
合并结果：[(1,3),(2,1),(5,0),(6,2)]

最终 counts = [2, 1, 1, 0]，与期望一致。

第 3 章 LeetCode 493：翻转对

3.1 题目

LeetCode 493 - Reverse Pairs（困难）

给定一个数组 nums，如果 i < j 且 nums[i] > 2 * nums[j]，则称 (i, j) 为一个翻转对。返回数组中所有翻转对的数量。

输入: nums = [1, 3, 2, 3, 1]
输出: 2
解释: (1, 4) 和 (3, 4) 是翻转对
     nums[1]=3 > 2*nums[4]=2
     nums[3]=3 > 2*nums[4]=2

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

3.2 与 LeetCode 315 的关键区别

LeetCode 315 的条件是 nums[i] > nums[j]，而 LeetCode 493 的条件是 nums[i] > 2 * nums[j]。这个区别看似微小，实则导致了完全不同的归并统计策略。

在 315 中，我们的统计和合并是同步进行的：在合并 L 和 R 的同时，每次从 R[j] 取元素时，rightCount 累加到左段剩余元素的 counts 中。这之所以可行，是因为”从 R[j] 取出”这个事件，等价于 R[j] < L[i]（合并的判断条件），也就是满足翻转对条件的判断。

但对于 493，条件是 L[i] > 2 * R[j]。这与合并操作的判断 L[i] <= R[j]（用于决定从哪边取）不同步。换句话说，满足翻转对条件的配对，不一定是在归并的某一步”恰好被检测到”的。

关键认知：统计与合并要分离

对于条件形如 f(L[i]) > g(R[j]) 的归并统计，当 f 和 g 与合并的大小比较不完全相同时，需要将统计阶段和合并阶段分开：

统计阶段：在合并之前，用双指针在有序的 L 和 R 上扫描，统计满足条件的跨段配对数量（此时 L 和 R 都已经是有序的，可以用单调性加速）

合并阶段：正常归并排序，将 L 和 R 合并为有序段

3.3 双指针统计翻转对

在合并 L 和 R 之前，L 和 R 都已经是有序的（递归排好了）。现在要统计满足 L[i] > 2 * R[j] 的配对数量。

对固定的 j，满足条件的 i 是 L 中所有值大于 2 * R[j] 的元素。由于 L 有序，这些元素是 L 的某个后缀 L[k..m-1]（其中 k 是第一个满足 L[k] > 2 * R[j] 的位置）。

关键观察：随着 j 增大，R[j] 增大，2 * R[j] 增大，满足条件的 k 只会增大（不会减小）。因此可以用双指针：

j 从 0 到 n-1 遍历右段
k 从 0 开始，对每个 j 向右移动直到 L[k] <= 2*R[j]
配对数量 += m - k   （L[k..m-1] 中所有元素都满足条件）

整体统计复杂度： $O (m + n)$ ，与合并本身的复杂度相同。

3.4 完整实现

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
 
    private int mergeSort(int[] nums, int left, int right) {
        if (left >= right) return 0;
 
        int mid = left + (right - left) / 2;
 
        // 递归排序左右两段，并统计各段内部的翻转对
        int count = mergeSort(nums, left, mid)
                  + mergeSort(nums, mid + 1, right);
 
        // 统计跨越两段的翻转对
        // 此时 nums[left..mid] 和 nums[mid+1..right] 都已有序
        count += countCross(nums, left, mid, right);
 
        // 合并两个有序段
        merge(nums, left, mid, right);
 
        return count;
    }
 
    private int countCross(int[] nums, int left, int mid, int right) {
        // 统计满足 nums[i] > 2 * nums[j] 的跨段配对数量
        // 其中 i ∈ [left, mid]，j ∈ [mid+1, right]
        int count = 0;
        int k = mid + 1;  // 双指针的右端指针
 
        for (int i = left; i <= mid; i++) {
            // 对当前的 i，找到第一个满足 nums[k] * 2 >= nums[i] 的 k
            // 注意：用 nums[i] > 2 * nums[k]，但要防止溢出
            // 等价判断：nums[i] / 2.0 > nums[k]（用浮点避免溢出）
            // 更安全的方式：将 nums 转成 long
            while (k <= right && (long) nums[i] > 2L * nums[k]) {
                k++;
            }
            // [mid+1, k-1] 范围内的元素都满足 nums[j] * 2 < nums[i]
            count += k - (mid + 1);
        }
 
        return count;
    }
 
    private void merge(int[] nums, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
 
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= right) temp[k++] = nums[j++];
 
        for (int t = 0; t < temp.length; t++) {
            nums[left + t] = temp[t];
        }
    }
}

生产避坑：整数溢出

2 * nums[j] 在 nums[j] 接近 Integer.MAX_VALUE / 2 时会溢出。必须将比较表达式改为 (long) nums[i] > 2L * nums[j]，或者将整个数组提前转为 long[]。这是面试中容易被扣分的细节。

3.5 为什么双指针的 k 不需要重置

这是最容易让人困惑的地方。循环中 k 从 mid+1 开始，然后随着 i 的增大，k 只会增大（不会减小），这看起来好像 k 没有随 i 重置？

这是正确的。原因是：当 i 从 i 增大到 i+1 时，nums[i+1] <= nums[i]（因为左段 [left, mid] 已有序，但我们是从小到大遍历，所以 nums[i+1] >= nums[i]，即左段值递增）。

等等，左段是从小到大有序的，所以 nums[i+1] >= nums[i]，这意味着 nums[i+1] > 2 * nums[k] 的条件比 nums[i] > 2 * nums[k] 更难满足（左边更大了，但右边 2*nums[k] 没变）……

等等，这里要重新想：随着 i 增大，nums[i] 增大（因为左段有序，我们从 left 到 mid 遍历），所以 nums[i] > 2 * nums[k] 的条件更容易满足（左边更大），k 应该继续右移或保持不动，但不会左移。

因此 k 单调递增，每次内层 while 循环总共最多移动 $O (n)$ 步，整体 countCross 的时间复杂度是 $O (m + n)$ 。

第 4 章 LeetCode 327：区间和的个数

4.1 题目

LeetCode 327 - Count of Range Sum（困难）

给你一个整数数组 nums 以及两个整数 lower 和 upper，求数组中值位于范围 [lower, upper]（含两端点）之内的区间和的个数。

区间和 S(i, j) 表示在 nums[i] 到 nums[j] 的元素总和（ $i \leq j$ ）。

输入: nums = [-2, 5, -1], lower = -2, upper = 2
输出: 3
解释: 满足条件的三个区间是：[0,0]、[2,2]、[0,2]
     S(0,0) = -2 ∈ [-2, 2]
     S(2,2) = -1 ∈ [-2, 2]
     S(0,2) = 2 ∈ [-2, 2]

4.2 前缀和转化：将问题变为”有序段上的配对统计”

核心转化：区间和 $S (i, j) = prefix [j + 1] - prefix [i]$ ，其中 $prefix [k] = \sum_{t = 0}^{k - 1} nums [t]$ （前缀和数组，prefix[0] = 0）。

条件 $lower \leq S (i, j) \leq upper$ 等价于：

$lower \leq prefix [j + 1] - prefix [i] \leq upper$

即：

$prefix [j + 1] - upper \leq prefix [i] \leq prefix [j + 1] - lower$

现在问题变成：在前缀和数组中，统计满足 $i < j + 1$ 且 $prefix [j + 1] - upper \leq prefix [i] \leq prefix [j + 1] - lower$ 的配对 $(i, j + 1)$ 数量。

这正是一个”两个有序段上的配对计数”问题：在归并排序前缀和数组的过程中，当合并 L = prefix[left..mid] 和 R = prefix[mid+1..right] 时，对每个 R[j]，统计 L 中满足区间条件的元素数量。

4.3 双指针统计区间配对

对固定的 R[j] = prefix[j']（j' 是某个 j+1），满足条件的 L[i] 需要满足：

$R [j] - upper \leq L [i] \leq R [j] - lower$

由于 L 有序，满足条件的 L[i] 是某个连续段 [lo, hi)，可以用双指针维护：

int lo = left, hi = left;  // [lo, hi) 是满足条件的区间
 
for (int j = mid + 1; j <= right; j++) {
    // 随 R[j] 增大，lo 和 hi 单调右移
    while (lo <= mid && prefix[lo] < prefix[j] - upper) lo++;
    while (hi <= mid && prefix[hi] <= prefix[j] - lower) hi++;
    count += hi - lo;
}

注意：lo 和 hi 不需要重置，因为随着 prefix[j] 增大（R 有序），下界 prefix[j] - upper 和上界 prefix[j] - lower 也单调递增，满足条件的 lo 和 hi 只会向右移动。

4.4 完整实现

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        // 构建前缀和数组
        // prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
        // 使用 long 防止溢出（nums 中值可能高达 10^4，n 高达 10^4，总和可达 10^8）
        int n = nums.length;
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
 
        return mergeSort(prefix, 0, n, lower, upper);
    }
 
    private int mergeSort(long[] prefix, int left, int right, int lower, int upper) {
        if (left >= right) return 0;
 
        int mid = left + (right - left) / 2;
 
        // 递归处理左右两段
        int count = mergeSort(prefix, left, mid, lower, upper)
                  + mergeSort(prefix, mid + 1, right, lower, upper);
 
        // 统计跨越两段的满足条件的配对
        // 此时 prefix[left..mid] 和 prefix[mid+1..right] 都已有序
        int lo = left, hi = left;
        for (int j = mid + 1; j <= right; j++) {
            // 找到 [lo, hi) 使得 prefix[lo..hi-1] ∈ [prefix[j]-upper, prefix[j]-lower]
            while (lo <= mid && prefix[lo] < prefix[j] - upper) lo++;
            while (hi <= mid && prefix[hi] <= prefix[j] - lower) hi++;
            count += hi - lo;
        }
 
        // 合并两个有序段
        merge(prefix, left, mid, right);
 
        return count;
    }
 
    private void merge(long[] prefix, int left, int mid, int right) {
        long[] temp = new long[right - left + 1];
        int i = left, j = mid + 1, k = 0;
 
        while (i <= mid && j <= right) {
            if (prefix[i] <= prefix[j]) {
                temp[k++] = prefix[i++];
            } else {
                temp[k++] = prefix[j++];
            }
        }
        while (i <= mid) temp[k++] = prefix[i++];
        while (j <= right) temp[k++] = prefix[j++];
 
        for (int t = 0; t < temp.length; t++) {
            prefix[left + t] = temp[t];
        }
    }
}

4.5 复杂度分析与正确性

时间复杂度：归并排序 $O (n lo g n)$ ，统计阶段每层 $O (n)$ ，整体 $O (n lo g n)$ 。

空间复杂度： $O (n)$ ，临时数组。

正确性关键：为什么在归并排序前缀和数组是正确的？

关键在于，统计 count 的阶段是在合并之前执行的，此时 prefix[left..mid] 和 prefix[mid+1..right] 虽然已经被重新排序（它们各自是有序的），但它们的原始含义（前缀和的值）没有改变。我们统计的是”来自左段（原始下标 $\leq$ mid）的前缀和” 和 “来自右段（原始下标 $>$ mid）的前缀和”满足条件的配对，这恰好对应原始问题中 $i \leq j$ 的区间和（因为 $prefix [j + 1] - prefix [i]$ 中，j+1 在右段，i 在左段，所以 i < j+1）。

设计哲学：前缀和 + 归并分治的通用性

“前缀和 + 归并分治”是一类通用的模式，凡是需要统计”子数组的某种聚合统计量满足条件的个数”，都可以考虑：

将区间聚合统计量转化为”两个前缀统计量之差”

对前缀统计量数组进行归并分治

在合并阶段统计跨段配对数量

第 5 章三题横向对比与模式总结

5.1 三道题的统一视角

特征	LeetCode 315	LeetCode 493	LeetCode 327
条件	$L [i] > R [j]$	$L [i] > 2 \cdot R [j]$	$R [j] - upper \leq L [i] \leq R [j] - lower$
条件与合并大小比较关系	等价（从右段取元素时成立）	不等价	不等价
统计策略	统计和合并同步	先统计，再合并（`countCross` 分离）	先统计，再合并（双指针范围查询）
统计时需要 per-element 结果	是（315 要每个元素各自的数量）	否（493 只要总数）	否（327 只要总数）
处理原始下标的方式	存储 `(值, 下标)` 配对，用 `rightCount` 记录	不需要追踪原始下标	不需要追踪原始下标
时间复杂度	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$

5.2 归并分治统计的通用模板

int mergeSort(T[] arr, int left, int right) {
    if (left >= right) return 0;
 
    int mid = left + (right - left) / 2;
 
    // 步骤 1：递归处理左右两段，统计各段内部的配对数
    int count = mergeSort(arr, left, mid)
              + mergeSort(arr, mid + 1, right);
 
    // 步骤 2：在合并之前（或期间），统计跨越两段的配对数
    // 此时 arr[left..mid] 和 arr[mid+1..right] 均已有序，可利用有序性加速
    count += countCross(arr, left, mid, right);
 
    // 步骤 3：将两段合并为有序段（标准归并）
    merge(arr, left, mid, right);
 
    return count;
}

5.3 什么情况下统计可以与合并同步

同步条件：当”满足统计条件”和”合并时从右段取元素”是等价的事件。

具体来说，如果统计的条件是 L[i] > R[j]（普通逆序对），那么：

合并时从右段取 R[j]，等价于 L[i] > R[j]（当前左段头部比右段头部大）
此时左段的 L[i], L[i+1], ..., L[m-1] 都比 R[j] 大，逆序对数量是 m - i（或用 rightCount 统计）

不同步条件：当统计条件是 L[i] > 2 * R[j]（493）或范围查询（327），条件与合并判断不等价，必须将统计阶段独立出来。

第 6 章本文核心结论

归并的”合并”阶段是统计跨段配对的黄金时机：此时左右两段分别有序，可以用双指针在 $O (m + n)$ 时间内完成原本需要 $O (mn)$ 的配对统计。
区分”同步统计”和”分离统计”：统计条件与归并方向一致时（如 $L [i] > R [j]$ ），可以同步进行；条件更复杂时（如范围查询），先统计再合并。
整数溢出是这类题的常见陷阱：LeetCode 493 中需要用 (long) nums[i] > 2L * nums[j]，LeetCode 327 中需要将前缀和数组定义为 long[]。
追踪原始下标需要存储 (值, 下标) 配对：LeetCode 315 需要 per-element 的结果，因此在排序过程中必须携带原始下标信息。
前缀和将区间聚合问题转化为前缀差问题：LeetCode 327 的核心转化，将”区间和 ∈ [lower, upper]“变为”两个前缀和的差 ∈ [lower, upper]“，从而适配归并分治框架。

汀的知识碎片

文章导航

02 归并分治精讲：逆序对的多种面孔

归并分治精讲：逆序对的多种面孔

摘要

第 1 章归并合并阶段的隐藏能力

1.1 回顾：归并排序的合并阶段

1.2 逆序对的原始形式

第 2 章 LeetCode 315：统计后面更小的元素数目

2.1 题目

2.2 为什么这是”逆序对”的变形

2.3 核心难点：元素在归并中会被移动

2.4 完整实现

2.5 正确性验证

第 3 章 LeetCode 493：翻转对

3.1 题目

3.2 与 LeetCode 315 的关键区别

3.3 双指针统计翻转对

3.4 完整实现

3.5 为什么双指针的 k 不需要重置

第 4 章 LeetCode 327：区间和的个数

4.1 题目

4.2 前缀和转化：将问题变为”有序段上的配对统计”

4.3 双指针统计区间配对

4.4 完整实现

4.5 复杂度分析与正确性

第 5 章三题横向对比与模式总结

5.1 三道题的统一视角

5.2 归并分治统计的通用模板

5.3 什么情况下统计可以与合并同步

第 6 章本文核心结论

On this page

汀的知识碎片

文章导航

02 归并分治精讲：逆序对的多种面孔

归并分治精讲：逆序对的多种面孔

摘要

第 1 章 归并合并阶段的隐藏能力

1.1 回顾：归并排序的合并阶段

1.2 逆序对的原始形式

第 2 章 LeetCode 315：统计后面更小的元素数目

2.1 题目

2.2 为什么这是”逆序对”的变形

2.3 核心难点：元素在归并中会被移动

2.4 完整实现

2.5 正确性验证

第 3 章 LeetCode 493：翻转对

3.1 题目

3.2 与 LeetCode 315 的关键区别

3.3 双指针统计翻转对

3.4 完整实现

3.5 为什么双指针的 k 不需要重置

第 4 章 LeetCode 327：区间和的个数

4.1 题目

4.2 前缀和转化：将问题变为”有序段上的配对统计”

4.3 双指针统计区间配对

4.4 完整实现

4.5 复杂度分析与正确性

第 5 章 三题横向对比与模式总结

5.1 三道题的统一视角

5.2 归并分治统计的通用模板

5.3 什么情况下统计可以与合并同步

第 6 章 本文核心结论

On this page

第 1 章归并合并阶段的隐藏能力

第 5 章三题横向对比与模式总结

第 6 章本文核心结论