一、線段樹基本概念
線段樹是一種二叉搜索樹，與區間樹相似，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。
對於線段樹中的每一個非葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。因此線段樹是平衡二叉樹，最後的子節點數目為N，即整個線段區間的長度。
使用線段樹可以快速的查找某一個節點在若干條線段中出現的次數，時間復雜度為O(logN）。而未優化的空間復雜度為2N，因此有時需要離散化讓空間壓縮。
性質：父親的區間是[a,b],(c=(a+b)/2)左兒子的區間是[a,c]，右兒子的區間是[c+1,b]，線段樹需要的空間為數組大小的四倍
二、線段樹的存儲數據結構
由上面的圖可以看出，存儲一顆線段樹和二叉樹有點類似，需要左孩子和右孩子節點，另外，為了存儲每條線段出現的次數，所以一般會加上計數的元素，其具體如下：
[cpp]
struct Node // 線段樹
{
int left;
int right;
int counter;
}segTree[4*BORDER];
struct Node // 線段樹
{
int left;
int right;
int counter;
}segTree[4*BORDER];
其中，;left代表左端點、right代表右端點，counter代表每條線段出現的次數，BORDE代表線段端點坐標不超過100。由上面的性質可以知道，我們需要4倍的空間來存儲。
三、線段樹支持的操作
一顆線段樹至少支持以下四個操作：
void construct(int index, int lef, int rig)，構建線段樹 根節點開始構建區間[lef,rig]的線段樹
void insert(int index, int start, int end)，插入線段[start,end]到線段樹, 同時計數區間次數
int query(int index, int x)，查詢點x的出現次數，從根節點開始到[x,x]葉子的這條路徑中所有點計數相加方為x出現次數
void delete_ (int c , int d, int index)，從線段樹中刪除線段[c,d]
具體操作如下：
1、線段樹的創建
[cpp]
/* 構建線段樹 根節點開始構建區間[lef,rig]的線段樹*/
void construct(int index, int lef, int rig)
{
segTree[index].left = lef;
segTree[index].right = rig;
if(lef == rig) // 葉節點
{
segTree[index].counter = 0;
return;
}
int mid = (lef+rig) >> 1;
construct((index<<1)+1, lef, mid);
construct((index<<1)+2, mid+1, rig);
segTree[index].counter = 0;
}
/* 構建線段樹 根節點開始構建區間[lef,rig]的線段樹*/
void construct(int index, int lef, int rig)
{
segTree[index].left = lef;
segTree[index].right = rig;
if(lef == rig) // 葉節點
{
segTree[index].counter = 0;
return;
}
int mid = (lef+rig) >> 1;
construct((index<<1)+1, lef, mid);
construct((index<<1)+2, mid+1, rig);
segTree[index].counter = 0;
}
2、線段樹的元素插入
[cpp]
/* 插入線段[start,end]到線段樹, 同時計數區間次數 */
void insert(int index, int start, int end)
{
if(segTree[index].left == start && segTree[index].right == end)
{
++segTree[index].counter;
return;
}
int mid = (segTree[index].left + segTree[index].right) >> 1;
if(end <= mid)//左子樹
{
insert((index<<1)+1, start, end);
}else if(start > mid)//右子樹
{
insert((index<<1)+2, start, end);
}else//分開來了
{
insert((index<<1)+1, start, mid);
insert((index<<1)+2, mid+1, end);
}
}
/* 插入線段[start,end]到線段樹, 同時計數區間次數 */
void insert(int index, int start, int end)
{
if(segTree[index].left == start && segTree[index].right == end)
{
++segTree[index].counter;
return;
}
int mid = (segTree[index].left + segTree[index].right) >> 1;
if(end <= mid)//左子樹
{
insert((index<<1)+1, start, end);
}else if(start > mid)//右子樹
{
insert((index<<1)+2, start, end);
}else//分開來了
{
insert((index<<1)+1, start, mid);
insert((index<<1)+2, mid+1, end);
}
}
3、線段樹的元素查找
[cpp]
/* 查詢點x的出現次數
* 從根節點開始到[x,x]葉子的這條路徑中所有點計數相加方為x出現次數
*/
int query(int index, int x)
{
if(segTree[index].left == segTree[index].right) // 走到葉子，返回
{
return segTree[index].counter;
}
int mid = (segTree[index].left+segTree[index].right) >> 1;
if(x <= mid)
{
return segTree[index].counter + query((index<<1)+1,x);
}
return segTree[index].counter + query((index<<1)+2,x);
}
/* 查詢點x的出現次數
* 從根節點開始到[x,x]葉子的這條路徑中所有點計數相加方為x出現次數
*/
int query(int index, int x)
{
if(segTree[index].left == segTree[index].right) // 走到葉子，返回
{
return segTree[index].counter;
}
int mid = (segTree[index].left+segTree[index].right) >> 1;
if(x <= mid)
{
return segTree[index].counter + query((index<<1)+1,x);
}
return segTree[index].counter + query((index<<1)+2,x);
}4、線段樹的元素刪除
[cpp]
void delete_ (int c , int d, int index)
{
if(c <= segTree[index].left && d >= segTree[index].right)
segTree[index].counter--;
else
{
if(c < (segTree[index].left + segTree[index].right)/2 ) delete_( c,d, segTree[index].left);
if(d > (segTree[index].left + segTree[index].right)/2 ) delete_( c,d, segTree[index].right);
}
}
void delete_ (int c , int d, int index)
{
if(c <= segTree[index].left && d >= segTree[index].right)
segTree[index].counter--;
else
{
if(c < (segTree[index].left + segTree[index].right)/2 ) delete_( c,d, segTree[index].left);
if(d > (segTree[index].left + segTree[index].right)/2 ) delete_( c,d, segTree[index].right);
}
} 四、線段樹的應用
區間最值查詢問題
連續區間修改或者單節點更新的動態查詢問題
多維空間的動態查詢
