---
title: 分治
tags: 7th 教學
---
# 分治
#### Author: PixelCat
## 概要
1. 分治的架構
3. 分治複雜度分析
2.1. 遞迴樹
2.2. 主定理
4. 分治與排序
3.1. 暴力作法 (Bubble Sort, Insertion Sort)
3.2. 歸併排序 Merge Sort
3.3. 快速排序 Quick Sort
3.4. 暴力與分治混合？
3.5. 關於排序的題外話
5. 分治例題
4.1. TIOJ1080 逆序數對
4.2. ZJd784 最大連續元素和
4.3. 太陽軍團
6. 更多習題
7. 應用與延伸
8. 結語
## 分治的架構
分治與遞迴有緊密的關係。許多時候，一個問題不好正面解決，但我們可以找到一個方法把大問題切割成一些小一點的問題，逐步簡化，最後用小問題的結果合併成大問題的解答。因此，分治又稱為「Divide and Conquer」，可以分為三個部分
1. 分 Divide：分割大問題，變成一些小的子問題
2. 遞迴 Recurse：遞迴解決小問題，直到答案變得顯然
3. 治 Conquer：合併小問題的答案，成為大問題的解答
以一個鋪磚塊的問題為例。
> 給你一個 $2^n\times 2^n$的方格，其中缺了某一格。請問要如何用很多個L型的磚塊鋪滿方格，只留下缺失的格子?
> 你可以利用各種方法發現 $\left(2^n\right)^2$ 可以被三整除。
例如在這個例子中，$n=3$，缺失的格子在 $(3,4)$ 的位置（以紅色格子表示），以下是一種可能的答案。
<center><img src="https://i.imgur.com/PZgq0LA.png" width="300"></center><br>
前面說過，進行分治需要先分割問題，也就是找到大問題裡面包含的小問題。假設現在你什麼磚塊都還沒放上去，盤面應該長這樣
<center><img src="https://i.imgur.com/xCXfRaq.png" width="300"></center><br>
經由神秘的通靈，你決定畫兩條線把整個盤面切成四塊，並嘗試分治這四個小問題，這樣你就可以把問題從邊長 $2^n$ 的方格變成只剩邊長 $2^{n-1}$ 的方格要解決。
左上角的子問題和原本題目要求的一模一樣，要將缺一塊的正方形方格填滿，直接遞迴解決就可以了。剩下三塊怎麼辦？經由更多通靈你發現可以放上一塊磚塊
<center><img src="https://i.imgur.com/gEbEc2R.png" width="300"></center><br>
如此一來，你可以把原本的問題切成四個完全相同，但方格邊長少一半的問題
<center><img src="https://i.imgur.com/9wMMEUX.png" width="300"></center><br>
如此這般不斷遞迴，最後終於遞迴到了 $n=1$ 的問題，此時只有四種情況
<center><img src="https://i.imgur.com/iN5F0YA.png" width="300"></center><br>
此時答案很顯然了，這是遞迴的終止條件。於是你利用分治解決了這個問題，可喜可賀！
依照這個方式，以這個例子來說你最後會得到像是上面的那張圖。
<center><img src="https://i.imgur.com/PZgq0LA.png" width="300"></center><br>
## 分治複雜度分析
### 遞迴樹
在上一篇[遞迴](https://hackmd.io/@nehs-iced-7th/r1weYk3UK)裡有提過，對於一個遞迴函數你可以畫出他的遞迴樹，算算函數被呼叫了幾次、每次花了多久時間，加起來就是呼叫函數需要的總時間。同樣的，我們畫出剛剛放磚塊問題的遞迴樹（第三層太大了只畫出一部分）
每次邊長砍一半，從 $2^n$ 開始遞迴 $n$ 層。每次呼叫函數花 $O(1)$ 時間放一塊磚塊，並呼叫四次遞迴。總時間複雜度是
$$
1+4+4^2+\dots+4^n=\dfrac{4^{n+1}-1}{3}=O(4^n)
$$
也就是盤面的總大小。從另一方面來想，每次呼叫函數都放上一塊，呼叫次數就是你需要的磚塊數量，而磚塊數量是跟盤面大小直接相關的。
### 主定理
不過，我們還可以用另一種方式，利用[主定理(Master Theorem)](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))，來分析遞迴（或分治）問題的時間複雜度。主定理說，假如一個遞迴函數可以寫成這個形式
$$
T(n)=aT(\frac{n}{b})+f(n)
$$
也就是大小為 $n$ 的問題可以被切成 $a$ 個小 $b$ 倍的問題，並在 $f(n)$ 的時間內合併，那可以分成[三種情況](https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Generic_form)，計算 $T(n)$ 有多大。
<center><img src="https://i.imgur.com/jCkI5sR.png" width="800"></center>
（圖片來源：維基百科）
以上面的例子來說，首先我們定義 $T(k)$ 是解決盤面邊長為 $k$ 的問題所需的時間，可以寫出遞迴關係
$$
T(k)=4T(\dfrac{k}{2})+1
$$
依據主定理列出的條件，
$$
c_{\text{crit}}=\log_2 4=2\\
f(k)=O(1)=O(n^0), c=0
$$
因此我們知道這個遞迴關係適用第一種情況，因此
$$
T(k)=\Theta(k^{c_{\text{crit}}})=\Theta(k^2)
$$
以 $k=2^n$ 代入，我們得到這個分治演算法的時間複雜度
$$
T(2^n)=\Theta(4^n)
$$
:::spoiler 這裡的Θ是什麼意思？
$\Theta$ 和 $O$ 在這裡都是代表複雜度的符號，都是[Big O Notation的兄弟姊妹](https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations)。簡單來說，
- $O$(Big O)是上界，表示函數不會超過這麼多
- $\Theta$(Big Theta) 是剛剛好，表示函數就是這麼多
- $\Omega$(Big Omega) 是下界，表示函數最多就這麼多
:::
## 分治與排序
排序是一個經典而重要的問題：給你一個長度是 $n$ 的整數序列，元素依序為 $a_1,a_2,\dots,a_n$，你需要重新排列這些元素使得對所有位置 $i$ 都符合 $a_i\leq a_{i+1}$，也就是序列遞增。
其實排序問題也沒有限定要是整數，只是概念都是互通的，這裡就先用整數來說明。
網路上也有[視覺化的排序演算法](https://visualgo.net/en/sorting)，看不懂code的話可以去觀賞觀賞。
### 暴力作法 (Bubble Sort, Insertion Sort)
一個簡單的想法是，我每次從前面看到後面，發現有某個地方發生 $a_i>a_{i+1}$ 就把他們交換，這樣做一輪之後最大的數字就會「浮」到後面，之後可以不用考慮他，做 $n$ 輪之後整個序列就被排序好了。這個方法稱為「泡沫排序(bubble sort)」
:::spoiler 參考程式碼
```cpp=
int a[100010];
// sort a[1] ~ a[n]
void bubbleSort(int n) {
for (int r = n; r > 1; r--) {
for (int i = 1; i < r; i++) {
if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);
}
}
}
```
:::
總複雜度 $O(n^2)$。
另外一種想法是，假如我已經知道 $a_1,\dots a_i$ 排序好了，想要把 $a_{i+1}$ 排進去，我可以把 $a_1,\dots a_i$ 裡面比 $a_{i+1}$ 大的數字都往後移一格，空出來的位置給 $a_{i+1}$ 用，如此依序插入每個數字。這個方法稱為「插入排序(insertion sort)」
:::spoiler 參考程式碼
```cpp=
int b[100010];
// sort b[1] ~ b[n]
void insertionSort(int n) {
for (int r = 2; r <= n; r++) {
int t = b[r];
for (int i = r; i >= 1; i--) {
if (i == 1 || b[i - 1] <= t) {
b[i] = t;
break;
} else {
b[i] = b[i - 1];
}
}
}
}
```
:::
總複雜度也是 $O(n^2)$。
實際上，泡沫排序會比插入排序慢數倍，可以想想為什麼？泡沫排序中的`swap()`裡面確切來說如何實現？
```
n = 20000
Doing bubble sort
Time Elapsed: 0.729 s
Doing insertion sort
Time Elapsed: 0.066 s
```
### 歸併排序 Merge Sort
$O(n^2)$ 顯然滿足不了我們，我們希望能用分治來加速排序的過程。分治要先能切割問題，假設我今天把序列分成前後兩半，那分治的架構應該會是
1. 分：把序列分成前後兩半
2. 遞迴：分別排序前半段和後半段
3. 治：合併兩個排好的序列
1和2簡單，至於3，因為排序過序列的第一項一定是最小的，你可以每次都比較兩個序列的第一個元素，把比較小的拿出來加進答案，最後在 $O(n)$ 的時間合併兩個序列。這樣的作法稱為「歸併排序(merge sort)」。
```cpp=
{ 1, 2, 5, 7 } + { 3, 4, 6, 8 } => { }
{ 2, 5, 7 } + { 3, 4, 6, 8 } => { 1, }
{ 5, 7 } + { 3, 4, 6, 8 } => { 1, 2, }
{ 5, 7 } + { 4, 6, 8 } => { 1, 2, 3, }
{ 5, 7 } + { 6, 8 } => { 1, 2, 3, 4, }
{ 7 } + { 6, 8 } => { 1, 2, 3, 4, 5, }
{ 7 } + { 8 } => { 1, 2, 3, 4, 5, 6, }
{ } + { 8 } => { 1, 2, 3, 4, 5, 6, 7, }
{ } + { } => { 1, 2, 3, 4, 5, 6, 7, 8 }
```
實做大概像這樣，其中`il`和`ir`代表左邊序列和右邊序列的第一項被拔到哪裡了。注意合併的時候要另外放在一個陣列在複製回去，不然會把原本的資料蓋掉。
:::spoiler 參考程式碼
```cpp=
int a[500050];
int tmp[500050];
// sort a[l] ~ a[r]
void mergeSort(int l, int r) {
if (l == r) return;
int m = (l + r) / 2;
mergeSort(l, m);
mergeSort(m + 1, r);
int il = l, ir = m + 1;
for (int i = l; i <= r; i++) {
if (il == m + 1 || (ir <= r && a[ir] < a[il])) {
tmp[i] = a[ir];
ir++;
} else {
tmp[i] = a[il];
il++;
}
}
for (int i = l; i <= r; i++) a[i] = tmp[i];
}
```
:::
下一個問題是，分治一大串，這樣是有比較快嗎？我們把遞迴樹畫出來
<center><img src="https://i.imgur.com/SL15OwP.png" width="600"></center><br>
每一次遞迴呼叫兩次遞迴，直到需要排序的區間長度是1，深度是 $\log n$，每層呼叫的遞迴數量都變兩倍。一次遞迴需要的時間等於要排序的區間長度，隨著遞迴深度增加每次砍一半。需要的總時間是
$$
\sum_{k=1}^{\log n}2^{k-1}\times\frac{n}{2^{k-1}}=n\log n
$$
時間複雜度是 $O(n\log n)$。當然也可以套用主定理來分析
$$
T(n)=2T(\frac{n}{2})+n\\
c_{\text{crit}}=\log_2 2=1\\
f(n)=n=\Theta(n^1\log^0n)
$$
適用第二種情況。
$$
T(n)=\Theta(n\log n)
$$
結果相同。這種「序列砍一半，$O(n)$ 合併」的形式非常常見，只要觀察出分治的關係常常可以在$O(n\log n)$ 解決原本需要 $O(n^2)$ 時間的問題。
### 快速排序 Quick Sort
歸併排序希望能能合併兩個排好的序列，但換一個想法，假如已經滿足「前半段都小於後半段」，是不是就可以不用合併了？於是我們又得到一個分治的結構
1. 分：找一個 $p$，把序列重新排列成「小於等於 $p$」「大於 $p$」兩段
2. 遞迴：分別排序兩段
3. 治：不用合併，序列已經排序好了
此時的 $p$ 如何選擇就很重要了。假如你每次都選到中位數，那你可以每次都把序列從正中間切開，得到跟merge sort一樣的 $O(n\log n)$；但是假如你每次都選到最大值或最小值，複雜度會瞬間退化成 $O(n^2)$。好消息是，這種狀況很少發生，數學告訴你假如你從要排序的數字裡隨機選一個 $p$，那複雜度期望值還是會落在 $O(n\log n)$。
至於重新排列的部份，我們可以從前面開始看過每個元素，每次
1. 假如 $a_i>p$，不理他
2. 假如 $a_i\leq p$，把他跟第一個 $>p$ 的元素交換
:::spoiler 參考程式碼
```cpp=
int b[500050];
// sort b[l] ~ b[r]
void quickSort(int l, int r) {
if (r <= l) return;
int ip = rand() % (r - l + 1) + l;
swap(b[ip], b[r]); // b[r] is now the pivot
int now = l;
for (int i = l; i < r; i++) {
if (b[i] <= b[r]) {
swap(b[i], b[now]);
now++;
}
}
swap(b[now], b[r]);
quickSort(l, now - 1);
quickSort(now + 1, r);
}
```
:::
期望複雜度是 $O(n\log n)$，想深入了解的請進[複雜度證明（第8~9頁）](https://www.cs.auckland.ac.nz/compsci220s1c/lectures/2016S1C/CS220-Lecture10.pdf)，我就不再重寫一次了。當然他跟merge sort各有優劣勢，但超出了本篇範圍QQ
### 暴力與分治混合？
$O(n\log n)$ 算法真香，要 $O(n^2)$ 算法何用？在大資料上，merge sort和quick sort等算法確實優於 $O(n^2)$ 的方法，但在小規模資料上（例如 $n=20$），insertion sort因為常數優勢會有更好的表現。不僅是排序演算法，在很多問題中，混用分治與暴力作法都可以有些微的加速，比如說設定一個閾值，問題規模小於閾值時暴力解決，否則使用複雜度較好但常數大的算法。
### 關於排序的題外話
除了上面提到的幾種，還有其他並非基於分治的排序算法，例如基於堆積的算法heap sort，都可以達到排序演算法的理論複雜度上限 $O(n\log n)$。假如在特定條件下，可能還有更優的radix sort、counting sort、bucket sort。
[C++內建函式庫也包含了內建排序](https://hackmd.io/@nehs-iced-7th/rk7moqETd#/4/5)`std::sort`，使用的是混合quick sort、heap sort、insertion sort三種算法的intro sort，最差複雜度是 $O(n\log n)$。因為這三種算法都是基於比較兩個元素決定誰先後，因此`std::sort`是可以使用在自訂的結構或者自訂的比較基準上的。
排序還有很多相關的主題可以寫，有機會再獨立出去一篇吧。
## 分治例題
### [TIOJ1080 逆序數對](https://tioj.ck.tp.edu.tw/problems/1080)
> 經典問題。給你一個序列 $a_1, a_2, \dots, a_n$ ，請你求出有幾組 $i<j$ 使得 $a_i>a_j$，也就是有幾對數字前面的比後面的大。
>
> $n\leq 10^5$，$-2^{31}\leq a_i<2^{31}$
這個問題可以輕鬆用資料結構（BIT、線段樹甚至是treap，看你想吸多少毒）解決，但是我們考慮以下分治的作法。首先，我們可以把序列切成前後兩半，此時所有的逆序數對會有三種
1. 兩個數字都在左半邊：相同的問題，序列長度小了一半，可以遞迴計算
2. 兩個數字都在右半邊：相同的問題，序列長度小了一半，可以遞迴計算
3. 一個在左邊、一個在右邊：？？？
只要分別算出三種各有幾對，加起來就是需要的答案。前兩類都可以遞迴解決，因此我們要解決的只有第三種，又因為前半段的數字一定會在後半段的數字前面（廢話），第一個條件 $i<j$ 也可以不用理他了。因此我們實際上要解決的是：
> 對於後半段的每一個數字，前半段裡面有幾個比他還大？
這時你想起了[二分搜](https://hackmd.io/@nehs-iced-7th/S1bNH5YB_)，假如你先把前半段<font color="blue">排序</font>，我可以對後半段的每個數字，在前半段裡<font color="green">二分搜</font>第一個比他大的數字在哪裡。這裡~~因為我不想再畫一次遞迴樹~~直接套主定理了，複雜度是
$$
T(n)=2T(\frac{n}{2})+
\color{blue}{\frac{n}{2}\log\left(\frac{n}{2}\right)}+
\color{green}{\frac{n}{2}\log\left(\frac{n}{2}\right)}\\
T(n)=n\log^2n
$$
這時你盯著log上面的平方覺得很不開心，也許我們可以把二分搜省了。觀察到右半邊的數字越大，左半邊比他大的數字也會越少，假如右半邊也已經排序好了，對於右半邊的每個數字，二分搜出來的位置也會一直往右走，那你可以維護一個一直往右移的指針代表「對於這個右半段的數字，在左半邊第一個比他大的在哪裡」，因為指針只會往右移動，最多移動 $\frac{n}{2}$ 次，我們在 $O(n)$ 的時間裡成功計算出橫跨兩邊的逆序數對數量。
```cpp=
{ 2, 3, 5, 7, 8 }
^ 1 ?
^ 3 ?
^ 4 ?
^ 6 ?
^ 10 ?
```
「等一等」你說。「誰跟你說兩邊都排序好了？對兩邊都先排序一次，合併需要的log還是沒有消失啊？」這時，你又想起了merge sort。merge sort做的事情，正是把兩個排序好的序列，合併成一個排序好的大序列，那你當然可以在計算完逆序數對之後，把前後兩半合起來日後好做事。至此，分治的架構呼之欲出
1. 分：序列切一半，把逆序數對分成三類
2. 遞迴：遞迴前後兩半，計算只出現在同一邊的逆序數對數量
3. 治：
- $O(n)$ 計算橫跨兩邊的逆序數對數量
- 合併兩段，排序好整個區間
複雜度又是熟悉的
$$
T(n)=2T(\frac{n}{2})+n\\
T(n)=O(n\log n)
$$
這樣切一半的技巧特別常用！
:::spoiler 參考程式碼
```cpp=
int a[100010];
int tmp[100010];
int inversion(int l, int r) {
// base case
if (l == r) return 0;
// divide & conquer
int m = (l + r) / 2;
int ans = inversion(l, m) + inversion(m + 1, r);
// calculate
int idx = l;
for (int i = m + 1; i <= r; i++) {
while (idx <= m && a[idx] <= a[i]) idx++;
ans += m + 1 - idx;
}
// merge sort
int il = l, ir = m + 1;
for (int i = l; i <= r; i++) {
if (ir == r + 1 || (il <= m && a[il] < a[ir])) {
tmp[i] = a[il];
il++;
} else {
tmp[i] = a[ir];
ir++;
}
}
for (int i = l; i <= r; i++) a[i] = tmp[i];
return ans;
}
```
:::
### [ZJd784 最大連續元素和](https://zerojudge.tw/ShowProblem?problemid=d784)
>
> 給你一個序列 $a_1, a_2, \dots, a_n$，請求出最大的連續元素的和，也就是
> $$
> \max_{1\leq l,r\leq n}\left(\sum_{k=l}^r > a_k\right)
> $$
>
> $n\leq 100$，$|a_i|\leq 10000$
:::spoiler 看到這裡，DP大師們坐不住了。
$$
dp_i=max(0,dp_{i-1})+a_i
$$
$O(n)$ DP不香嗎？
:::
然而，既然要學習分治，我們嘗試用不同的想法來解決他：沒錯，我們又要把序列切一半了。手起刀落，序列從中間應聲斷裂，我們又可以把所有的連續區間分成三種
1. 整段都在左邊
2. 整段都在右邊
3. 橫跨正中間，左右各出一段接起來
前兩種依舊可以遞迴，需要解決的只有第三種。注意到左邊出的那一段一定是從右邊長出來的，也就是他一定會接上正中間的分割點，既然左半邊和右半邊的貢獻無關（最後加起來不會互相影響），那左半邊最好的選擇一定是「從哪裡開始，一路加到正中間的總和最大」。例如
```cpp=
{ 2, -5, 4, -3, 5 }
--- = 5
------- = 2
---------- = 6 (max)
-------------- = 1
----------------- = 3
```
假如左半邊長這樣，那你會知道不管右半邊怎麼選，最好的選擇一定是從4開始。要求出這個最大值，你只需要從右邊開始一路加到左邊，看看加到哪裡會最大，同理對於右半段也可以用相同的辦法，從左邊加到右邊找最大的。複雜度仍然是
$$
T(n)=2T(\frac{n}{2})+n=O(n\log n)
$$
:::spoiler 參考程式碼
```cpp=
int a[100010];
int sum(int l, int r) {
// base case
if (l == r) return a[l];
// divide & conquer
int m = (l + r) / 2;
int ans = max(sum(l, m), sum(m + 1, r));
// calculate
int now;
int maxl = -INT_MAX;
now = 0;
for (int i = m; i >= l; i--) {
now += a[i];
maxl = max(maxl, now);
}
int maxr = -INT_MAX;
now = 0;
for (int i = m + 1; i <= r; i++) {
now += a[i];
maxr = max(maxr, now);
}
ans = max(ans, maxl + maxr);
return ans;
}
```
:::
### [太陽軍團](https://neoj.sprout.tw/problem/127/)
> 給你一個不知道長怎樣、很大很大的 $N\times M$ 矩陣。你可以多次詢問某一格的值是多少，且已知每一列的最大值出現位置都在上一列最大值的右邊，請你找出每一列的最大值出現在哪裡。
>
> $1<N\leq M\leq 10^6$
比如說這是一個可能的矩陣
<center><img src="https://i.imgur.com/4bzLO7M.png" width="300"></center><br>
其中，黃色的格子是每一列的最大值。
暴力檢查 $O(NM)$ 個格子肯定不行的，我們需要分治。我們可以選正中間的那一列，$O(M)$ 找出他的最小值，像這樣
<center><img src="https://i.imgur.com/Sinnldn.png" width="300"></center><br>
其中，黃色格子需要被詢問，橘色格子則是最大值發生的位置。因為最大值的出現位置有單調性（一直往右跑），所以你會發現，有不少格子絕對不會是答案
<center><img src="https://i.imgur.com/9ADKN6a.png" width="300"></center><br>
灰色的格子都沒救了，所以你只需要檢查紅色的格子們就好。
「等等！」你發現。「每次都要檢查 $O(M)$ 個格子，沒救了吧？」
真的會這麼糟嗎？以剛剛的例子來說，下一層遞迴需要被檢查的格子有
<center><img src="https://i.imgur.com/DwSlCiO.png" width="300"></center><br>
再下一層遞迴呢？觀察到：遞迴樹上每一層需要詢問的所有格子，加起來不會超過 $M$ 格，而遞迴樹的深度正是 $\log N$ 層。總時間複雜度是 $M\log N$，完全可以通過。
這個例題和前面的問題最大的不同在於，這一層遞迴需要的時間不僅和要分治的 $N$ 有關，也和其他變數有關，是不能直接主定理的。但是經過分析，還是可以發現我們已經透過「分」的過程把問題規模縮的夠小，因此，在複雜度不顯然的時候，一些巧妙的複雜度分析也許可以幫你找到出路。
## 更多習題
我道歉，這些題目的難度好像高出上面的例題有點多QQ
### [好的連續子序列](https://neoj.sprout.tw/problem/788/)
:::spoiler 提示1
（原題也有提供）題目需要的限制，等同於找出有幾組 $(l,r)$ 使得
$$
r-l=\max_{l\leq i\leq r}\{ a_i \}-\min_{l\leq i\leq r}\{ a_i \}
$$
:::
:::spoiler 提示2
又是要你找有幾個連續區間，切一半有用嗎？
:::
:::spoiler 提示3
「橫跨中間的區間」需要分成幾種情況？
:::
:::spoiler 題外話
這題有很多作法，就我所知還有另外兩種需要資料結構的方法，但分治是所有方法中最快的
:::
### [JOISC2019 Minerals](https://oj.uz/problem/view/JOI19_minerals)
:::spoiler 提示1
25分的第二子題頗為有用
:::
:::spoiler 提示2
把礦物放進去或拿出來有差嗎？機器給你的回覆本身比較重要，還是一次詢問前後這個數字的變化量比較重要？
:::
:::spoiler 提示3
切兩半！
切什麼？要怎麼切？花多久切？
:::
:::spoiler 提示4
有必要從正中間切下去嗎？把 $T(n)$ 列出來，從正中間切下去一定最好嗎？
:::
:::spoiler 提示5
DP可能會有用
:::
:::spoiler 題外話
我自己只有想出70分解orz
要超過70分，提示4是關鍵。
:::
### [最長上升子序列LIS](https://tioj.ck.tp.edu.tw/problems/1175)
:::spoiler 提示1
對於每個 $i$，你想知道結束在 $a_i$ 的最長遞增子序列有多長。
:::
:::spoiler 提示2
合併一定要在遞迴之後嗎？能不能先遞迴一半，合併，再遞迴後面一半？
姑且稱為「合併」，更像「轉移」一些。
:::
:::spoiler 提示3
CDQ分治
:::
:::spoiler 題外話
假如變成二維的最長遞增子序列，也就是給你 $a_1,a_2\dots ,a_n$ 和 $b_1,b_2,\dots,b_n$，要你選出一些 $p_1<\dots<p_k$ 使得
$$
a_{p_1}<a_{p_2}<\dots<a_{p_k}\\
b_{p_1}<b_{p_2}<\dots<b_{p_k}
$$
求出 $k$ 最大可以是多少。這樣可做嗎？
:::
## 應用與延伸
分治並不是特定一個演算法。應該說，分治就像遞迴一樣是一種概念，可以衍生出許多應用，例如
- CDQ分治
- 動態規劃中的分治優化
- 在樹上的分治，例如樹DP、重心分治
- 線段樹也可以是分治的一種形式
- ....
這篇僅止於最經典的分治，希望能給讀者一些對分治的認識，從這裡開始為日後探究更精深的分治鋪路。
## 結語
分治博大精深而無所不在。這篇大概是我目前為止花最久時間撰寫的一篇講義，但還有許多不足之處，例如廢話太多、例題可能不夠有代表性等等，排序的部份也佔據略多篇幅，有機會應該要再分出去獨立寫一篇。然而，還是希望這篇講義能作為入門幫助到讀者。
另外，這篇講義相當一部分參考了算法班的分治單元，也要特別感謝資訊之芽算法班的講師們！
Sign in with Wallet
Connect another wallet