分治与归并计数 · HTML
数学 / 逻辑形态
对索引域 [lo,hi) 二分。递归统计两侧内部关系；L、R 有序后，用单调指针统计满足 P(L[i],R[j]) 的跨半区对，再归并。
识别信号
- 统计满足大小或范围关系的索引对。
- 关系包含 i<j，可由左右索引半区保证。
- 两侧有序后合法配对边界单调。
- 暴力 O(n²)，跨半区可线性批量累计。
- 计数后仍需有序结果供父层使用。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 没有索引先后约束的频次 | 普通排序或哈希计数可能更直接。 |
| 关系边界不单调 | 若 j 随 i 来回移动，线性 combine 的依据消失。 |
| 在线更新 | 这是离线算法；动态查询更适合 Fenwick/segment tree。 |
核心不变量
进入 combine 时两半各自有序且内部答案完整；关系指针只前进，离开时跨半区合法对恰计一次且父区间有序。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 数组/记录、共享 buffer、累计计数、关系指针与归并指针。 |
| Transition | 递归左右；在有序两半上批量计数；随后归并回父区间。 |
| Frontier / order | 递归后序；每层前沿是两个有序半区的未消费元素和单调关系边界。 |
Python 骨架
def count_inversions(nums):
a, buf = list(nums), [0] * len(nums)
def solve(lo, hi):
if hi - lo <= 1: return 0
mid = (lo + hi) // 2
count = solve(lo, mid) + solve(mid, hi)
i, j, w = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
buf[w] = a[i]; i += 1
else:
buf[w] = a[j]; j += 1; count += mid - i
w += 1
while i < mid: buf[w] = a[i]; i += 1; w += 1
while j < hi: buf[w] = a[j]; j += 1; w += 1
a[lo:hi] = buf[lo:hi]
return count
return solve(0, len(a))
正确性思路
- 递归完整统计左右内部关系。
- 若 a[i]>a[j]，左半有序意味着 a[i:mid] 全大于 a[j]，可加 mid-i；否则移动 i 不会漏逆序。
- 每个索引对在其最低共同分割层成为跨半区对，所以恰计一次。
复杂度
| Time | Space | Parameters |
|---|
| O(n log n) | O(n) buffer + O(log n) 栈 | n 为元素数；每层 combine 必须 O(n)。 |
边界条件
- 重复值是否计入
- 空/单元素
- 计数溢出
- 严格与非严格关系
- 需保留原索引
- 覆盖数据的时序
错误模式
| Pattern | Why it fails / fix |
|---|
| 等号方向错误 | <= 走哪侧决定重复值是否计入。 |
| 计数后不归并 | 父层依赖子区间有序；否则上层指针失效。 |
| 每个 i 重置 j | 退化为 O(n²)；必须利用单调边界。 |
| 值对与索引对混淆 | 重复值的多个实例通常对应不同索引对。 |
选择与排除规则
- 先定严格性与计数对象。
- 证明有序后配对边界单调。
- 每层恢复父层需要的有序摘要。
- 在线场景改 Fenwick/segment tree。
相关模板
| Relation | Template | Boundary |
|---|
| specialization | 分治：拆分、递归、合并 | 合并时利用两半有序统计跨半区关系。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 共 2 对：(4,1)、(4,3)。 |
| Setup | 序列 [4,1,3]，统计前值大于后值。 |
| Trace | 右半 [1,3] 已排序；合并时 1 与 3 各让剩余左项数 1 加入。 |
Recall prompts
我的补充