分治

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

你會學到三件事

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

開始之前

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

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

一、三步

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

⚠️ 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²)。

四、分治能做什麼

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

完成的樣子

int msum(vector<int>& a, int lo, int hi) {
    if (lo == hi) return a[lo];
    int mid = (lo + hi) / 2;
    int left = msum(a, lo, mid);
    int right = msum(a, mid + 1, hi);
    return left + right;
}

int main() {
    vector<int> a = {1, 2, 3, 4};
    cout << msum(a, 0, 3) << endl;
    return 0;
}

換你了

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

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

這一課你做了什麼

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

如果卡住了