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