分治

切成兩半，各自解決，再合起來。 · ⏱ 約 30 分鐘

你會學到三件事

1. 分治的三步：分、解、合
2. 為什麼它是 O(n log n)
3. vector<int>& 傳的是參考，不複製

開始之前

二分搜（第 3 課）每次丟掉一半。

分治每次處理兩半，而那正是它比較慢（log n vs n log n）而能做更多的原因。

🟢 先把編輯器打開，跟著下面一起做：跟著做

一、三步

照著打上這一段，三步都在裡面：

1int msum(vector<int>& a, int lo, int hi) {2    if (lo == hi) return a[lo];          // ① 小到不能再分 → 直接回答3    int mid = (lo + hi) / 2;             // ② 分4    int left = msum(a, lo, mid);5    int right = msum(a, mid + 1, hi);6    return left + right;                 // ③ 合7}

⚠️ lo == hi 那個出口不能少（C++ 入門第 16 課的規矩：遞迴要有出口）。

二、vector<int>& 的那個 &

那個 & 在這裡是這個意思：

int msum(vector<int>& a, int lo, int hi)
              ↑
        「傳參考」——不複製

沒有那個 & 的話，每次遞迴呼叫都會把整個 vector 複製一份。

n = 10⁵、遞迴 log n 層、每層 n 次呼叫，複製的成本會遠遠超過演算法本身。

競賽裡容器參數幾乎一律加 &。 不改它的話再加個 const：const vector<int>& a。

（這和 C 銜接課 C 銜接第 5 課「結構參數傳指標」是同一件事的兩種寫法。）

三、為什麼是 O(n log n)

        n              ← 一層合起來的工作量是 n
      /   \
   n/2    n/2          ← 這一層加起來也是 n
   / \    / \
 n/4 n/4 n/4 n/4       ← 還是 n
   ...
共 log n 層

每一層的總工作量都是 n，而有 log n 層 → O(n log n)。

⚠️ 這個算法只在「合併的成本是 O(那一段的長度)」時成立。 合併要 O(n²) 的話整體會是 O(n²)。

四、分治能做什麼

⚠️ 幾乎每一題的難處都在「跨越中間」那部分： 左右兩半是遞迴幫你解的，而中間那些只有你會處理。

完成的樣子

1#include <iostream>2#include <vector>3using namespace std;4int msum(vector<int>& a, int lo, int hi) {5    if (lo == hi) return a[lo];6    int mid = (lo + hi) / 2;7    int left = msum(a, lo, mid);8    int right = msum(a, mid + 1, hi);9    return left + right;10}11 12int main() {13    vector<int> a = {1, 2, 3, 4};14    cout << msum(a, 0, 3) << endl;15    return 0;16}

換你了

把 return left + right; 改成 return max(left, right);—— 它變成「找最大值」。

分和解都沒變，只有「合」變了。那就是分治的形狀。

積木盤上那顆寫著「較大值 … …」（max）——它旁邊還有一顆「較小值」。

到編輯器做這一題：練習：把「合」換成 max，它就變成找最大值

做一個

不准用 sort。自己寫 mergeSort，把 5 1 9 3 7 排好印出來（用空白隔開）。

🔴 三步：分成兩半、各自解、再把兩串已排好的合起來。 而「合」那一步是整題唯一真正在做事的地方，它是兩個指標往前走。

到編輯器做這一題：做一個：自己寫一次合併排序

這一課你做了什麼

• 你寫了一個分、解、合三步的遞迴
• 你用 & 避免了每次呼叫複製整個容器
• 你知道 O(n log n) 是「每層 n、共 log n 層」

如果卡住了