分治：拆开独立子问题，再合并局部答案｜算法讲义

解决什么问题#

分治（Divide and Conquer）把一个规模较大的问题拆成若干结构相同、规模更小且相互独立的子问题，递归解决它们，再把局部答案合并为原问题答案。

它适合以下结构：

输入可以按位置或空间区域自然拆开；
子问题与原问题同型，能使用同一段递归逻辑；
子问题之间基本独立；
合并局部答案比直接解决原问题更容易。

归并排序、快速排序、最近点对、逆序对统计、快速幂和许多计算几何算法都体现了分治思想。

核心思想与不变量#

一个分治算法通常分成三步：

Divide：将当前问题拆成更小的子问题；
Conquer：递归求解每个子问题；
Combine：利用子问题答案构造当前问题答案。

归并排序将半开区间 [left, right) 从中点拆成两半。两个递归调用返回后，维持关键不变量：

[left, middle) 与 [middle, right) 各自已经有序；合并过程中，临时数组 [left, write) 始终包含两段中尚未处理元素里最小的若干个，并且自身有序。

每次比较两段的首个剩余元素，把较小者写入临时数组。因为每段内部有序，未被选择的其他元素不可能更小。最终复制回原数组即可得到整个区间有序。

复杂度#

归并排序的递推式是：

$T(n)=2T(n/2)+O(n).$

递归树共有 $O(\log n)$ 层，每层合并的总元素数都是 $n$ ，因此时间复杂度为 $O(n\log n)$ 。临时缓冲区占 $O(n)$ ，递归栈占 $O(\log n)$ 。

更一般地，若递推式为 $T(n)=aT(n/b)+f(n)$ ，可以通过递归树或主定理比较叶子规模 $n^{\log_b a}$ 与合并成本 $f(n)$ 。

C++17 模板一：递归分治框架（稳定归并排序）#

归并排序完整对应递归分治框架：基例处理长度不超过 1 的区间，两个递归调用分别完成 Conquer，随后线性 Combine。模板只申请一次缓冲区并在所有递归层复用；相等时优先取左半元素，因此排序是稳定的。

#include <cstddef>
#include <iostream>
#include <vector>

void merge_sort_impl(std::vector<int>& values, std::vector<int>& buffer,
                     std::size_t left, std::size_t right) {
  if (right - left <= 1) {
    return;
  }

  const std::size_t middle = left + (right - left) / 2;
  merge_sort_impl(values, buffer, left, middle);
  merge_sort_impl(values, buffer, middle, right);

  std::size_t first = left;
  std::size_t second = middle;
  std::size_t write = left;

  while (first < middle && second < right) {
    if (values[first] <= values[second]) {
      buffer[write++] = values[first++];
    } else {
      buffer[write++] = values[second++];
    }
  }
  while (first < middle) {
    buffer[write++] = values[first++];
  }
  while (second < right) {
    buffer[write++] = values[second++];
  }

  for (std::size_t index = left; index < right; ++index) {
    values[index] = buffer[index];
  }
}

void merge_sort(std::vector<int>& values) {
  std::vector<int> buffer(values.size());
  merge_sort_impl(values, buffer, 0, values.size());
}

int main() {
  std::vector<int> values{7, 2, 5, 3, 1};
  merge_sort(values);

  for (int value : values) {
    std::cout << value << ' ';
  }
  std::cout << '\n';
}

C++17 模板二：递归模快速幂#

快速幂展示了“只递归求解一个子问题，再复用其答案”的分治形式。设 $k=\lfloor n/2\rfloor$ ，先求一次 $a^k$ ：指数为偶数时平方即可，指数为奇数时再乘一个 $a$ 。模意义下每次乘法后立刻取模，就不需要保存指数级增长的完整幂。

下面使用标准 C++17 整数，并把模数限制为不超过 $3\times10^9$ ，从而保证两个模内数相乘不会超过 long long。更大的模数需要额外的防溢出乘法。

#include <cstdint>
#include <iostream>
#include <stdexcept>

using i64 = long long;
using u64 = std::uint64_t;

i64 modular_power(i64 base, u64 exponent, i64 modulus) {
  if (modulus <= 0 || modulus > 3'000'000'000LL) {
    throw std::invalid_argument("require 1 <= modulus <= 3e9");
  }
  base %= modulus;
  if (base < 0) {
    base += modulus;
  }
  if (exponent == 0) {
    return 1 % modulus;
  }

  const i64 half = modular_power(base, exponent / 2, modulus);
  const i64 square = (half * half) % modulus;
  return exponent % 2 == 0 ? square : (square * base) % modulus;
}

int main() {
  std::cout << "3^13 mod 1e9+7 = "
            << modular_power(3, 13, 1'000'000'007LL) << '\n';
}

递推式为 $T(k)=T(k/2)+O(1)$ ，所以时间和递归深度都是 $O(\log k)$ 。最常见的错误是递归计算两次 power(base, exponent / 2)，这会把线性数量的重复子问题重新引入；半次幂必须只计算一次并复用。

C++17 模板三：分治最大子段和#

最大子段可能完全在左半、完全在右半，也可能跨越中点。为了用 $O(1)$ 时间合并，递归结果同时维护区间总和、最大前缀和、最大后缀和与最大子段和：

\text{best}=\max(\text{left.best},\text{right.best}, \text{left.suffix}+\text{right.prefix}).

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

using i64 = long long;

struct SegmentSummary {
  i64 total;
  i64 best_prefix;
  i64 best_suffix;
  i64 best_subarray;
};

SegmentSummary combine(const SegmentSummary& left,
                       const SegmentSummary& right) {
  return {
      left.total + right.total,
      std::max(left.best_prefix, left.total + right.best_prefix),
      std::max(right.best_suffix, right.total + left.best_suffix),
      std::max({left.best_subarray, right.best_subarray,
                left.best_suffix + right.best_prefix})};
}

SegmentSummary maximum_subarray_impl(const std::vector<i64>& values,
                                     std::size_t left, std::size_t right) {
  if (right - left == 1) {
    return {values[left], values[left], values[left], values[left]};
  }
  const std::size_t middle = left + (right - left) / 2;
  return combine(maximum_subarray_impl(values, left, middle),
                 maximum_subarray_impl(values, middle, right));
}

i64 maximum_subarray_sum(const std::vector<i64>& values) {
  if (values.empty()) {
    throw std::invalid_argument("maximum subarray requires a nonempty array");
  }
  return maximum_subarray_impl(values, 0, values.size()).best_subarray;
}

int main() {
  const std::vector<i64> values{-2, 1, -3, 4, -1, 2, 1, -5, 4};
  std::cout << "maximum subarray sum = "
            << maximum_subarray_sum(values) << '\n';  // 6
}

递归树有 $O(n)$ 个节点，每个节点只做常数次合并，因此时间为 $O(n)$ 、递归栈为 $O(\log n)$ 。它与线性的 Kadane 算法复杂度相同，但更直接展示了“跨中点答案”应如何进入 Combine。

延伸阅读：最近点对的分治写法#

平面最近点对先按 $x$ 坐标排序，在中点两侧分别求最短距离 $d$ 。跨越中线的更优点对，其两个点都必须落在距中线小于 $d$ 的条带中；将条带按 $y$ 排序后，只需继续比较纵向距离仍小于 $d$ 的候选。

下面是结构清晰的 $O(n\log^2 n)$ 写法：每层单独排序条带。进一步让递归区间始终按 $y$ 有序，可以把它优化到 $O(n\log n)$ 。

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <limits>
#include <stdexcept>
#include <vector>

struct Point {
  double x;
  double y;
};

double squared_distance(const Point& first, const Point& second) {
  const double dx = first.x - second.x;
  const double dy = first.y - second.y;
  return dx * dx + dy * dy;
}

double closest_pair_impl(const std::vector<Point>& points,
                         std::size_t left, std::size_t right) {
  const std::size_t count = right - left;
  if (count <= 3) {
    double best = std::numeric_limits<double>::infinity();
    for (std::size_t i = left; i < right; ++i) {
      for (std::size_t j = i + 1; j < right; ++j) {
        best = std::min(best, squared_distance(points[i], points[j]));
      }
    }
    return best;
  }

  const std::size_t middle = left + count / 2;
  const double middle_x = points[middle].x;
  double best = std::min(closest_pair_impl(points, left, middle),
                         closest_pair_impl(points, middle, right));

  std::vector<Point> strip;
  strip.reserve(count);
  for (std::size_t i = left; i < right; ++i) {
    const double dx = points[i].x - middle_x;
    if (dx * dx < best) {
      strip.push_back(points[i]);
    }
  }
  std::sort(strip.begin(), strip.end(),
            [](const Point& first, const Point& second) {
              return first.y < second.y;
            });

  for (std::size_t i = 0; i < strip.size(); ++i) {
    for (std::size_t j = i + 1; j < strip.size(); ++j) {
      const double dy = strip[j].y - strip[i].y;
      if (dy * dy >= best) {
        break;
      }
      best = std::min(best, squared_distance(strip[i], strip[j]));
    }
  }
  return best;
}

double closest_pair_distance(std::vector<Point> points) {
  if (points.size() < 2) {
    throw std::invalid_argument("closest pair requires at least two points");
  }
  std::sort(points.begin(), points.end(),
            [](const Point& first, const Point& second) {
              if (first.x != second.x) {
                return first.x < second.x;
              }
              return first.y < second.y;
            });
  return std::sqrt(closest_pair_impl(points, 0, points.size()));
}

int main() {
  const std::vector<Point> points{{0.0, 0.0}, {5.0, 5.0},
                                  {3.0, 4.0}, {3.5, 4.0}};
  std::cout << "closest distance = " << closest_pair_distance(points)
            << '\n';  // 0.5
}

条带内不能退化成不加限制的两两比较；内层循环必须在纵向距离已经不可能改进 best 时停止。标准几何结论还能说明每个点只需检查之后常数个点。

示例推演#

对 [7, 2, 5, 3, 1]：

拆成 [7, 2] 与 [5, 3, 1]；
左侧递归排序为 [2, 7]；
右侧继续拆分并排序为 [1, 3, 5]；
合并时依次比较两段首元素，写出 1, 2, 3, 5, 7。

递归正确性可以用区间长度归纳：长度 0 或 1 显然有序；假设更短区间都能正确排序，则当前两半递归后有序，而线性合并会产生整个区间的有序排列。

易错点#

没有明确区间是 [left, right) 还是 [left, right]，导致中点重复、漏元素或无限递归。
缺少规模为 0 或 1 的递归出口。
两半排序后直接拼接，忽略了跨越中点的次序；分治的关键往往正是 Combine。
每层递归都重新申请大数组，产生不必要的分配开销；可以像模板一样复用缓冲区。
合并完成后忘记把临时结果复制回原数组。
子问题大量重叠时仍使用纯分治，重复计算严重；这种结构通常更适合记忆化或动态规划。
只分析递归调用而漏掉每层合并的成本。