首頁 教學 演算法

# 前言

分治法就是一直把問題切兩半然後再合併。核心公式只有三步：分解（divide）→ 解決（conquer）→ 合併（combine）。跟 1-2 遞迴 的關係很直接 —— 分治法幾乎都是靠遞迴實現的，差別在於分治法特別強調「切一半」跟「合併兩邊答案」這兩個步驟。

# 熱身：找最大值

隨機給 10 個數字然後找最大值。題目就是這麼短，用分治法的想法是：把陣列切一半，兩邊各自遞迴找出最大值，再比較兩邊的最大值哪個比較大。

// [自己的解法]
#include <bits/stdc++.h>
using namespace std;
#define N 10
int search_max(vector<int>& _v,int l,int r){// 左閉右開
    if(l+1==r) return _v[l];// 終止條件
    int mid=(l+r)>>1;// 分割
    int a=search_max(_v,l,mid);// 兩邊各自遞迴
    int b=search_max(_v,mid,r);
    if(a>b) return a;// 比較兩邊的最大值
    else return b;
}
int main(){
    vector<int> v;
    for(int i=0,temp;i<N;i++){
        temp=rand()%N;
        cout<<temp<<" ";
        v.push_back(temp);
    }
    cout<<"\n"<<search_max(v,0,N);
}

我程式的函式採用的是左閉右開區間，可以發現用這種寫法程式內呼叫函式都不需要 +1 或者 -1 看的就非常的清爽， (l+r)>>1 就是找終點的意思， >>1 就是除以二的意思用位元運算會比用 / （除號）還要快。觀察程式內分治的感覺再去看圖對應的 idx (索引值)，分治法就是這樣的感覺。

分治法的複雜度分析通常用遞迴關係式表達：把問題切成兩半，各花 T(n/2) ，合併花 O(f(n)) ，整體是 T(n) = 2T(n/2) + O(f(n)) 。這題合併只是比較兩個數， f(n)=O(1) ，根據主定理（master theorem），總複雜度是 O(n) —— 跟直接掃一遍陣列找最大值一樣快，但這個簡單例子的價值在於展示分治法的骨架，之後的題目會看到合併步驟做更多事情，複雜度也會不一樣。

# 合併排序（Merge Sort）

[l,r) 這裡的 "[" 代表包含 ")" 代表不包含，所以是左閉右開區間。

// [自己的解法]
#include<bits/stdc++.h>
using namespace std;
void merge_sort(vector<int>& _v,int l,int r){//[l,r)
    if(l+1==r) return;
    int mid=(l+r)>>1;
    merge_sort(_v,l,mid);
    merge_sort(_v,mid,r);
    vector<int> temp;
    int i=l,j=mid;
    while(i<mid){
        while(j<r && _v[j]<_v[i]){// 這邊要注意一下
            temp.push_back(_v[j]);
            j++;//_v [j]>_v [mid-1] 那就不需要再放入 temp
        }
        temp.push_back(_v[i]);
        i++;
    }
    for(auto &u:temp){
        _v[l]=u;
        l++;
    }
}
int main(){
    vector<int> v;
    int n=10;// 幾筆測資
    for(int i=0,temp;i<n;i++){
        temp=rand()%10;// 亂數大小
        v.push_back(temp);
    }
    merge_sort(v,0,v.size());
    for(auto u:v) cout<<u<<" ";
}

這裡示範了合併排序的寫法，也有人稱作歸併排序，建議自己寫寫看這個排序，因為分治法的題目很多都像是這種感覺。

合併排序的複雜度是 T(n) = 2T(n/2) + O(n) （合併兩個已排序陣列需要 O(n) ），根據主定理解出來是 O(n log n) —— 這也是為什麼 sort() 這類通用排序函式的複雜度基準都是 O(n log n) 。

注意這裡合併時 while 迴圈的細節： while(j<r && _v[j]<_v[i]) ，這裡用嚴格小於（ < ）而不是 <= ，這個選擇會影響排序的穩定性（stability）—— 相同的值會不會維持原本的相對順序。如果需要穩定排序，要確保相等時優先取左邊（前段）的元素。

# P-5-4. 反序數量（APCS）

題目來源：APCS 201806 ｜ AP325 P-5-4

考慮一個數列 A [1:n]。如果 A 中兩個數字 A [i] 和 A [j] 滿足 i<j 且 A[i]>A[j] ，也就是在前面的比較大，則我們說 (a [i],a [j]) 是一個反序對 (inversion)。定義 W (A) 為數列 A 中反序對數量。例如，在數列 A=(3,1,9,8,9,2) 中，一共有 (3,1)、(3,2)、(9,8)、(9,2)、(8,2)、(9,2) 一共 6 個反序對，所以 W (A)=6。

請注意到序列中有兩個 9 都在 2 之前，因此有兩個 (9,2) 反序對，也就是說，不同位置的反序對都要計算，不管兩對的內容是否一樣。請撰寫一個程式，計算一個數列 A 的反序數量 W (A)。

輸入格式：第一行是一個正整數 n，代表數列長度，第二行有 n 個非負整數，是依序數列內容，數字間以空白隔開。n 不超過 1e5，數列內容不超過 1e6。

輸出：輸出反序對數量。

範例輸入 範例輸出
6
3 1 9 8 9 2		 6

# 解題思路

這一題仔細觀察會發現好像跟合併排序有點像，覺得不像沒關西看完程式碼就會覺得像了。

這一題用合併排序的時候因為左邊跟右邊都是排好續的：

1 2 3 4 5 6 | 2 3 4 5 6

分成兩邊，然後由小到大排序要判斷哪個值比較小，所以一開始 1 比 2 小因為右端還沒放入任何東西所以答案不會增加。

   3 4 5 |    3 4 5 6
1 2   2

下面的表格是現在排好序的數組，上面的表格空的代表已經變放到下面的表格，放入 3 的時候因為右端已經放入了一個值 (值為 2)，所以這時答案要加上 1，而這個 1 就是右端指向的 idx 減掉 mid。

答案增加的情況，上方表格是放入哪個值，下面則是放入那個值答案加多少，所以答案是 6。

// [自己的解法]
#include <bits/stdc++.h>
using namespace std;
long long ans=0;
void merge_sort(vector<int>& _v,int l,int r){
    if(l+1==r) return;
    int mid=(l+r)>>1;
    merge_sort(_v,l,mid);
    merge_sort(_v,mid,r);
    int i=l,j=mid;
    vector<int> temp;
    while(i<mid){
        while(j<r && _v[j]<_v[i]){
            temp.push_back(_v[j]);
            j++;
        }
        temp.push_back(_v[i]);
        i++;
        ans+=(j-mid);// 右邊比左邊小的數量
    }// 因為兩邊都排好序所以左邊放進來 temp 的時候直接計算剛剛有幾個右端放進來
    for(auto u:temp)
        _v[l++]=u;
}
int main(){
    int n;
    vector<int> v;
    cin>>n;
    for(int i=0,temp;i<n;i++){
        cin>>temp;
        v.push_back(temp);
    }
    merge_sort(v,0,n);
    cout<<ans;
}

可以發現我函式名稱一直用 merge_sort 因為函式內容大概都圍繞著那個感覺在變化，不過分治法也有一些比較難的題目寫起來就沒辦法那麼直覺了。

這題的關鍵洞察是：在合併排序的過程中，「合併」這個動作本身就會自然地暴露出反序對。因為左右兩半各自已經排好序，當右邊的元素 _v[j] 比左邊的 _v[i] 還小、需要提前放進 temp 時，代表 _v[i] 跟這個以及它之後所有還沒放進 temp 的右邊元素都構成反序對 —— 這就是 ans += (j - mid) 的意思。

這種「藉助分治法的合併過程，順便算出額外資訊」的手法非常實用，之後遇到需要計算「逆序對」「區間內特殊配對數」的題目，都可以考慮往這個方向想。

# 低地距離（APCS）

輸入一個長度為 2n 的陣列，其中 1~n 的每個數字都剛好各 2 次。i 的低窪值的定義是兩個數值為 i 的位置中間，有幾個小於 i 的數字。以 [3,1,2,1,3,2] 為例，1 的低窪值為 0，2 的低窪值值為 1，3 的低窪值為 3。請對於每個 1~n 的數字都求其低窪值（兩個相同的數字之間有幾個數字比它小），輸出低窪值的總和，答案可能會超過 C++ int 的上限。

輸入說明：第一行有一個正整數 n，第二行有 2n 個正整數，以空格分隔，保證 1~n 每個數字都恰好出現兩次。

輸出說明：輸出 1~n 每個數字的低窪值總和。

範例輸入 #1 範例輸出 #1
3
3 1 2 1 3 2		 4

# 解題思路

這一題有沒有覺得跟剛剛那題很像，覺得不像沒關西，看完圖之後就覺得像了。

3  1  2  1  3  2
3  1  2  1  3  2
3  1  2  1  3  2
3  1  2  1  3  2

有沒有看出什麼規律，第一行是原本的數組，第二行則是判斷 1 的低地距離，因為沒有所以跟第一行一樣，第三行就不一樣了，前面比較淺的部分是判斷前面的 2 的反序數有多少個減掉後面 2 的反序數就是低地距離，第四行就更清楚了第一個 3 的反序數有 1,2,1,2，有四個減掉後面的 3 的反序數也就是只剩下一個的 2，這樣答案就出來了。

這一題跟「反序數量」的關聯是：每個數字的低窪值，其實就是「這個數字第一次出現時的反序數」減掉「第二次出現時的反序數」。這是因為兩次出現之間比它小的數字，一定會在「第一次出現」時被算進反序對（因為它們在前面且比它大…… 不對，這裡要更精確一點）：關鍵在於利用同一個數字出現兩次這件事，讓合併排序在計算反序對時，能夠分別追蹤「第一次出現的貢獻」跟「第二次出現的貢獻」，兩者相減就是低窪值。

// [自己的解法]
#include<bits/stdc++.h>
using namespace std;
#define N 100005
long long ans=0;
void merge_sort(vector<pair<int,bool>>& _v,int l,int r){
    if(l+1 == r) return;
    int mid=(l+r)>>1;
    merge_sort(_v,l,mid);
    merge_sort(_v,mid,r);
    int i=l,j=mid;
    vector<pair<int,bool>> temp;
    while(i<mid){
        while(j<r && _v[j].first<_v[i].first){
            temp.push_back({_v[j].first,_v[j].second});
            j++;
        }
        if(_v[i].second) ans-=j-mid;// 第二個數字反序數要減掉
        else ans+=j-mid;// 第一個數字的反序數要加上
        temp.push_back({_v[i].first,_v[i].second});
        i++;
    }
    for(auto u:temp)
        _v[l++]={u.first,u.second};
}
int main(){
    vector<pair<int,bool>> v;
    bool check[N]={0};
    int n;
    cin>>n;
    for(int i=0,temp;i<2*n;i++){
        cin>>temp;
        v.push_back({temp,check[temp]});
        check[temp]=!check[temp];
    }
    merge_sort(v,0,2*n);
    cout<<ans;
}

程式裡用一個 bool 標記每個數字是「第一次出現」還是「第二次出現」，然後在合併排序的過程中，第一次出現時把反序數加進答案，第二次出現時把反序數減掉 —— 兩次出現之間比它小的數字，恰好會被「加一次、減一次」抵消成只算一次，正好等於低窪值的定義。

這題展示了分治法一個很重要的延伸能力：合併步驟不只可以合併「排序後的資料」，還可以順便累積任何跟順序相關的統計量，只要想清楚合併當下能得到什麼資訊。

# 最大連續子陣列（分治）

題目來源：AP325

有一個整數陣列 A [0:n-1]，請計算 A 的連續子陣列的最大可能總和，空陣列的和以 0 計算。

1-5 貪心演算法 已經用「維護最小前綴和」的貪心角度解過這題，這裡用分治法的角度再解一次，體會同一題可以有不同的思路。

# 解題思路

把陣列切成左右兩半，最大子陣列可能存在於三個地方：完全在左半、完全在右半、或是跨越兩半。前兩種直接遞迴求解即可，第三種需要額外處理：跨越中點的最大子陣列，一定是「左半部以中點結尾的最大後綴和」加上「右半部以中點 + 1 開頭的最大前綴和」。

// [來源：AP325]
#include <bits/stdc++.h>
#define N 200020
using namespace std;
typedef long long LL;
LL psum[N]; // prefix-sum
struct Rdata {
    // max-sum, max prefix-sum, max suffix-sum
    LL msum, lmax, rmax;
};
//return max in [le, ri), 左閉右開
Rdata subarr(LL a[], int le, int ri) {
    if (le+1 == ri) {
        LL t = max(a[le],(LL)0);
        return {t, t, t};
    }
    int mid=(le+ri)/2;
    // recursively solve left and right parts
    Rdata left=subarr(a, le, mid), right=subarr(a, mid, ri);
    Rdata my;
    my.lmax=max(left.lmax, psum[mid-1]-psum[le-1]+right.lmax);
    // 尋找最大前綴和在左邊還是跨越兩邊
    my.rmax=max(right.rmax, psum[ri-1]-psum[mid-1]+left.rmax);
    // 尋找最大後綴和在右邊還是跨越兩邊
    my.msum=max(left.msum, right.msum);
    // find largest sum cross middle
    my.msum=max(my.msum, left.rmax+right.lmax);
    return my;
}
int main() {
    LL n, a[N];
    cin>>n;
    a[0]=0, psum[0]=0;
    for (int i=1; i<=n; i++) {
        cin>>a[i];
        psum[i]=psum[i-1]+a[i];
    }
    cout<<subarr(a, 1, n+1).msum<<" "<<subarr(a, 1, n+1).lmax
<<" "<<subarr(a, 1, n+1).rmax;
    return 0;
}
最後輸出的地方我把最大前綴和跟最大後綴和都輸出了，這樣可以更清楚程式是如何前綴和跟後綴和在優化程式。我們來講一下最大區間可能在甚麼地方，最大區間可能存在於程式中分治法一刀切下去的左端前綴和或是右端後綴和或是穿越這兩端。


my.lmax=max(left.lmax, psum[mid-1]-psum[le-1]+right.lmax);
my.rmax=max(right.rmax, psum[ri-1]-psum[mid-1]+left.rmax);
這兩行就是關鍵的地方，後方的部分就是在比較兩種穿越兩端的可能。比較黑的部分就是前面用 psum 計算出來的地方，而比較淺的地方就是直接用  right.lmax  跟  left.rmax  得出來的地方，這裡是我當初程式碼想最久的地方，不過搭配圖，我相信好理解不少。


my.msum=max(left.msum, right.msum);
my.msum=max(my.msum, left.rmax+right.lmax);
再來是這兩行，上面那一行是在判斷說最大區間是在左邊還是右邊，下面那一行是在判斷說最大區間是穿越兩端。


換句話說其實分治法就是分成兩邊各自去找答案再用兩邊得出來的結果去判斷，因為會一直遞迴下去所以最後合併答案就會出來，要注意的就是終止條件及跨越兩邊的答案合併時要注意。


這題的複雜度是  T(n) = 2T(n/2) + O(1) （合併只需要常數時間比較），解出來是  O(n) —— 跟貪心解一樣快，但分治法的思路更容易推廣到二維（子矩陣最大和）等更複雜的變形。




# 小結


分治法的核心公式：分解 → 各自遞迴解決 → 合併答案。這章的四個例題展示了合併步驟可以做的事情越來越豐富：






題目
合併步驟做的事






找最大值
比較兩邊的最大值




合併排序
把兩個已排序陣列合併成一個




反序數量
合併的同時累計「跨越兩邊」的反序對數




低地距離
合併的同時累計「第一次／第二次出現」的反序數差




最大連續子陣列
合併時額外考慮「跨越中點」的解






判斷一個問題能不能用分治法解，關鍵是看：這個問題切成兩半之後，能不能只靠「左邊的答案」「右邊的答案」外加一些額外資訊，快速合併出整體的答案。如果合併步驟的複雜度夠低（通常要求  O(n)  或更低），分治法就能把問題複雜度壓到  O(n log n) 。


下一章要講動態規劃，這是全系列篇幅最長、也是變化最多的單元 —— 它跟分治法一樣是把大問題拆成小問題，但差別在於動態規劃刻意利用子問題之間的重疊性來避免重複計算。


# 練習題


（之後補上）


      

          
          
          
          
      

  


   


    

  
    
      
    
    更新於
    
  
  
      
        
      
      閱讀次數
      
      次