線段樹

線段樹是一種二叉搜索樹，與區間樹相似，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。

對於線段樹中的每一個非葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。因此線段樹是平衡二叉樹，最後的子節點數目為N，即整個線段區間的長度。

使用線段樹可以快速的查找某一個節點在若干條線段中出現的次數，時間複雜度為O(logN）。而未優化的空間複雜度為2N，因此有時需要離散化讓空間壓縮。

線段樹至少支持下列操作：

Insert(t,x）：將包含在區間int的元素x插入到樹t中；

Delete(t,x）：從線段樹t中刪除元素x；

Search(t,x）：返回一個指向樹t中元素x的指針。

線段樹是建立在線段的基礎上，每個結點都代表了一條線段[a,b]。長度為1的線段稱為元線段。非元線段都有兩個子結點，左結點代表的線段為[a,(a+b)/2]，右結點代表的線段為[((a+b)/2）+1,b]。

右圖就是一棵長度範圍為[1,5]的線段樹。

長度範圍為[1,L]的一棵線段樹的深度為log(L)+1。這個顯然，而且存儲一棵線段樹的空間複雜度為O(L）。

線段樹支持最基本的操作為插入和刪除一條線段。下面以插入為例，詳細敘述，刪除類似。

將一條線段[a,b]插入到代表線段[l,r]的結點p中，如果p不是元線段，那麼令mid=（l+r）/2。如果b mid，那麼將線段[a,b也插入到p的右兒子結點中。

插入（刪除）操作的時間複雜度為O(Log N）。

上面的都是些基本的線段樹結構，但只有這些並不能做什麼，就好比一個程序有輸入沒輸出，根本沒有任何用處。

最簡單的應用就是記錄線段有否被覆蓋，並隨時查詢當前被覆蓋線段的總長度。那麼此時可以在結點結構中加入一個變數int count；代表當前結點代表的子樹中被覆蓋的線段長度和。這樣就要在插入（刪除）當中維護這個count值，於是當前的覆蓋總值就是根節點的count值了。

另外也可以將count換成bool cover；支持查找一個結點或線段是否被覆蓋。

實際上，通過在結點上記錄不同的數據，線段樹還可以完成很多不同的任務。例如，如果每次插入操作是在一條線段上每個位置均加k，而查詢操作是計算一條線段上的總和，那麼在結點上需要記錄的值為sum。

這裡會遇到一個問題：為了使所有sum值都保持正確，每一次插入操作可能要更新O(N）個sum值，從而使時間複雜度退化為O(N）。

解決方案是Lazy思想：對整個結點進行的操作，先在結點上做標記，而並非真正執行，直到根據查詢操作的需要分成兩部分。

根據Lazy思想，我們可以在不代表原線段的結點上增加一個值toadd，即為對這個結點，留待以後執行的插入操作k值的總和。對整個結點插入時，只更新sum和toadd值而不向下進行，這樣時間複雜度可證明為O(logN）。

對一個toadd值不為0的結點整個進行查詢時，直接返回存儲在其中的sum值；而若對其一部分進行查詢，則要更新其左右子結點的sum值，然後把toadd值傳遞下去，再對這個查詢本身，左右子結點分別遞歸下去。時間複雜度也是O(logN）。

#include

using namespace std;

#define Maxn 10000

struct Node{

int a,b,left,right,cover;

};

Node Tree[Maxn];

int Number,Tot,c,d;

void build(int a,int b){

int Now;

Tot++;

Now=Tot;

Tree[Now].a=a;

Tree[Now].b=b;

Tree[Now].cover=0;

if(b-a>1){

int mid=(a+b)>>1;

Tree[Now].left=Tot+1;

build(a,mid);

Tree[Now].right=Tot+1;

build(mid,b);

}

}

void insert(int Num){

if(c<=Tree[Num].a&&Tree[Num].b<=d)

Tree[Num].cover++;

else{

int mid=(Tree[Num].a+Tree[Num].b)>>1;

if(c<=mid)

insert(Tree[Num].left);

if(d>=mid)

insert(Tree[Num].right);

}

}

void del(int Num){

if(c<=Tree[Num].a&&Tree[Num].b<=d)

Tree[Num].cover--;

else{

int mid=(Tree[Num].a+Tree[Num].b)>>1;

if(c<=mid)

insert(Tree[Num].left);

if(d>=mid)

insert(Tree[Num].right);

}

}

void Count(int Num){

if(Tree[Num].cover)

Number+=(Tree[Num].b-Tree[Num].a);

else{

if(Tree[Num].left)

Count(Tree[Num].left);

if(Tree[Num].right)

Count(Tree[Num].left);

}

}

int main()

{

scanf("%d%d",&c,&d);

build(c,d);

while(scanf("%d%d",&c,&d)!=EOF)

insert(1);

Number=0;

Count(1);

printf("%d\n",Number);

return 0;

}

Program IntervalTree;

Const Maxn=10000;

Inf='Input.txt';

Ouf='Output.txt';

Type TreeNode=Record

a,b,Left,Right,Cover:Longint;

End;

Var Tree:array [1..Maxn] of TreeNode;

Number,Tot,c,d:Longint;

Procedure MakeTree(a,b:Longint);

Var Now:Longint;

Begin

Inc(Tot);

Now:=Tot;

Tree[Now].a:=a; Tree[Now].b:=b; Tree[Now].Cover:=0;

If a+1

Tree[Now].Left:=Tot+1;

MakeTree(a,(a+b) div 2);

Tree[Now].Right:=Tot+1;

MakeTree((a+b) div 2,b);

End;

End;

Procedure Insert(Num:Longint);

Begin

If (c<=Tree[Num].a) and (Tree[Num].b<=d) then

Tree[Num].Cover:=Tree[Num].Cover+1

Else begin

If c<(Tree[Num].a+Tree[Num].b) div 2 then Insert(Tree[Num].Left);

If d>(Tree[Num].a+Tree[Num].b) div 2 then Insert(Tree[Num].Right);

End;

End;

Procedure Delete(Num:Longint);

Begin

If (c<=Tree[Num].a) and (Tree[Num].b<=d) then

Dec(Tree[Num].Cover)

Else begin

If c<(Tree[Num].a+Tree[Num].b) div 2 then Delete(Tree[Num].Left);

If d>(Tree[Num].a+Tree[Num].b) div 2 then Delete(Tree[Num].Right);

End;

End;

Procedure Count(Num:longint);

Begin

If Tree[Num].Cover>0 then

Number:=Number+(Tree[Num].b-Tree[Num].a)

Else begin

If Tree[Num].Left>0 then Count(Tree[Num].Left);

If Tree[Num].Right>0 then Count(Tree[Num].Right);

End;

End;

Begin

Assign(Input,Inf);Reset(Input);

Assign(Output,ouf);Rewrite(Output);

Readln(c,d);

MakeTree(c,d);

While not eof do Begin

Readln(c,d);

Insert(1);

End;

Count(1);

Writeln(Number);

Close(Output);

Close(Input);

End.

相信對演演算法設計或者數據結構有一定了解的人對線段樹都不會太陌生。它是能夠在log(MaxLen）時間內完成線段的添加、刪除、查詢等操作。但一般的實現都有點複雜而線段樹應用中有一種是專門針對點的。（點樹？）它的實現卻非常簡單。

這種數據結構有什麼用？我們先來考慮一下下面的需求（全部要求在LogN時間內完成）：如何知道一個點在一個點集里的大小“排名”？很簡單，開一個點數組，排個序，再二分查找就行了；如何在一個點集內動態增刪點？也很簡單，弄個平衡樹就行了（本來平衡樹比線段樹複雜得多，但自從世界上有了STL set這麼個好東東，就……^_^）那如果我既要動態增刪點，也要隨時查詢到一個點的排名呢？那對不起，可能就要出動到我們的“點樹”了。

其實現原理很簡單：每當增加（或刪除）一個大小為X的點時，就在樹上添加（或刪除）一條（X,MaxLen）的線段（不含端點），當要查詢一個點的排名時，只要看看其上有多少條線段就可以了。針對這一需求，這裡有個非常簡單的實現（見以下代碼，十多行，夠短了吧？）其中clear（）用於清空點集；add（）用於添加一個點；cntLs（）返回小於n的點的個數，也就是n的升序排名，類似地cntGt是降序排名。

這個點樹有什麼用呢？其中一個應用是在O(NlogN）時間內求出一個排列的逆序數，方法是每讀到一個數x，就讓逆序數+=cntGt(x）；然後再add(x）。

這個實現還可以進行一些擴展。比如刪除del(int n），只要把add(int n）中的++size換成--size，把a[i/2]++改成a[i/2]--即可。另外還可以通過二分查找功能在O(logN）時間內查到排名第n的點的大小。應該也可以三四行內搞定。

補充：楊弋同學在2008年信息學奧賽冬令營上新發明了一種線段樹的省空間堆式存儲法，具體方法可以見08年冬令營課件.

實現代碼　template//表示可用區間為[0,N），其中N必須是2的冪數；

class PointTree{

int a[ 2 * N];

int size;

void clear() { memset(this,0,sizeof (* this));}

void add(int n) {

int i = N + n; ++ size;

for (++ a[i]; i > 1 ; i /= 2）

if (~ i & 1） a[i / 2 ] ++ ;

}

int cntLs(int n) { // 統計小於

int i = N + n,c = 0 ; // 若統計小於等於則c=a;

for (; i > 1 ; i /= 2）

if (i & 1） c += a[i / 2 ];

return c;

}

int cntGt(int n) { return size - a[N + n] - cntLs(n); }

} ;

void del(int n){

if(!a[n+=N])return;

--size;

for(--a[n]; n>1; n/=2）

if(~n&1）--a[n/2];

}

* 解決：求點集中第i小的數（由0數起）

* 注意：如果i>=size 返回N-1

*/

int operator[](int n){

int i=1;

while(i

if(n

else n-=a,i=i*2+1;

}

return i-N;

}

};

//附一個 測試程序

#include< iostream.h>

T<8192> t;

int main(){

char c; int n;

while(cin>>c){

if(c=='c') t.clear();

else{

cin>>n;

if(c=='a') t.add(n);

if(c=='d') t.del(n);

if(c=='q') cout< <

}

}

return 0;

}

另一種功能上比較類似的數據結構：“樹狀數組”。它們有不少相似之處：

針對點集的處理（添加、刪除、查找）；

相似的時空複雜度（logN時間，2N空間）；

相似的編程複雜度（都比線段樹簡短得多）；

因此，所有可以用樹狀數組解決的問題都可以用這個“點樹”來解決，另外它還有以下好處：

更直觀的轉移；

同時支持自下而上和自上而下兩種方向的查找和更新，而後者樹狀數組不支持，所以樹狀數組不提供某些功能，比如說O(logN）求點集中第k小數。