從簡單說起，線段樹其實可以理解成一種特殊的二叉樹。但是這種二叉樹較為平衡，和靜態二叉樹一樣，都是提前已經建立好的樹形結構。針對性強，所以效率要高。這里又想到了一句題外話：動態和靜態的差別。動態結構較為靈活，但是速度較慢；靜態結構節省內存，速度較快。
接著回到線段樹上來，線段樹是建立在線段的基礎上，每個結點都代表了一條線段 [a , b]。長度為1的線段成為元線段。非元線段都有兩個子結點，左結點代表的線段為[a , (a + b ) / 2]，右結點代表的線段為[( a + b ) / 2 , b]。
圖一就是一棵長度范圍為[1 , 10]的線段樹。
長度范圍為[1 , L] 的一棵線段樹的深度為log ( L - 1 ) + 1。這個顯然，而且存儲一棵線段樹的空間復雜度為O（L）。
線段樹支持最基本的操作為插入和刪除一條線段。下面已插入為例，詳細敘述，刪除類似。
將一條線段[a , b] 插入到代表線段[l , r]的結點p中，如果p不是元線段，那么令mid＝（l＋r）/2。如果a<mid，那么將線段[a , b] 也插入到p的左兒子結點中，如果b>mid，那么將線段[a , b] 也插入到p的右兒子結點中。
插入（刪除）操作的時間復雜度為O （ Log n ）。
上面的都是些基本的線段樹結構，但只有這些并不能做什么，就好比一個程序有輸入沒輸出，根本沒有任何用處。
最簡單的應用就是記錄線段有否被覆蓋，并隨時查詢當前被覆蓋線段的總長度。那么此時可以在結點結構中加入一個變量int count；代表當前結點代表的子樹中被覆蓋的線段長度和。這樣就要在插入（刪除）當中維護這個count值，于是當前的覆蓋總值就是根節點的count值了。
另外也可以將 count換成bool cover；支持查找一個結點或線段是否被覆蓋。
例題 1 （ ZJU1610 Count The Colors 線段樹基本應用題目 ）
給出在線段[0,8000]上的若干次涂色，問最后能看見哪些顏色，并統計能看到多少段。
解析
就這個題目而言，方法很多，而且數據范圍不大，但我們由線段樹的角度來解決這個問題。
建立一棵代表線段[0,8000]的線段樹，涂色操作就是將[a , b]涂成顏色c。最后做統計。
結構如下：
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
};
col 有幾種情況，如果col為－1，代表了尚未涂色，－2代表了是混和色，就是說這條線段并不是單一的顏色。其他情況，便是這條線段都是這個顏色的了。
全部程序見附錄1。
線段樹的第一種變化
基本的線段樹代表的是線段，如果我們把線段離散成點來看，那么線段樹可以變化成一種離散類型線段樹。
這里可以有兩種理解。一種離散關系可以是連續的線段的點，比方說在一條直線上放置的連續小球的著色問題；另一種則是完全將線段離散化分成若干小段，對每一段小段做為元線段來建立線段樹，這種線段樹可以支持實數劃分類型的線段。
例題2 （ZJU2451 Minimizing maximizer ）
Andy想要得到一組數中的最大值。會有一系列的操作Sorter (i[1], j[1]), ..., Sorter (i[k], j[k])。作用是將數組中的第i[k]個數字到第j[k]個數字排序。按照輸入給出的順序，你可以選擇要不要執行這個操作。問題是最少需要多少步操作，可以求出這個最大值。題目保證可以求出。
多組數據。
第一行為兩個數字N，M。表示N個數，M個操作。
接下來M行，每行描述一個操作i[k] , j [k]。
對于每組數據，輸出最少需要多少次操作分離得到最大值。
每組數據一行。
解析
由于要將最大的數字分離到最后的一位，如果我們考慮將數組看成一條[1,n]的線段，而每項操作也看成是從[i[k],j[k]]的線段，那么就是要求按照輸入的順序，將線段[1,n]從左到右依次覆蓋掉，問題變成求最小的覆蓋線段總數。
考慮最基本的規劃方法，用Opt [k] 表示覆蓋掉 [1,k]的線段最少需要的步數，那么狀態轉移方程為：
Opt [k] = min { Opt [d] + 1 | j [p] = k && d >= i [p] && d <= j [p] && k > 1 }
Opt [1] = 0;
最后的答案就是Opt [n]了，但是考慮時間復雜度，是O（m^2）級別的，m最大為500000，超時無疑。但是這里我們看到了規劃的決策集合是一條連續的線段，是要在這條線段上面取得最小值，那么線段樹的結構就正好適合在這里應用了。
由于這里最小的單位是一個點，所以我們采取線段樹的第一種變化，把元線段設置為單位點，即[k,k]。在規劃的時候維護線段樹即可。
線段樹結點結構中，需要加入的元素是int minstep 代表最少需要用到的覆蓋線段數目可以覆蓋到當前結點所代表的線段中。
全部程序見附錄2。
例題3 （PKU2104K-th Number）
給出一個大小為 n的數組A[]，給出m個問題（1 <= n <= 100 000, 1 <= m <= 5 000 ）。問題格式為Q（i，j，k），詢問從A[i]到A[j]第k大的元素是什么。A[]中的數各不相同。
解析
由于仍舊是離散的整數問題，我們依舊采取第一種變化。看到題目，最基本的想法就是排序然后求第k個數了，但是時限上不能滿足要求。
線段樹的最強大方面就是將一組數（一條線段）放到一起處理。每層樹需要的線段數目不會超過4，而深度為logn，所以最后操作的復雜度會是O(logn)。
但是僅僅應用線段樹還是不夠的，即使我們知道了需要處理的線段是那些，但是由于線段過多，也無法準確求出第k個元素究竟是什么。這里二分策略就派上了用場。我們用二分枚舉第k個數字P，然后再在所要的線段中找到枚舉的P所在的位置，同樣是用二分的策略。所以復雜度是O(mlognlognlogn)。
我們在找P所在的位置的時候需要用到二分策略，也就是說，我們需要將線段所代表的結點排序，這里可以將每一層的所有數放到一起，統一成一個數組SortArray[depth][]。其實也可以理解成將歸并排序的每個步驟記錄下來。
全部程序見附錄3。
線段樹的第二種變化 （樹狀數組）
在結構上對線段樹進行改變，可以得到線段樹的另一種變化。
用O（n）的一維數組構造出線段樹，無其他附加空間。比方說，一棵從[0,L]的線段樹表示為TNode Tree[L];
這里應用二進制將樹進行劃分。將整數R的二進制表示中的最后一個1換成0，得到數L。Tree[R]代表的線段就是[L,R]。例如：6的二進制表示為（110）2 將最后一個1換成0即為（100）2 ＝4，所以Tree[6]代表的線段就是[4,6]。
析出數R的最后一位1的方法是：LowBit（R）＝R^~R。
包含點L的一系列數為x1,x2,……，這里x1=R，x2=x1+LowBit (x1)，x3=x2+LowBit(x2)，……
這種線段樹的優點在于：
1． 節省空間。完全線段長度的空間，無需左右指針，無需左右范圍。
2． 線段樹查找嚴格log(R)，因為二進制的每位查找一遍。
3． 狀態轉移快，操作簡單。
4． 擴展到多維較為容易。
缺點：
1．隨意表示線段[a,b]較為困難。
這種線段樹適用于：
1． 查找線段[0,L]的信息。
2． 求線段[a,b]的和（應用部分和做差技術）。
// problem zju 1610
// Segment Tree
#define NoColor -1
#define MulColor -2
#include <stdio.h>
#include <string.h>
int Len;
struct TNode {
int left , right;
int col;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int , int );
void Calculate ();
} Tree [16000] , *Root = &Tree [0];
int CalColor [8001] , Many [8001];
void TNode :: Construct ( int l , int r )
{
left = l; right = r;
if ( l + 1 == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &Tree [Len ++];
RightChild = &Tree [Len ++];
LeftChild->Construct( l , mid );
RightChild->Construct( mid , r );
}
void TNode :: Insert ( int l , int r , int c )
{
if ( col == c ) return;
if ( l == left && r == right ) { col = c; return; }
int mid = ( left + right ) >> 1;
if ( col != MulColor ) { LeftChild -> col = col; RightChild -> col = col; }
col = MulColor;
if ( r <= mid ) { LeftChild -> Insert ( l , r , c ); return; }
if ( l >= mid ) { RightChild -> Insert ( l , r , c ); return; }
LeftChild -> Insert ( l , mid , c );
RightChild -> Insert ( mid , r , c );
}
void TNode :: Calculate ()
{
if ( col != MulColor && col != NoColor ) {
int i;
for ( i = left; i < right; i ++ ) CalColor [i] = col;
}
if ( col == MulColor ) { LeftChild -> Calculate (); RightChild -> Calculate (); }
}
main ()
{
int Total , a , b , c , i , t;
Len = 1; Tree [0].Construct( 0 , 8000 );
// printf ( "After Construct the Tree , Len = %d\n" , Len );
while ( scanf ( "%d" , &Total ) != EOF ) {
Tree [0].col = NoColor;
while ( Total ) {
scanf ( "%d %d %d" , &a , &b , &c );
Root -> Insert( a , b , c );
Total --;
}
memset ( CalColor , 0xff , sizeof ( CalColor ) );
memset ( Many , 0 , sizeof ( Many ));
Root -> Calculate ();
t = -1;
for ( i = 0; i <= 8000; i ++ ) {
if ( CalColor [i] == t ) continue;
t = CalColor [i];
if ( t != -1 ) Many [t] ++;
}
for ( i = 0; i <= 8000; i ++ ) if ( Many [i] )
printf ( "%d %d\n" , i , Many [i] );
printf ( "\n" );
}
}
// Problem zju2451
// DP with Segment Tree
#include <stdio.h>
#define MAX 50000
int Len;
struct TNode {
int left , right;
int minstep;
TNode *LeftChild , *RightChild;
void Construct ( int , int );
void Insert ( int , int );
int GetRank ( int , int );
} STree [MAX * 2 + 2] , *Root = &STree [0];
int N , M;
void TNode :: Construct ( int l , int r )
{
left = l; right = r; minstep = 999999;
if ( l == r ) { LeftChild = NULL; RightChild = NULL; return; }
int mid = ( l + r ) >> 1;
LeftChild = &STree [Len ++];
RightChild = &STree [Len ++];
LeftChild->Construct ( l , mid );
RightChild->Construct( mid + 1 , r );
}
void TNode :: Insert ( int p , int x )
{
if ( x < minstep ) minstep = x;
if ( left == right ) return;
if ( p <= ( left + right ) >> 1 ) LeftChild->Insert( p , x );
else RightChild->Insert( p , x );
}
int TNode :: GetRank ( int l , int r )
{
if ( l == left && r == right ) return minstep;
int mid = ( left + right ) >> 1;
if ( r <= mid ) return LeftChild->GetRank( l , r );
if ( l > mid ) return RightChild->GetRank( l , r );
int ret1 , ret2;
ret1 = LeftChild->GetRank( l , mid );
ret2 = RightChild->GetRank( mid + 1 , r );
return ret1 < ret2 ? ret1 : ret2;
}
main ()
{
int i , a , b , p;
while ( scanf ( "%d %d" , &N , &M ) != EOF ) {
Len = 1; Root->Construct( 1 , N );
Root->Insert ( 1 , 0 );
for ( i = 0; i < M; i ++ ) {
scanf ( "%d%d" , &a , &b );
if ( a < b ) {
p = Root->GetRank ( a , b - 1 );
Root->Insert ( b , p + 1 );
}
}
printf ( "%d\n" , Root->GetRank( N , N ) );
}
}
// PKU 2104
// Segment Tree && Binnary Search
#include <stdio.h>
#define MAX 100000
int len;
struct TNode {
int left , right;
char depth;
TNode *LeftChild , *RightChild;
void construct ( int , int , int );
int GetRank ();
} Node [2 * MAX + 2];
int SortArray [18] [MAX + 2];
int Key , ls , rs;
void TNode :: construct ( int l , int r , int dep )
{
left = l; right = r; depth = dep;
if ( left == right ) {
scanf ( "%d" , &SortArray [dep] [l] );
return;
}
int mid = ( l + r ) >> 1;
LeftChild = &Node [len ++];
LeftChild->construct( l , mid , dep + 1 );
RightChild = &Node [len ++];
RightChild->construct( mid + 1 , right , dep + 1 );
int i = left , j = mid + 1 , k = left;
while ( i <= mid && j <= r ) {
if ( SortArray [dep + 1] [i] < SortArray [dep + 1] [j] )
SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
else
SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
while ( i <= mid ) SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];
while ( j <= right ) SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];
}
int TNode :: GetRank ()
{
if ( ls <= left && right <= rs ) {
if ( SortArray [depth] [left] >= Key ) return 0;
if ( SortArray [depth] [right] < Key ) return right - left + 1;
if ( SortArray [depth] [right] == Key ) return right - left;
int low = left , high = right , mid;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
if ( SortArray [depth] [mid] < Key ) low = mid;
else high = mid;
}
return low - left + 1;
}
int ret = 0;
if ( ls <= LeftChild->right ) ret += LeftChild->GetRank();
if ( RightChild->left <= rs ) ret += RightChild->GetRank();
return ret;
}
main ()
{
int N , Q , i;
int low , high , mid , Index;
scanf ( "%d%d" , &N , &Q );
len = 1; Node [0].construct( 0 , N - 1 , 0 );
for ( i = 0; i < Q; i ++ ) {
scanf ( "%d%d%d" , &ls , &rs , &Index );
ls --; rs --;
low = 0; high = N;
while ( low + 1 < high ) {
mid = ( low + high ) >> 1;
Key = SortArray [0] [mid];
if ( Node [0].GetRank() >= Index ) high = mid;
else low = mid;
}
printf ( "%d\n" , SortArray [0] [low] );
}
}