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