二維線段樹(shù)最主要用于平面統(tǒng)計(jì)問(wèn)題。類似一維線段樹(shù)，最經(jīng)典的就是求區(qū)間最值（或區(qū)間和），推廣到二維，求得就是矩形區(qū)域最值（或矩形區(qū)域和），對(duì)于矩形區(qū)域和，二維樹(shù)狀數(shù)組更加高效，而矩形區(qū)域最值，更加高效的方法是二維RMQ，但是二維RMQ不支持動(dòng)態(tài)更新，所以二維線段樹(shù)還是有用武之地的。
如果對(duì)一維線段樹(shù)已經(jīng)駕輕就熟，那么直接來(lái)看下面兩段對(duì)比，就可以輕松理解二維線段樹(shù)了。
一維線段樹(shù)是一棵二叉樹(shù)，樹(shù)上每個(gè)結(jié)點(diǎn)保存一個(gè)區(qū)間和一個(gè)域，非葉子結(jié)點(diǎn)一定有兩個(gè)兒子結(jié)點(diǎn)，兒子結(jié)點(diǎn)表示的兩個(gè)區(qū)間交集為空，并集為父結(jié)點(diǎn)表示的區(qū)間；葉子結(jié)點(diǎn)的表示區(qū)間長(zhǎng)度為1，即單位長(zhǎng)度；域則表示了需要求的數(shù)據(jù)，每個(gè)父結(jié)點(diǎn)的域可以通過(guò)兩個(gè)兒子結(jié)點(diǎn)得出。
二維線段樹(shù)是一棵四叉樹(shù)，樹(shù)上每個(gè)結(jié)點(diǎn)保存一個(gè)矩形和一個(gè)域，非葉子結(jié)點(diǎn)一定有二或四 個(gè)兒子結(jié)點(diǎn)，兒子結(jié)點(diǎn)表示的四個(gè)矩形交集為空，并集為父結(jié)點(diǎn)表示的矩形；葉子結(jié)點(diǎn)表示的矩形長(zhǎng)寬均為1，域則表示了需要求的數(shù)據(jù)，每個(gè)父結(jié)點(diǎn)的域可以通過(guò)四個(gè)兒子結(jié)點(diǎn)得出。
一個(gè)4x3的矩形，可以用圖1的樹(shù)形結(jié)構(gòu)來(lái)表示，給每個(gè)單位方塊標(biāo)上不同的顏色易于理解。
圖1
圖1中，每個(gè)葉子結(jié)點(diǎn)的單位面積為1，非葉子結(jié)點(diǎn)表示的矩形進(jìn)行四分后，如圖2所示，四個(gè)子矩形分別表示的是兒子結(jié)點(diǎn)表示的矩形區(qū)域。特殊的，當(dāng)矩形面積為1 X H或者W X 1的時(shí)候，變成了一維的情況，這就是為什么有些結(jié)點(diǎn)有四個(gè)子結(jié)點(diǎn)，而有些結(jié)點(diǎn)只有兩個(gè)子結(jié)點(diǎn)的原因了。
圖2
基本結(jié)構(gòu)已經(jīng)清楚了，按照慣例，要介紹一下時(shí)空復(fù)雜度。
首先來(lái)看空間復(fù)雜度，一個(gè) W x H 的矩形，根結(jié)點(diǎn)表示的矩形是W x H，令N = max{W, H}，那么這棵二維線段樹(shù)的深度D = log2(N)+1，當(dāng)這棵樹(shù)是一棵滿四叉樹(shù)的時(shí)候，結(jié)點(diǎn)數(shù)達(dá)到最大值，根據(jù)等比數(shù)列求和公式，最大情況的結(jié)點(diǎn)數(shù)為 (4^D - 1) / 3。更加直觀的，當(dāng)N = W = H = 2^k, 必定是一棵滿四叉樹(shù)，結(jié)點(diǎn)數(shù)為(4^D-1) / 3 = ( 4^(k+1) - 1 ) / 3 = (2^（2k+2）-1) / 3，去掉分子上的零頭1，約等于(4/3)*N^2， 所以空間復(fù)雜度為O(N^2)。
再來(lái)看時(shí)間復(fù)雜度，需要分情況：
建樹(shù)：建樹(shù)時(shí)必定訪問(wèn)到每個(gè)結(jié)點(diǎn)，而且都是訪問(wèn)一次，所以建樹(shù)的復(fù)雜度為O(N^2)；
單點(diǎn)更新：每次更新一個(gè)單位矩形的值，訪問(wèn)時(shí)只會(huì)訪問(wèn)從樹(shù)的根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的一條路徑，所以單點(diǎn)更新的復(fù)雜度為O( log2(N) )。
區(qū)域詢問(wèn)：情況類似一維的區(qū)間詢問(wèn)。從根結(jié)點(diǎn)開(kāi)始拆分區(qū)域，當(dāng)詢問(wèn)區(qū)域完全覆蓋結(jié)點(diǎn)區(qū)域時(shí)，不需要遞歸往下走，總體復(fù)雜度是O( log2(N) * log2(N) ) ？ 這里還是打個(gè)問(wèn)號(hào)先，具體是一個(gè)log還是兩個(gè)log記不清了，找個(gè)時(shí)間證明一下，可以肯定的是，不會(huì)退化成O(N)。
接下來(lái)看看每個(gè)樹(shù)結(jié)點(diǎn)需要保存一些什么信息， 以最值為例，除了保存最值以外，有可能需要知道這個(gè)最值在整個(gè)矩形的具體坐標(biāo)，所以我們的最值信息dataInfo需要保存三個(gè)信息，posx和posy表示最值的具體位置，val保存最值，由于二維線段樹(shù)的空間復(fù)雜度為O(N^2)，所以坐標(biāo)信息不會(huì)很大，為了盡力節(jié)省內(nèi)存，坐標(biāo)值用short來(lái)存即可。最值val的話看實(shí)際情況而定，一般用int就夠了。
treeNode則是線段樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)體，其中成員由dataInfo對(duì)應(yīng)的最值和son[4]表示的子結(jié)點(diǎn)編號(hào)組成，我們的線段樹(shù)結(jié)點(diǎn)采用靜態(tài)結(jié)點(diǎn)，即每個(gè)線段樹(shù)結(jié)點(diǎn)都對(duì)應(yīng)靜態(tài)數(shù)組 nodes中的某個(gè)元素，便于通過(guò)編號(hào)在O(1)的時(shí)間內(nèi)獲取到對(duì)應(yīng)樹(shù)結(jié)點(diǎn)的指針，son[4]記錄了四個(gè)子結(jié)點(diǎn)在nodes中的下標(biāo)。仔細(xì)觀察可以發(fā)現(xiàn)，如果對(duì)于一棵線段樹(shù)，保證所有結(jié)點(diǎn)編號(hào)都連續(xù)的情況下，如果父結(jié)點(diǎn)的編號(hào)確定，那么子結(jié)點(diǎn)的編號(hào)也就確定了。例如，根結(jié)點(diǎn)編號(hào)為1，那么四個(gè)子結(jié)點(diǎn)編號(hào)為2、3、4、5，父結(jié)點(diǎn)編號(hào)為2，四個(gè)子結(jié)點(diǎn)的編號(hào)為6、7、8、9，根據(jù)數(shù)學(xué)歸納法，當(dāng)結(jié)點(diǎn)編號(hào)為p，那么它的四個(gè)子結(jié)點(diǎn)編號(hào)為(4*p-2+x)，其中x取值為[0, 3]，所以四個(gè)子結(jié)點(diǎn)的編號(hào)信息可以通過(guò)O(1)的時(shí)間計(jì)算出來(lái)，就不用存儲(chǔ)在線段樹(shù)結(jié)點(diǎn)上了，大大節(jié)省了內(nèi)存開(kāi)銷(xiāo)。
結(jié)構(gòu)定義代碼如下：
#define LOGN 10
#define MAXN (1<<LOGN)
#define MAXNODES 3*(1<<(2*LOGN)/4 + 100)
#define son(x) (p*4-2+x)
// 最值信息
struct dataInfo {
short posx, posy;
int val;
dataInfo() {
posx = posy = val = -1;
}
dataInfo(short _posx, short _posy, int _val) {
posx = _posx;
posy = _posy;
val = _val; }
};
// 線段樹(shù)結(jié)點(diǎn)信息
struct treeNode {
// int son[4]
dataInfo maxv, minv;
void reset() { maxv = dataInfo(0, 0, INT_MIN);
minv = dataInfo(0, 0, INT_MAX);
}
}nodes[ MAXNODES ];
// 注意，這里需要返回指針，因?yàn)樵诤罄m(xù)使用中需要對(duì)這個(gè)結(jié)點(diǎn)的信息進(jìn)行改變，如果返回對(duì)象的話只是一個(gè)copy，不會(huì)改變?cè)Y(jié)點(diǎn)的內(nèi)容
treeNode* getNode(int id) { return &nodes[id];
}
這時(shí)候，我們發(fā)現(xiàn)線段樹(shù)的結(jié)點(diǎn)上還缺少一個(gè)很重要的信息，因?yàn)槊總€(gè)結(jié)點(diǎn)表示了一個(gè)矩形區(qū)域，那為什么沒(méi)有存下這個(gè)矩形區(qū)域呢？毋庸置疑，也是為了節(jié)省內(nèi)存，在接下來(lái)的區(qū)域查詢、單點(diǎn)更新的介紹中會(huì)講到，這個(gè)區(qū)域其實(shí)在每次遞歸的時(shí)候是作為傳參進(jìn)入函數(shù)內(nèi)部的，結(jié)點(diǎn)編號(hào)確定，矩形區(qū)域就確定了，所以沒(méi)必要存儲(chǔ)在結(jié)點(diǎn)中。
為了處理方便，我們還需要封裝一個(gè)區(qū)間類（由于矩形可以表示成兩個(gè)不同維度的區(qū)間，所以這里只需要封裝一個(gè)區(qū)間類即可，矩形類的操作沒(méi)有區(qū)間內(nèi)那么簡(jiǎn)單，一目了然），它支持一些基本操作，如判交、判包含、取左右半?yún)^(qū)間等等、，具體代碼如下：
struct Interval {
int l, r;
Interval() {}
Interval(int _l, int _r) {
l = _l;
r = _r; }
// 區(qū)間中點(diǎn)
int mid() {
return (l + r) >> 1;
}
// 區(qū)間長(zhǎng)度
int len() {
return r - l + 1;
}
// 左半?yún)^(qū)間
Interval left() {
return Interval(l, mid());
}
// 右半?yún)^(qū)間
Interval right() {
return Interval(mid()+1, r); }
// 區(qū)間判交
bool isIntersectWith( Interval& tarI ) {
return !( l > tarI.r || r < tarI.l ); }
// 區(qū)間判包含
bool isInclude( Interval& tarI ) {
return l <= tarI.l && tarI.r <= r; }
bool in (int v) {
return l <= v && v <= r; }
};
那么接下來(lái)就是建樹(shù)了，建樹(shù)就是遞歸生成結(jié)點(diǎn)的過(guò)程，這里的生成并非創(chuàng)建，原因是因?yàn)槲覀兊慕Y(jié)點(diǎn)是靜態(tài)的。每建一次樹(shù)，只是把所有線段樹(shù)結(jié)點(diǎn)的信息進(jìn)行一次重置，對(duì)于一個(gè)W x H的矩形，假定它的兩個(gè)對(duì)角線坐標(biāo)為(1, 1) - (W, H)，那么我們首先將它切割成四個(gè)矩形，令WM = (1+W)/2, HM = (1+H)/2對(duì)角線坐標(biāo)分別為：
(1, 1) - (WM, HM)
(WM+1, 1) - (W, HM)
(1, HM+1) - (WM, H)
(WM+1, HM+1) - (W, H)
圖3
這個(gè)切割過(guò)程是遞歸進(jìn)行的，當(dāng)某次切割的矩形為單位面積的時(shí)候，即為遞歸出口。當(dāng)然還有一種情況，就是當(dāng)某次切割后的矩形的某一維為1，而另一維大于1時(shí)，這里假設(shè)W = 1，H > 1，那么繼續(xù)切割時(shí)會(huì)發(fā)現(xiàn)WM+1 > W,導(dǎo)致 (WM+1, 1) - (W, HM) 和 (WM+1, HM+1) - (W, H) 這兩個(gè)矩形面積為負(fù)，所以在遞歸入口處需要判斷是否有某一維的右端點(diǎn)小于左端點(diǎn)，如果有，這種矩形是不合法的，不能做為線段樹(shù)的結(jié)點(diǎn)，不需要繼續(xù)往下遞歸創(chuàng)建。
建樹(shù)代碼如下：
void build_segtree(int p, Interval xI, Interval yI) { // 空矩形（右端點(diǎn)小于左端點(diǎn)）
if(xI.len() <= 0 || yI.len() <= 0) {
return ;
}
treeNode* now = getNode(p); // 結(jié)點(diǎn)初始化
now->reset(); // 單位矩形
if(xI.len() == 1 && yI.len() == 1) {
return ;
}
build_segtree( son(0), xI.left(), yI.left() );
build_segtree( son(1), xI.right(), yI.left());
build_segtree( son(2), xI.left(), yI.right() );
build_segtree( son(3), xI.right(), yI.right()); }
其中p為當(dāng)前線段樹(shù)結(jié)點(diǎn)的編號(hào)，son(0) - son(3)則是作為子結(jié)點(diǎn)編號(hào)穿參進(jìn)入切割后的矩形, getNode(p)用于獲取編號(hào)為p的結(jié)點(diǎn)的結(jié)構(gòu)指針，建樹(shù)的目的就是為每個(gè)結(jié)點(diǎn)進(jìn)行初始化，如果求的是最大值，那么將結(jié)點(diǎn)上的域都設(shè)成 INT_MIN ( 只要比所有接下來(lái)要插入的值小即可 )，如果求的是最小值，那么結(jié)點(diǎn)上的域都設(shè)成 INT_MAX( 只要比所有接下來(lái)要插入的值大即可 )。
建樹(shù)完畢后，這些結(jié)點(diǎn)都有了一個(gè)初始值，那么接下來(lái)就是需要在矩形的每個(gè)點(diǎn)插入一個(gè)值，然后更新線段樹(shù)上每個(gè)結(jié)點(diǎn)的最值信息了。
插入過(guò)程和建樹(shù)過(guò)程的思想是一致的，同樣是將矩形切割成四份，因?yàn)椴迦氲氖且粋€(gè)點(diǎn)，所以不可能同時(shí)存在于任意兩個(gè)矩形中（因?yàn)槭莻€(gè)矩形是互不相交的），所以每次四分只會(huì)選擇一個(gè)矩形進(jìn)行插入，為了讓代碼簡(jiǎn)介，我們還是先將矩形進(jìn)行切割，然后模擬所有的矩形都能夠插入，然后在遞歸入口處判斷該點(diǎn)是否在矩形區(qū)域中，如果不在矩形區(qū)域直接返回。這樣，當(dāng)遞歸到單位矩形的時(shí)候，這個(gè)點(diǎn)的坐標(biāo)一定是和矩形的坐標(biāo)重合的，就可以直接更新該矩形所在的線段樹(shù)結(jié)點(diǎn)的域信息了，更新完這個(gè)單位矩形還不夠，還需要將信息傳遞給它的父結(jié)點(diǎn)，因?yàn)槊看胃轮挥幸粋€(gè)點(diǎn)，所以改變的結(jié)點(diǎn)只有從這個(gè)單位矩形所在結(jié)點(diǎn)到根結(jié)點(diǎn)的一條路徑上的結(jié)點(diǎn)，所以復(fù)雜度是樹(shù)的深度，即O(log2(N))。
插入結(jié)點(diǎn)（單點(diǎn)更新）代碼如下：
bool insert_segtree(int p, Interval xI, Interval yI, int x, int y, int val) {
if(xI.len() <= 0 || yI.len() <= 0) {
return false;
}
if( !xI.in(x) || !yI.in(y) ) {
return true;
}
treeNode *now = getNode(p);
if(xI.len() == 1 && yI.len() == 1) {
now->maxv = now->minv = dataInfo(x, y, val);
return true;
}
bool isvalid[4];
isvalid[0] = insert_segtree( son(0), xI.left(), yI.left(), x, y, val );
isvalid[1] = insert_segtree( son(1), xI.right(), yI.left(), x, y, val );
isvalid[2] = insert_segtree( son(2), xI.left(), yI.right(), x, y, val );
isvalid[3] = insert_segtree( son(3), xI.right(), yI.right(), x, y, val );
// 通過(guò)四個(gè)子結(jié)點(diǎn)的信息更新父結(jié)點(diǎn)
now->maxv = dataInfo(0, 0, MIN_VAL);
now->minv = dataInfo(0, 0, MAX_VAL);
int i;
for(i = 0;i < 4; i++) {
if( !isvalid[i] ) continue;
treeNode *sonNode = getNode(son(i));
now->maxv = sonNode->maxv.val > now->maxv.val ? sonNode->maxv : now->maxv;
now->minv = sonNode->minv.val < now->minv.val ? sonNode->minv : now->minv;
}
return true; }
可以發(fā)現(xiàn)，插入的核心代碼和建樹(shù)是一致的，但是這里的插入操作，返回了一個(gè)值，表示的是當(dāng)前插入的線段樹(shù)結(jié)點(diǎn)p是否合法，因?yàn)槲覀冊(cè)诓迦氲臅r(shí)候無(wú)論如何都會(huì)將矩形切割成四份，沒(méi)有去考慮上文中提到的有一維為1的情況，父結(jié)點(diǎn)的域值是通過(guò)子結(jié)點(diǎn)回溯上來(lái)進(jìn)行更新的，如果子結(jié)點(diǎn)不合法，不應(yīng)該作為更新的依據(jù)，所以作為父結(jié)點(diǎn)，需要知道哪些結(jié)點(diǎn)是不合法的。
有了更新，當(dāng)然需要詢問(wèn)，沒(méi)有詢問(wèn)，更新也就失去了意義。
詢問(wèn)一般是區(qū)域詢問(wèn)（單點(diǎn)詢問(wèn)就沒(méi)必要用線段樹(shù)了），如圖4所示，在一個(gè)4 x 3的矩形中，需要詢問(wèn)灰色的矩形（3 x 2的矩形，以下統(tǒng)一稱為詢問(wèn)矩形）中最大的數(shù)是什么。首先來(lái)說(shuō)說(shuō)原理，同樣，和建樹(shù)以及插入操作一樣，我們首先不斷將矩形進(jìn)行切割，每當(dāng)訪問(wèn)到一個(gè)結(jié)點(diǎn)的時(shí)候?qū)⒃儐?wèn)矩形和結(jié)點(diǎn)矩形進(jìn)行判交測(cè)試，一共有以下幾種情況：
1、詢問(wèn)矩形 和 結(jié)點(diǎn)矩形 沒(méi)有交集 （圖4中所有白色的葉子結(jié)點(diǎn)）；
2、詢問(wèn)矩形 完全包含 結(jié)點(diǎn)矩形 （圖4中根結(jié)點(diǎn)的第三個(gè)子結(jié)點(diǎn)）；
3、詢問(wèn)矩形 不完全包含 結(jié)點(diǎn)矩形，并且存在交集（圖4中根結(jié)點(diǎn)的第一、二、四個(gè)子結(jié)點(diǎn)）；
首先我們需要保存一個(gè)全局最大值信息，這個(gè)信息可以通過(guò)引用的方式傳遞到函數(shù)中去，在遞歸的過(guò)程中不斷迭代更新；
對(duì)于第1、2兩種情況都是不需要繼續(xù)往下遞歸的，第1種情況不會(huì)影響目前的最大值，第2種情況需要將結(jié)點(diǎn)上的最大值和全局最大值進(jìn)行比較，保留大的那個(gè)；第三種情況有交集，所以我們需要將矩形繼續(xù)分割，直到出現(xiàn)第1或者第2種情況為止，而且一定是可以出現(xiàn)的。
圖4
區(qū)域詢問(wèn)代碼如下：
// query_type 0 最大值 1最小值
void query_segtree(int p, Interval xI, Interval yI, Interval tarXI, Interval tarYI, dataInfo& ans, int query_type) {
if(xI.len() <= 0 || yI.len() <= 0) {
return ;
}
if( !tarXI.isIntersectWith(xI) || !tarYI.isIntersectWith(yI) ) {
return ;
}
treeNode *now = getNode(p);
// 最大值優(yōu)化
if(query_type == 0 && ans.val >= now->maxv.val) {
return ; }
// 最小值優(yōu)化
if(query_type == 1 && ans.val <= now->minv.val) {
return ;
}
if(tarXI.isInclude(xI) && tarYI.isInclude(yI)) {
if(query_type == 0) {
ans = now->maxv;
}else {
ans = now->minv;
}
return ;
}
query_segtree( son(0), xI.left(), yI.left(), tarXI, tarYI, ans, query_type );
query_segtree( son(1), xI.right(), yI.left(), tarXI, tarYI, ans, query_type );
query_segtree( son(2), xI.left(), yI.right(), tarXI, tarYI, ans, query_type ); query_segtree( son(3), xI.right(), yI.right(), tarXI, tarYI, ans, query_type );
}
這里加入了一個(gè)query_type，表示求的是最大值還是最小值，因?yàn)橛械臅r(shí)候既需要知道最大值，又需要知道最小值，為了簡(jiǎn)化函數(shù)個(gè)數(shù)引入的一個(gè)變量。這里我們發(fā)現(xiàn)，當(dāng)求最大值的時(shí)候，如果 詢問(wèn)矩形 和 結(jié)點(diǎn)矩形 是有交集并且并非完全包含的情況下，如果結(jié)點(diǎn)最大值比全局最大值（以上代碼中的ans即全局最大值信息）還小，那么沒(méi)必要再往下遞歸了，因?yàn)檫f歸下去的最大值不會(huì)比當(dāng)前結(jié)點(diǎn)的最大值大，這個(gè)優(yōu)化很重要。
以上就是二維線段樹(shù)通過(guò)三個(gè)函數(shù)實(shí)現(xiàn)求區(qū)域最值的全部?jī)?nèi)容，建樹(shù)(build_segtree)、插入(insert_segtree) 、詢問(wèn)(query_segtree),其實(shí)當(dāng)我們將這三個(gè)函數(shù)中的 yI 這個(gè)區(qū)間變成[1, 1]的時(shí)候，就變成了一維線段樹(shù)的模板了。