CSCI3160 Exercise 2：分治与线性合并

课程：CSCI3160 本组：Regular Exercise Set 2，Problem 1–5；题目原件（本地课件） p.1；官方答案（本地课件） p.1–2 定位：理解怎样利用有序性把合并降到线性时间，以及怎样写出完整的算法、正确性理由和复杂度分析。前后：上一组 Exercise 1：随机算法与期望分析

本文为逐题学习解析。题意采用中文概述，完整英文题面见原件；推导、伪代码、易错分析为本解析补充。所有数组采用从 1 开始的下标，页码指 PDF 页码。默认课程 RAM 模型，整数比较、加法和数组访问为常数时间。

Problem 1：线性时间统计跨集合逆序对（题目 p.1；答案 p.1）

题意概述。 两个不相交集合各有 $n$ 个整数，分别以升序数组保存。统计第一个集合中大于第二个集合元素的有序对，要求线性时间。

把“每个数重新查一次”变成“一起扫一遍”

固定左数组中的一个数 $a$ ，它贡献的对数恰好是右数组中严格小于 $a$ 的元素数。单独二分一次花 $O(\log n)$ ，为每个 $a$ 二分就花 $O(n\log n)$ 。但左数组按升序处理，下一个 $a$ 更大，右边已确定小于前一个 $a$ 的元素一定也小于新 $a$ ，不必从头再找。

输入：升序数组 L[1..u]、R[1..v]
j ← 1；c ← 0
对 i 从 1 到 u：
    当 j ≤ v 且 R[j] < L[i]：
        j ← j + 1
    c ← c + (j - 1)
返回 c

原题是 $u=v=n$ ；这里写成不同长度，以便下一题直接复用。j-1 就是当前右数组中已确认严格小于 L[i] 的元素个数。不要在每个 i 开始时把 j 重置。

算一遍（数字是本解析自取）

取 $L=[2,5,8]$ ， $R=[1,4,7]$ 。

当前 L[i]	右边严格更小的数	j	本次新增	累计 c
2	1	2	1	1
5	1、4	3	2	3
8	1、4、7	4	3	6

六对就是 $(2,1),(5,1),(5,4),(8,1),(8,4),(8,7)$ 。

正确性：计到的全合法，合法的全计到

当内层循环结束时，排序性质保证右数组前 $j-1$ 个数全部小于当前左元素，其余数全部不小于它。所以新增 $j-1$ 正好是以当前左元素为第一项的合法对数。外层循环处理每个左元素一次，而一对只有一个第一项，因此没有遗漏，也没有重复。

为什么嵌套循环仍然线性

外层走 $u$ 次；内层的 j 在整个算法中只从 1 增至至多 $v+1$ ，总共至多增加 $v$ 次。不能把“外层次数”乘上“内层理论最大次数”，因为内层不会每轮重新走完整个右数组。因此总耗时 $O(u+v)$ ，额外空间 $O(1)$ 。

与官方解法的对应。 官方把两数组归并，然后从小到大扫描；维护“已见过多少个来自右数组的元素”。见到左数组元素就把这个计数加入答案。本文的 j-1 就是该计数，只省去了显式保存合并数组。

边界。 若右数组所有元素都较大，计数始终为零；若右数组全较小，每个左元素贡献 $v$ 。扩展到允许重复值时必须用严格小于，等值不算逆序。

Problem 2：归并排序顺带统计全部逆序对（题目 p.1；答案 p.1）

题意概述。 给定未排序整数数组，统计所有满足位置在前而数值更大的元素对，目标时间 $O(n\log n)$ 。

为什么不能先把原数组排序再统计

逆序对由原位置关系 $i<j$ 和数值关系 $A[i]>A[j]$ 共同定义。直接把全数组排序会丢掉原位置关系。分治应先按原位置的中点分为左半和右半，此时跨半区的对自动满足左元素原本在前，再用数值排序来辅助计数。

任意逆序对恰好属于三类之一：两端都在左半、两端都在右半、第一端在左半第二端在右半。这三类不重叠且覆盖全部答案。

关键设计：递归同时返回数量和有序数组

如果递归只返回数量，父层还得重新排序来统计跨半区贡献。改成递归顺带返回有序数组，就能让每层只做线性合并。

CountSort(A)：
    若长度 ≤ 1：返回 (0, A)
    按原位置将 A 切成大小尽量接近的两半
    (cL, L) ← CountSort(左半)
    (cR, R) ← CountSort(右半)
    i ← 1；j ← 1；cross ← 0；B ← 空数组
    当 i ≤ L 的长度 且 j ≤ R 的长度：
        若 L[i] ≤ R[j]：
            将 L[i] 加入 B；i ← i + 1
        否则：
            cross ← cross + (L 的长度 - i + 1)
            将 R[j] 加入 B；j ← j + 1
    将 L 或 R 尚未处理的后缀加入 B
    返回 (cL + cR + cross, B)

这一写法与 Q1 按左元素累计等价，不过现在按右元素累计：当 $R[j]<L[i]$ ，左数组剩下的每个元素都不小于 $L[i]$ ，因此全部大于 $R[j]$ ，一次增加整个剩余长度。

算一遍（自取数组）

对 [3,1,2,1]，原位置分为 [3,1] 和 [2,1]。

左半有 1 对，递归返回 [1,3]。
右半有 1 对，递归返回 [1,2]。
合并时，左右首项都是 1，先取左边，不新增；取右边的 1 时，剩余左边 [3] 贡献 1；取右边的 2 时，同一个左边 3 再贡献 1。

跨半区共 2 对，总数 $1+1+2=4$ 。按原位置核对： $(1,2),(1,3),(1,4),(3,4)$ ，确实四对。

等值规则为何和下一题不同

本题条件是严格大于，两个 1 不能计数，所以相等时先输出左元素。若相等时走右侧计数分支，就会把相等元素误认为逆序。下一题支配定义用小于等于，会需要另一种计数含义，不能混用不等号。

正确性与复杂度

归纳假设两侧递归数量正确且数组有序。上面的合并对每个右元素恰好数出仍未取出的、严格大于它的左元素；已取出的左元素不大于当前右元素，不贡献逆序。因此跨半区数量正确。三类相加正确，合并结果也有序，递归接口成立。

递归式为

T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+O(n).

第 $d$ 层有大约 $2^d$ 个子问题，每个规模约 $n/2^d$ ，该层总工作仍为 $O(n)$ ；层数 $O(\log n)$ ，所以总时间 $O(n\log n)$ 。常规共享归并缓冲区的实现额外空间 $O(n)$ ，递归栈 $O(\log n)$ 。

Problem 3：二维支配计数（题目 p.1；答案 p.1）

题意概述。 将课堂中的二维支配计数改进至 $O(n\log n)$ 期望时间。原题引用课堂定义，因此必须先补齐定义，不能自行猜测严格还是非严格不等号。

课堂定义和一个容易遗漏的条件

Lecture 2（本地课件） p.14–16 定义：点 $q$ 支配另一个点 $p$ ，当且仅当

p_x\le q_x\quad\text{and}\quad p_y\le q_y.

输入的所有点 x 坐标互异，但没有说 y 坐标互异。每个点要输出自己支配的其他点数，不计自己。

用 x 划分后，跨半区只剩 y 条件

先把所有点按 x 升序排序，之后始终按这一固定次序的中点递归。左半任何点的 x 都小于右半任何点的 x。因此：

左半点不可能支配右半点，x 条件不成立。
右半点 $q$ 是否支配左半点 $p$ ，只需检查 $p_y\le q_y$ 。

递归已处理同半区的支配关系；父层只需给每个右半点增加左半区的贡献。这又成为“两份按 y 排好的数组之间线性计数”。

可实现的递归接口

预排序后的 x 数组保留不动，用它划分点的集合。每次递归额外返回该子集按 y 排序的列表；每个点保留唯一身份及累计答案。不能把 x 数组原地改成按 y 排序后，还对它按中点当作 x 划分。

预处理：按 x 升序排序得到 X；所有点的 count 设为 0
Solve(l, r)：
    若 l = r：返回只含 X[l] 的 y 有序列表
    mid ← floor((l+r)/2)
    L ← Solve(l, mid)
    R ← Solve(mid+1, r)
    i ← 1；j ← 1；t ← 0；B ← 空列表
    当 L 或 R 还有未处理点：
        若 R 已用完，或 L 未用完且 L[i].y ≤ R[j].y：
            将 L[i] 加入 B
            i ← i + 1；t ← t + 1
        否则：
            count[R[j]] ← count[R[j]] + t
            将 R[j] 加入 B；j ← j + 1
    返回 B

若输入为空，直接返回空结果；上面递归针对非空区间。

t 只数本次合并中已输出的左半点。遇到右半点时，先前输出的右半点不会增加 t，因为右半内部贡献递归已经算过。

为什么 y 相等时左半点必须先处理

支配条件允许相等。若左点 y 为 2、右点 y 也为 2，它们满足 y 条件，且跨半区自动满足 x 条件，因此这一对必须计入。让左点先输出，就会先增加 t，再让右点读取增加后的计数。若反过来，就会漏算这一对。

算一遍：完整保留相等 y 的情况（数字是本解析自取）

令四点按 x 排序为 $a=(1,2),b=(2,1),c=(3,2),d=(4,3)$ 。

左半 $\{a,b\}$ 内互不支配，答案都为 0，按 y 返回 [b,a]。右半 $\{c,d\}$ 内，d 支配 c，所以 c 的局部答案为 0，d 为 1，返回 [c,d]。

合并动作	t	对答案的影响
输出左点 b，y=1	1	无
输出左点 a，y=2	2	相等 y 时先左后右
输出右点 c，y=2	2	c 加 2，变成 2
输出右点 d，y=3	2	d 加 2，从 1 变成 3

最后 a、b、c、d 的支配数分别为 0、0、2、3。手工看坐标：c 支配 a、b；d 支配 a、b、c，吻合。

为什么既不重复也不遗漏

从根向下追踪任意两点，它们起初位于同一个子问题，直到唯一一个节点把它们分到左右两侧。在这个节点，跨半区计数正好决定它们是否构成支配；更深的节点不会再同时包含这两点，更高的节点则把它们的关系交给同一侧的递归处理。因此每个合法关系只增加一次。加上递归内部已正确计数，父层结果就正确。

更直白地说：本层只加左右之间的关系，绝不重算左左或右右；两边递归也从未看过对侧的点，所以它们没有提前算过本层的跨边关系。

为什么能满足“期望”时间要求

按 x 使用归并排序花最坏 $O(n\log n)$ ；递归每层 y 合并总共 $O(n)$ ，层数 $O(\log n)$ ，也是最坏 $O(n\log n)$ 。两者相加仍是 $O(n\log n)$ 。确定性的最坏保证比题目要求的期望保证更强，自然满足要求。

这沿用官方“按 x 分左右、按 y 合并”的思路，补出了初始排序与数据结构约定。官方所说递归返回有序列表，这里的“有序”明确指 y 顺序。不能在每个递归节点重新按 y 排序，否则合并成本升到 $O(n\log n)$ ，总时间会退回 $O(n\log^2 n)$ 。

Problem 4：最大子数组——先解固定端点，再处理跨中点（题目 p.1；答案 p.1–2）

题意概述。 数组含正负数，子数组必须连续且非空。第一问固定右端点为数组末尾，在线性时间内找最大和；第二问允许任意左右端点，要求 $O(n\log n)$ 。

第一问：固定右端点就只有 n 个候选

候选恰好是 $A[n:n],A[n-1:n],\ldots,A[1:n]$ 。若每次重新求和，花费 $1+2+\cdots+n$ ，成为平方时间。但相邻两个候选只差最左边一个元素，累积维护即可。

s ← 0；best ← 负无穷；bestLeft ← n
对 i 从 n 递减到 1：
    s ← s + A[i]
    若 s > best：
        best ← s；bestLeft ← i
返回 (bestLeft, n, best)

循环中 s 始终是从当前 i 到 n 的后缀和。每个候选都恰好检查一次，所以返回最大者；只做一次扫描，时间 $O(n)$ 、额外空间 $O(1)$ 。

用题目给定数组算到最后

题目数组是 [13,-3,-25,20,-3,-16,-23,18]。

i	新加入 A[i]	当前后缀和 s	当前最大后缀和
8	18	18	18
7	-23	-5	18
6	-16	-21	18
5	-3	-24	18
4	20	-4	18
3	-25	-29	18
2	-3	-32	18
1	13	-19	18

所以固定右端点为 8 时，最佳为 $A[8:8]$ ，和为 18。

为什么 best 不能初始化为 0。 子数组不允许为空。对自取例子 [-5,-2]，两个后缀的和为 -2、-7，答案应为 -2。如果初始化为 0，就会返回一个不存在的合法子数组和。也可直接用末元素初始化，避免负无穷哨兵。

第二问：最优区间只可能位于三种位置

在区间 $[l,r]$ 中取中点 $m$ 。任何连续子数组必为：完全在左边、完全在右边、跨过中点。前两类交给递归，第三类必须单独计算，否则会漏掉最优答案。

一个跨中点的连续子数组一定从左半某个位置一路延伸到 $m$ ，再从 $m+1$ 延伸到右半某个位置。因此它恰好由一个左半后缀和一个右半前缀拼成。

令左半后缀和为 $L(i)$ ，右半前缀和为 $R(j)$ 。左右端点选择互不限制，故

\max_{l\le i\le m<j\le r}\bigl(L(i)+R(j)\bigr) =\max_{l\le i\le m}L(i)+\max_{m<j\le r}R(j).

证明分两步：任意一对选择都不超过右边两个最大值之和；分别取到两个最大值的端点又能构成一个合法跨中点子数组，所以这个上界可以达到。

MaxSubarray(l, r)：
    若 l = r：返回 (l, r, A[l])
    m ← floor((l+r)/2)
    leftBest ← MaxSubarray(l, m)
    rightBest ← MaxSubarray(m+1, r)
    从 m 向 l 扫描：求最大非空后缀，记起点 i 和和值 L
    从 m+1 向 r 扫描：求最大非空前缀，记终点 j 和和值 R
    crossBest ← (i, j, L+R)
    返回 leftBest、rightBest、crossBest 中和值最大者

同一个原题数组的顶层合并

在第 4 项后分割。左半 [13,-3,-25,20] 的后缀和，从右往左依次为 $20,-5,-8,5$ ，最大为 20，起点是 4。右半 [-3,-16,-23,18] 的前缀和依次为 $-3,-19,-42,-24$ ，最大为 -3，终点是 5。因此最佳跨中点区间是 $A[4:5]$ ，和为 $20-3=17$ 。

左半递归得到 $A[4:4]$ 、和 20；右半递归得到 $A[8:8]$ 、和 18。三者比较 $\max\{20,18,17\}=20$ ，所以全局最佳是 $A[4:4]$ 。

为了核实左半结果：左半的再一次划分为 [13,-3] 与 [-25,20]。它们最佳和分别为 13 与 20；跨这次中点的最大值为左后缀 10 加右前缀 -5，得到 5，因此左半选 20。右半划分为 [-3,-16] 与 [-23,18]，内部最佳分别是 -3 与 18，跨区最大是 -16 加 -5 等于 -21，因此右半选 18。

补充：跨中点的两个最优选择能独立相加，依赖连续性。 左后缀必覆盖到 m，右前缀必从 m+1 开始，所以无论各自最优端点在哪里，拼接中间都没有空隙。自取 [5,-100,6,7] 在第二项后分半：左半任意最优子数组是[5]，右半最优是[6,7]，两者“相加18”并不是原数组里的连续区间；合法跨区的左后缀只能选[-100]或[5,-100]，最佳-95，加右前缀13只得-82。全局答案则由右递归给出13。

自测：为何算法仍要计算一个明显为负的跨区候选？

三类划分的正确性要求每类都使用同一合法规格。跨区必须同时用到两侧，即便结果负也如实返回；最后再与左右递归值比较。擅自令跨区一侧为空，相当于更改类别，容易在全负或端点恢复时返回不存在的方案。

时间与常见错误

每层递归的两个扫描共 $O(r-l+1)$ ，所以与归并排序同样得到 $O(n\log n)$ 。若用数组区间下标递归，扫描只需常数局部变量，递归栈为 $O(\log n)$ 。

不能把“左右各自的任意最佳子数组”直接拼起来，它们可能隔着空隙；必须用贴住中点的后缀和前缀。跨区候选左右两侧都必须非空，即便其中一侧的最佳和为负，也不能在跨区候选里把它删掉；不跨区的情况已经由另两个候选负责。

Problem 5：将二次幂规模的矩阵乘法扩展到任意规模（题目 p.1；答案 p.2）

题意概述。 已有适用于边长为二次幂的快速方阵乘法，课堂以 $O(n^{2.81})$ 表述其代价。说明任意正整数边长也能保持该阶。

补到最近的二次幂，不能任意补得很大

取不小于 $n$ 的最小二次幂 $m$ 。如果 $n$ 本来就是二次幂，取 $m=n$ ；否则不断翻倍找到它。对所有正整数 $n$ ，有 $n\le m<2n$ 。

在两个矩阵的末尾添加零行和零列，将它们变成 $m\times m$ 。计算扩展矩阵乘积后，取左上角 $n\times n$ 块。

为什么补零不改变需要的结果

设扩展后的两个矩阵为 $A',B'$ 。对所需范围内的 $i,j\le n$ ，矩阵乘法定义给出

\begin{aligned} (A'B')_{ij} &=\sum_{k=1}^{m}A'_{ik}B'_{kj}\\ &=\sum_{k=1}^{n}A_{ik}B_{kj}+\sum_{k=n+1}^{m}0\cdot0\\ &=(AB)_{ij}. \end{aligned}

所以不是“补零看起来无害”，而是新增项在每个所需输出位置都确实为零。补零不要求原元素为正；负数也满足同一等式。

数字例子（本解析自取）

取 $n=3$ ，补成 $m=4$ 。令 A 的三行是 [1,2,3]、[4,5,6]、[7,8,9]，令 B 为三阶单位矩阵。补零后的 B 的对角线为 1、1、1、0，其余位置为零。

例如扩展乘积的第 2 行第 3 列是 $4\cdot0+5\cdot0+6\cdot1+0\cdot0=6$ ，与原乘积相同；第 4 行和第 4 列全为零。裁掉它们就恢复 $AB=A$ 。

复杂度需要把准备工作也算进去

用 $p=\log_2 7\approx2.8074$ 表示 Strassen 指数。由 $m<2n$ ，有

O(m^p)\subseteq O((2n)^p)=O(2^p n^p)=O(n^p).

$p$ 为常数，所以 $2^p$ 也是常数。分配和填充扩展矩阵花 $O(m^2)=O(n^2)$ ；取出答案至多 $O(n^2)$ 。因为 $p>2$ ，这些工作不会超过主项，整体仍是 $O(n^p)$ ，从而也满足题目写的 $O(n^{2.81})$ 。

易错点。 不能往下取二次幂，会丢数据；不能把矩阵补到 $n^2$ 边长，会放大时间阶；必须同时给两个输入补行与列。这里默认算术操作为常数成本，不另外讨论大整数位运算复杂度。

本讲核心考点

Q1：有序数组双指针的总移动次数，题目 p.1。
Q2：递归同时返回计数与排序结果，把合并降到线性，题目 p.1。
Q3：x 分治消去一个维度，y 扫描计数；同 y 时先左后右，题目 p.1，L02 p.14–16。
Q4：连续子数组的三类位置与最大后缀、前缀的组合，题目 p.1。
Q5：补零正确性，以及扩展规模小于两倍时保持渐近阶，题目 p.1。

以上是练习覆盖点；本次没有据此预测考试题目。

来源与证据

官方题目，p.1；官方答案，p.1–2。下载核验日期：2026-09-30。
Q3 定义补核：L02 课件（本地课件） p.14–16，仅使用文字定义，未借用图中坐标。
2026-09-30 核验时官网可见的 Regular Exercises List 2；源 PDF 未注明学期，不补猜原始学期。
本文补充了可执行的步骤、循环不变量、等值处理、端点恢复和完整数值演算。
考试证据：本次仅核对官方练习与答案，未据此断言考试范围。

i	新加入 A[i]	当前后缀和 s	当前最大后缀和
8	18	18	18
7	-23	-5	18
6	-16	-21	18
5	-3	-24	18
4	20	-4	18
3	-25	-29	18
2	-3	-32	18
1	13	-19	18

i	新加入 A[i]	当前后缀和 s	当前最大后缀和
8	18	18	18
7	-23	-5	18
6	-16	-21	18
5	-3	-24	18
4	20	-4	18
3	-25	-29	18
2	-3	-32	18
1	13	-19	18

i	新加入 A[i]	当前后缀和 s	当前最大后缀和
8	18	18	18
7	-23	-5	18
6	-16	-21	18
5	-3	-24	18
4	20	-4	18
3	-25	-29	18
2	-3	-32	18
1	13	-19	18