O(nlnnblnb)

我們發現blnb的最小值點為x=e，也就在2~3之間，而且x=2和x=3的函數值相差不大，也就是說我們劃分成2個子問題或者劃分成3個子問題的時候，效率是最高的。另一方面，劃分成2個子問題的程序比3個的要更好實現，因此我們一般在分治的時候將問題劃分為2個子問題。當然在必要時可能會有其他劃分方法。

快速傅里葉變換
處理多項式的乘法，分解多項式并應用復數的對稱和周期性減少重復計算

快速冪
將求n次冪分為2個n/2次冪的較小問題，而兩個小問題是相同的，求出一個就知道另外一個的解

（在樹上的分治）

……

數據結構

實際上很多基于樹的數據結構都可以認為采用了分治思想，但分治不代表一定是簡單的二分。

線段樹
數列每次對半切割，區間查找被劃分為幾個已有的線段樹節點的并。

線段樹是最基礎的數據結構之一，這里較詳細地講一下。譬如給定一個數列1, 2, 3, 4，構造這個數列的線段樹。
結果如下：

|---------------|| 1 2 3 4 ||---------------|| 1 2 | 3 4 ||---------------|| 1 | 2 | 3 | 4 ||---------------|

看起來和歸并排序的遞歸過程很像。實際上因為都有分治思想，像是必然的。
那么我們查詢區間[2,3]的和，我們會這么走：
[2,3] in [1,4]->[2,2] in [1,2] & [3,3] in [3,4] -> [2,2] in [2,2] & [3,3] in [3,4]
也就是我們將這個區間按照適當的方式（按照已有的劃分方法）劃分成2個子區間（或者正好不需要劃分，繼續往下走），得到2個子區間（子問題）的和，再加起來，得到當前區間（大問題）的和。我們很容易知道，這么做的時間復雜度是均攤logn的。

對半劃分子問題的優勢我們在將歸并排序的時候已經講過了，這里的理由類似。但是像B樹等就不是對半劃分的。
- 伸展樹
數列每次從某個點切割，某個點可以代表一個區間
- 劃分樹
數列每次按較小的一半和較大的一般切割
- 樹狀數組
和線段樹類似
- ……

一些題目

以下題目分類僅供參考。。

分治 POJ

2083

BZOJ

1095, 2001, 2229, 2287, 2458, 2229, 3614, 3658, 3879, 4025, 4059

CodeForces

321E, 576E

樹分治 POJ

1741, 1987, 2114,

BZOJ

1095, 1468, 1758, 2152, 2599, 3365, 3435, 3648, 3672, 3697, 3784, 3924, 4012, 4016, 4372

HDU

4812

CDQ分治 BZOJ

1176, 1492, 1537, 2244, 2683, 2716, 2961, 3262, 3295

總結

我們先介紹了分治法是怎么樣的一種思想，并介紹了一些典型（常見）的運用了分治思想的算法和數據結構。我們了解了分治法是如何自頂向下的。實際上現實生活中我們也能見到分治法的運用。我們寫一個策劃，會將策劃的不同環節交給不同的人做，最后總策劃再將各個人做好的各個部分的策劃修改并整合成最終的總策劃。而每個寫子策劃的人又可能將任務繼續下派分發給部門內部多個人員共同完成。可以說，計算機科學中的分治法源于生活。如此重要的思想，我們一定要理解。