O(nlnnblnb)

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

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

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

（在樹(shù)上的分治）

……

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

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

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

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

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

看起來(lái)和歸并排序的遞歸過(guò)程很像。實(shí)際上因?yàn)槎加蟹种嗡枷耄袷潜厝坏摹?br /> 那么我們查詢(xún)區(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ū)間（子問(wèn)題）的和，再加起來(lái)，得到當(dāng)前區(qū)間（大問(wèn)題）的和。我們很容易知道，這么做的時(shí)間復(fù)雜度是均攤logn的。

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

一些題目

以下題目分類(lèi)僅供參考。。

分治 POJ

2083

BZOJ

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

CodeForces

321E, 576E

樹(shù)分治 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é)

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