分治法
===
###### tags: `Algorithm`

>分治法:分而治之
分: 切分問題
治: 解決、合併問題

很多時候大的問題很難解決，但是當規模較小的時候我們能直接知道答案。
那我們何不嘗先解決小的問題，在解決大的呢?
:::info
分治步驟:
我有一個問題 -> 如果小到我們知道答案直接回答 否則繼續問更小的問題 -> 想辦法用兩個小問題的答案湊出原本問題的答案。
:::
或許這樣講有點抽象，我們用範例來讓大家體會分治的強大。

## 例一. 區間最小值
>給你 n 個數字, 請輸出其中的最小值。

用單純的分治解最小值看起來或許很蠢，不過我認為他是夠簡單且能體會分治的問題。
試著套用上面剛剛學到的步驟，嘗試以分治解決。
1. 問題: `int query(int l, int r)`
我們希望這個函式能回傳`[l,r)`區間的最小值。

2. 什麼時候可以直接回答?
當 `r-l==1` 時, 只有一個元素, 最小值就是他自己

3. 當不能直接回答，問更小的問題
我們把詢問 `[l,r)` 切成兩半
變成 `[l,m)` 和 `[m,r)`，其中 `m = (l+r)/2`

4. 當我們有了小問題的答案，該如何回答原問題?
整個區間的最小值 = min( 左半最小, 右半最小)
因此 `return min( query(l,m), query(r,m) );`

:::warning
呼叫遞迴時有個要點，你要先假設你的下一層會好好地把事情做完。
不要擔心下一層怎麼運作，你只要確保:
1. 如果下一層是對的我能算對這一層
2. 遞迴直到某一層能直接停下來(直接取得答案)

類似數學歸納法的感覺
:::

### Code
寫成程式碼會長成:

int arr[100];

int query (int l, int r)
{
    if (r-l == 1) return arr[l];
    else
    {
        int m = (l+r)/2;
        return min( query(l,m), query(m,r) );
    }
}

## 例二. 合併排序

>給你 n 個數字, 請你由小到大排序。

這個問題看起來有點難，至少我們不能很直覺的解決他。
我們再度嘗試以分治解決。

1. 問題: msort(l,r) 我們希望把 `[l,r)` 排序

2. 什麼時候可以直接回答?
當 `r-l == 1` ，也就是只有一個元素時，我們不用排序。

3. 當不能直接回答，問更小的問題
我們把它切成兩半
設 `m = (l+r)/2` ，然後 `msort(l,m); msort(m,r);`

4. 用兩個小問題的答案湊出原本問題的答案
這部分稍微難一點
當我們有
`左:(1,3,6,7)` 和 `右:(2,4,5,8)` 兩個序列
要如何推出 `答:(1,2,3,5,7,8,10)`?

我們從左右兩邊各自拿最小的出來比較
1比較小先排入答案
因此有:

左:(3,6,7) 右(2,4,5,8) 答:(1, ...)

接下來繼續，這次最小的是右邊頭的 2, 那也把它丟進答案:

左:(3,6,7) 右(4,5,8) 答:(1,2, ...)

接下來可以試著自己推演。

示意圖:

### Code

int arr[N], n, tmp[N];

inline void merge (int l, int r) // 合併答案
{
    // tmp 拿來存合併時的答案
    // i 為左半邊頭, j 為右半邊頭, k 為放進答案的位置
	int m = (l+r)>>1;
	for (int i=l,j=m,k=l; k<r; k++)
	{
        // 右半邊空了 或 左半最小的比較小, 並且左半還有東西, 那就拿左邊。反之。
		if (i<m && (j>=r || arr[i]<arr[j])) tmp[k] = arr[i++];
		else tmp[k] = arr[j++];
	}
	for (int i=l; i<r; i++) arr[i] = tmp[i];
}
inline void merge_sort (int l, int r) // 遞迴
{
	if (r-l<=1) return;
	int m = (l+r)>>1;
	merge_sort(l,m);
	merge_sort(m,r);
    // 現在, 陣列的左半和右半都是分別排序好的。
	merge(l,r);
}