O(nlnnblnb)

我們發(fā)現(xiàn)blnb的最小值點(diǎn)為x=e，也就在2~3之間，而且x=2和x=3的函數(shù)值相差不大，也就是說我們劃分成2個(gè)子問題或者劃分成3個(gè)子問題的時(shí)候，效率是最高的。另一方面，劃分成2個(gè)子問題的程序比3個(gè)的要更好實(shí)現(xiàn)，因此我們一般在分治的時(shí)候?qū)栴}劃分為2個(gè)子問題。當(dāng)然在必要時(shí)可能會(huì)有其他劃分方法。

快速傅里葉變換
處理多項(xiàng)式的乘法，分解多項(xiàng)式并應(yīng)用復(fù)數(shù)的對(duì)稱和周期性減少重復(fù)計(jì)算

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

（在樹上的分治）

……

數(shù)據(jù)結(jié)構(gòu)

實(shí)際上很多基于樹的數(shù)據(jù)結(jié)構(gòu)都可以認(rèn)為采用了分治思想，但分治不代表一定是簡單的二分。

線段樹
數(shù)列每次對(duì)半切割，區(qū)間查找被劃分為幾個(gè)已有的線段樹節(jié)點(diǎn)的并。

線段樹是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)之一，這里較詳細(xì)地講一下。譬如給定一個(gè)數(shù)列1, 2, 3, 4，構(gòu)造這個(gè)數(shù)列的線段樹。
結(jié)果如下：

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

看起來和歸并排序的遞歸過程很像。實(shí)際上因?yàn)槎加蟹种嗡枷?，像是必然的?br /> 那么我們查詢區(qū)間[2,3]的和，我們會(huì)這么走：
[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]
也就是我們將這個(gè)區(qū)間按照適當(dāng)?shù)姆绞剑ò凑找延械膭澐址椒ǎ﹦澐殖?個(gè)子區(qū)間（或者正好不需要?jiǎng)澐?，繼續(xù)往下走），得到2個(gè)子區(qū)間（子問題）的和，再加起來，得到當(dāng)前區(qū)間（大問題）的和。我們很容易知道，這么做的時(shí)間復(fù)雜度是均攤logn的。

對(duì)半劃分子問題的優(yōu)勢我們?cè)趯w并排序的時(shí)候已經(jīng)講過了，這里的理由類似。但是像B樹等就不是對(duì)半劃分的。
- 伸展樹
數(shù)列每次從某個(gè)點(diǎn)切割，某個(gè)點(diǎn)可以代表一個(gè)區(qū)間
- 劃分樹
數(shù)列每次按較小的一半和較大的一般切割
- 樹狀數(shù)組
和線段樹類似
- ……

一些題目

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

分治 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

總結(jié)

我們先介紹了分治法是怎么樣的一種思想，并介紹了一些典型（常見）的運(yùn)用了分治思想的算法和數(shù)據(jù)結(jié)構(gòu)。我們了解了分治法是如何自頂向下的。實(shí)際上現(xiàn)實(shí)生活中我們也能見到分治法的運(yùn)用。我們寫一個(gè)策劃，會(huì)將策劃的不同環(huán)節(jié)交給不同的人做，最后總策劃再將各個(gè)人做好的各個(gè)部分的策劃修改并整合成最終的總策劃。而每個(gè)寫子策劃的人又可能將任務(wù)繼續(xù)下派分發(fā)給部門內(nèi)部多個(gè)人員共同完成?？梢哉f，計(jì)算機(jī)科學(xué)中的分治法源于生活。如此重要的思想，我們一定要理解。