http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html

線段樹在一些acm題目中經常見到，這種數據結構主要應用在計算幾何和地理信息系統中。下圖就為一個線段樹：

(PS：可能你見過線段樹的不同表示方式，但是都大同小異，根據自己的需要來建就行。)

1.線段樹基本性質和操作

線段樹是一棵二叉樹，記為T(a, b)，參數a,b表示區間[a,b]，其中b-a稱為區間的長度，記為L。

線段樹T(a,b)也可遞歸定義為：

若L>1 : [a, (a+b) div 2]為 T的左兒子；[(a+b) div 2,b]為T 的右兒子。 若L=1 : T為葉子節點。

?

線段樹中的結點一般采取如下數據結構：

struct Node {int left,right; //區間左右值Node *leftchild;Node *rightchild; };

線段樹的建立：

Node *build(int l , int r ) //建立二叉樹 {Node *root = new Node;root->left = l;root->right = r; //設置結點區間root->leftchild = NULL;root->rightchild = NULL;if ( l +1< r ){int mid = (r+l) >>1;root->leftchild = build ( l , mid ) ;root->rightchild = build ( mid , r) ; } return root; }

線段樹中的線段插入和刪除：

增加一個cover的域來計算一條線段被覆蓋的次數，因此在建立二叉樹的時候應順便把cover置0。

插入一條線段[c,d]：

void Insert(int c, int d , Node *root ) {if(c<= root->left&&d>= root->right) root-> cover++;else {if(c < (root->left+ root->right)/2 ) Insert (c,d, root->leftchild );if(d > (root->left+ root->right)/2 ) Insert (c,d, root->rightchild );} }

?

刪除一條線段[c,d]:

void Delete (int c , int d , Node *root ) {if(c<= root->left&&d>= root->right) root-> cover= root-> cover-1;else {if(c < (root->left+ root->right)/2 ) Delete ( c,d, root->leftchild );if(d > (root->left+ root->right)/2 ) Delete ( c,d, root->rightchild );} }

2.線段樹的運用

線段樹的每個節點上往往都增加了一些其他的域。在這些域中保存了某種動態維護的信息，視不同情況而定。這些域使得線段樹具有極大的靈活性，可以適應不同的需求。

例一：

桌子上零散地放著若干個盒子，桌子的后方是一堵墻。如圖所示。現在從桌子的前方射來一束平行光， 把盒子的影子投射到了墻上。問影子的總寬度是多少？

這道題目是一個經典的模型。在這里，我們略去某些處理的步驟，直接分析重點問題，可以把題目抽象地描述如下：x軸上有若干條線段，求線段覆蓋的總長度，即S1+S2的長度。

?

2.1最直接的做法：

設線段坐標范圍為[min,max]。使用一個下標范圍為[min,max-1]的一維數組，其中數組的第i個元素表示[i,i+1]的區間。數組元素初始化全部為0。對于每一條區間為[a,b]的線段，將[a,b]內所有對應的數組元素均設為1。最后統計數組中1的個數即可。

初始 0 0 0 0 0 [1，2] 1 0 0 0 0 [3，5] 1 0 1 1 0 [4，6] 1 0 1 1 1 [5，6] 1 0 1 1 1

其缺點是時間復雜度決定于下標范圍的平方，當下標范圍很大時（[0,10000]），此方法效率太低。

2.2離散化的做法：

基本思想：先把所有端點坐標從小到大排序，將坐標值與其序號一一對應。這樣便可以將原先的坐標值轉化為序號后，對其應用前一種算法，再將最后結果轉化回來得解。該方法對于線段數相對較少的情況有效。

示例:

[10000,22000] ? [30300,55000] ? [44000,60000] ? [55000,60000]

排序得10000，22000，30300，44000，55000，60000

對應得1， 2， 3， 4， 5， 6

然后是 [1,2] ? ? [3,5] ? ?[4,6] ? ?[5,6]

初始 0 0 0 0 0 [1，2] 1 0 0 0 0 [3，5] 1 0 1 1 0 [4，6] 1 0 1 1 1 [5，6] 1 0 1 1 1

10000，22000，30300，44000，55000，60000

1， ? ? ? 2， ? ? ? ?3， ? ? ? 4， ? ? ? 5， ? ? ? 6

(22000-10000)+(60000-30300)=41700

?

此方法的時間復雜度決定于線段數的平方，對于線段數較多的情況此方法效率太低。

2.3使用線段樹的做法：

給線段樹每個節點增加一個域cover。cover=1表示該結點所對應的區間被完全覆蓋，cover=0表示該結點所對應的區間未被完全覆蓋。

如下圖的線段樹，添加線段[1,2][3,5][4,6]

插入算法：

void Insert(Node *root , int a , int b) {int m;if( root ->cover == 0) { m = (root->left+ root->right)/2 ;if (a == root->left && b == root->right) root ->cover =1;else if (b <= m) Insert(root->leftchild , a, b);else if (a >= m) Insert(root->rightchild , a, b);else { Insert(root->leftchild ,a, m);Insert(root->rightchild , m, b);}} }

統計算法：

int Count(Node *root) {int m,n;if (root->cover == 1)return (root-> right - root-> left);else if (root-> right - root-> left== 1 )return 0;m= Count(root->leftchild);n= Count(root->rightchild);return m+n; }

?

首先排序，起點低的在前面，起點相同的按終點排。然后在進行掃描，并求距離

#include <iostream> #include <algorithm>using namespace std;struct Segment {int start;int end; };bool cmp(const Segment &seg1, const Segment &seg2) {if (seg1.start < seg2.start){return true;}else if (seg1.start > seg2.start){return false;}else{return seg1.end < seg2.end;} }int sum(int n, Segment *segs) {sort(segs, segs + n, cmp);int line = 0, start, end;for (int i = 0; i < n; i++){if (i == 0 || segs[i].start > end){start = segs[i].start;end = segs[i].end;line += end - start;}else if (segs[i].end > end){line += segs[i].end - end;end = segs[i].end;}}return line; }int main() {Segment segs[3];segs[1].start = 1;segs[1].end = 2;segs[0].start = 1;segs[0].end = 3;segs[2].start = 5;segs[2].end = 6;int s = sum(3, segs);cout << s << endl;system("pause");return 0; }

總結

以上是生活随笔為你收集整理的线段的覆盖长度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。