最近重溫了一下線段樹，發(fā)現(xiàn)暑假學(xué)得太囫圇吞棗蕉斜，某些細(xì)節(jié)沒有真正理解逾柿，學(xué)算法還是要腳踏實地啊(日常雞湯)！下面來總結(jié)一下線段樹宅此。

線段樹是什么机错？有什么用？

線段樹類似區(qū)間樹诽凌，它在各個節(jié)點保存一條線段(數(shù)組中的一段子數(shù)組)毡熏，主要用于高效解決連續(xù)區(qū)間的動態(tài)查詢問題，由于二叉結(jié)構(gòu)的特性侣诵，它基本能保持每個操作的復(fù)雜度為O(logn)痢法。
你可能會問：查詢區(qū)間和可以用O(n)的復(fù)雜度預(yù)處理一個前綴和數(shù)組，然后就可以O(shè)(1)地查詢某段區(qū)間和;查詢區(qū)間最值杜顺，也就是RMQ問題财搁，也可以用O(nlogn)的復(fù)雜度預(yù)處理ST表，然后O(1)地查詢區(qū)間最值躬络。那么為什么要使用線段樹呢尖奔？
線段樹的精髓就在于它能在支持區(qū)間動態(tài)修改的前提下保持每個操作O(logn)的復(fù)雜度，這是其他兩者做不到的。
線段樹能進(jìn)行的操作主要有：1)單點更新提茁，區(qū)間查詢 2)區(qū)間更新淹禾，區(qū)間查詢 3)區(qū)間更新，單點查詢
除了上述操作茴扁，線段樹還可以解決區(qū)間染色和矩形面積交铃岔、面積并等問題。

線段樹基本知識

線段樹的結(jié)構(gòu)：

1.png

建立一個線段樹的示意圖(可以維護(hù)區(qū)間和或最值)：

2.png

單點修改后重新調(diào)整線段樹：

3.png

區(qū)間查詢區(qū)間最值：

4.png

線段樹的結(jié)點關(guān)系:

5.png

線段樹的代碼實現(xiàn)

下面給出建立線段樹和進(jìn)行各種操作的模板峭火，關(guān)鍵點在代碼的注釋中有解釋：

/*node：區(qū)間結(jié)點號    begin：該node的區(qū)間左邊界   end：該node的區(qū)間右邊界     
  left：查詢區(qū)間的左邊界 right：查詢區(qū)間的右邊界      pos：查詢區(qū)間的點*/ 
  
/*線段樹:求和或最值 
單點更新,區(qū)間查詢
區(qū)間更新,單點查詢(lazy標(biāo)記表示本節(jié)點的信息已經(jīng)根據(jù)標(biāo)記更新過了毁习，但是本節(jié)點的子節(jié)點仍需要進(jìn)行更新。lazy初始為0,區(qū)間加上k給該區(qū)間管理的結(jié)點的lazy加k,push_down給子節(jié)點加(end-begin+1)*k)
區(qū)間更新,區(qū)間查詢 
lson 2*node
rson 2*node+1
[begin,end]
[begin,mid] [mid+1,end] 其中mid為(begin+end)/2 */ 

#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1) 
int segTree[maxn*4];
int lazy[maxn*4];

void pushUp(int node){//pushUp自底向上更新區(qū)間和與最值 
    segTree[node]=segTree[lson]+segTree[rson];//segTree[node]=max(segTree[lson],segTree[rson]) 
}

void pushDown(int node,int begin,int end){//pushDown自頂向下更新lazy數(shù)組和給結(jié)點加上lazy數(shù)組的值 
    if(!lazy[node]) return;//lazy[node]為0直接return 
    segTree[lson]+=(mid-begin+1)*lazy[node];
    segTree[rson]+=(end-mid)*lazy[node]; 
    lazy[lson]+=lazy[node]; 
    lazy[rson]+=lazy[node];//給左右孩子傳遞lazy,是+=不是=卖丸，因為孩子節(jié)點可能被多次延遲標(biāo)記又沒有向下傳遞 
    lazy[node]=0;//把父節(jié)點的lazy置為0 
}
void build(int node,int begin,int end){//建樹 
    lazy[node]=0;
    if(begin==end){//begin==end表示管理的是結(jié)點 
        scanf("%d",&segTree[node]);//按照順序輸入結(jié)點纺且，由于建樹類似于樹的先根遍歷，所以建立的線段樹的葉子結(jié)點從左到右的值就是輸入的順序 
        //segTree[node]=a[begin] 用于任意順序輸入,先將輸入存入a數(shù)組,下標(biāo)從1開始，begin = end = index 
        return;//輸入完成后要return，否則會繼續(xù)訪問左右孩子挟阻，可能越界
    }
    build(lson,begin,mid);
    build(rson,mid+1,end);
    pushUp(node);
}

void update(int node,int begin,int end,int pos,int k){//單點更新 
    if(pos<begin||pos>end) return;//管理的區(qū)間不包含pos,直接return 
    if(begin==end){
        segTree[node]+=k;
        return;
    } 
    update(lson,begin,mid,pos,k);
    update(rson,mid+1,end,pos,k);
    pushUp(node);
} 

int query(int node,int begin,int end,int left,int right){//區(qū)間查詢 
    if(left>end||right<begin) return 0;//查詢結(jié)點和區(qū)間沒有公共點 
    if(left<=begin&&right>=end) return segTree[node];//查詢區(qū)間包含查詢結(jié)點 
    pushDown(node,begin,end);
    int sum=0;//int maxx=-1
    sum+=query(lson,begin,mid,left,right);//maxx=max(maxx,query(lson,begin,mid,left,right))
    sum+=query(rson,mid+1,end,left,right);//maxx=max(maxx,query(rson,mid+1,end,left,right))
    return sum;
}

void update(int node,int begin,int end,int left,int right,int k){//區(qū)間更新 
    if(left>end||right<begin) return;//結(jié)點和更新區(qū)間沒有公共點 
    if(left<=begin&&right>=end){//更新區(qū)間包含結(jié)點 
        segTree[node]+=(end-begin+1)*k;
        lazy[node]+=k;
        return;
    }
    pushDown(node,begin,end);
    update(lson,begin,mid,left,right,k);
    update(rson,mid+1,end,left,right,k);
    pushUp(node);
}

例題

一、單點更新恐仑，區(qū)間查詢

HDU1166 敵兵布陣
題目鏈接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1166
代碼：

#include<bits/stdc++.h>
#define maxn 50005
#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1)
using namespace std;
int segTree[maxn*4];
int T,N,a,b;
char command[10];
void pushUp(int node){
    segTree[node]=segTree[lson]+segTree[rson];
}
void build(int node,int begin,int end){
    if(begin==end){
        scanf("%d",&segTree[node]);
        return;
    }
    build(lson,begin,mid);
    build(rson,mid+1,end);
    pushUp(node);
}

void update(int node,int begin,int end,int pos,int k){
    if(pos<begin||pos>end) return;
    if(begin==end){
        segTree[node]+=k;
        return;
    }
    update(lson,begin,mid,pos,k);
    update(rson,mid+1,end,pos,k);
    pushUp(node);
}

int query(int node,int begin,int end,int left,int right){
    if(left>end||right<begin) return 0;
    if(left<=begin&&right>=end) return segTree[node];
        int sum=0;
    sum+=query(lson,begin,mid,left,right);
    sum+=query(rson,mid+1,end,left,right);
    return sum;
}

int main(){
    scanf("%d",&T);
    int cas=1;
    while(T--){
        scanf("%d",&N);
        build(1,1,N);
        printf("Case %d:\n",cas++);
        while(scanf("%s",command)!=EOF){
            if(command[0]=='E') break;
            scanf("%d%d",&a,&b);
            if(command[0]=='Q')
            cout<<query(1,1,N,a,b)<<endl;
            else if(command[0]=='A')
            update(1,1,N,a,b);
            else if(command[0]=='S')
            update(1,1,N,a,-b);
        }
    }
}

HDU 1754 I Hate It
題目鏈接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1754
代碼:

#include<bits/stdc++.h>
#define maxn 200005
#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1)
using namespace std;
int segTree[4*maxn];
int N,M,A,B;
char C[3];

void pushUp(int node){
    segTree[node]=max(segTree[lson],segTree[rson]);
}

void build(int node,int begin,int end){
    if(begin==end){
        scanf("%d",&segTree[node]);
        return;
    }
    build(lson,begin,mid);
    build(rson,mid+1,end);
    pushUp(node);
}

void update(int node,int begin,int end,int pos,int k){
    if(pos<begin||pos>end) return;
    if(begin==end){
        segTree[node]=k;//直接修改
        return;
    }
    update(lson,begin,mid,pos,k);
    update(rson,mid+1,end,pos,k);
    pushUp(node);
}

int query(int node,int begin,int end,int left,int right){
    if(left>end||right<begin) return 0;
    if(left<=begin&&right>=end) return segTree[node];
    int maxx=0;
    maxx=max(maxx,query(lson,begin,mid,left,right));
    maxx=max(maxx,query(rson,mid+1,end,left,right));
    return maxx;
}
int main(){
    while(scanf("%d%d",&N,&M)!=EOF){
         build(1,1,N);
         while(M--){
            scanf("%s%d%d",C,&A,&B);
            if(C[0]=='Q'){
                printf("%d\n",query(1,1,N,A,B));
            }
            else{
                update(1,1,N,A,B);
            }
         }
    }

}

二、區(qū)間更新为鳄，區(qū)間查詢

POJ 3468 A Simple Problem with Integers
題目鏈接:http://poj.org/problem?id=3468
代碼：

#include<cstdio>
#define maxn 100005
#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1)
using namespace std;
typedef long long ll;
ll segTree[4*maxn];
ll lazy[4*maxn];
ll N,Q,A,B,C;
char command[3];
void pushUp(ll node){
    segTree[node]=segTree[lson]+segTree[rson];
}

void pushDown(ll node,ll begin,ll end){
    if(!lazy[node]) return;
    segTree[lson]+=(mid-begin+1)*lazy[node];
    segTree[rson]+=(end-mid)*lazy[node];
    lazy[lson]+=lazy[node];
    lazy[rson]+=lazy[node];
    lazy[node]=0;
}

void build(ll node,ll begin,ll end){
    lazy[node]=0;
    if(begin==end){
        scanf("%lld",&segTree[node]);
        return;
    }
    build(lson,begin,mid);
    build(rson,mid+1,end);
    pushUp(node);   
}

ll query(ll node,ll begin,ll end,ll left,ll right){
    if(left>end||right<begin) return 0;
    if(left<=begin&&right>=end) return segTree[node];
    pushDown(node,begin,end);
    ll sum=0;
    sum+=query(lson,begin,mid,left,right);
    sum+=query(rson,mid+1,end,left,right);
    return sum;
}

void update(ll node,ll begin,ll end,ll left,ll right,ll k){
    if(left>end||right<begin) return;
    if(left<=begin&&right>=end){
        segTree[node]+=(end-begin+1)*k;
        lazy[node]+=k;
        return;
    }
    pushDown(node,begin,end);
    update(lson,begin,mid,left,right,k);
    update(rson,mid+1,end,left,right,k);
    pushUp(node);
}

int main(){
    scanf("%lld%lld",&N,&Q);
    build(1,1,N);
    while(Q--){
        scanf("%s",command);
        if(command[0]=='Q'){
            scanf("%lld%lld",&A,&B);
            printf("%lld\n",query(1,1,N,A,B));
        }
        else{
            scanf("%lld%lld%lld",&A,&B,&C);
            update(1,1,N,A,B,C);
        }
    }
} 

HDU 1698 Just A Hook
題目鏈接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1698
代碼：

#include<bits/stdc++.h>
#define maxn 100005
#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1)
using namespace std;
int segTree[4*maxn];
int lazy[4*maxn];
int T,N,Q,X,Y,Z;
void pushUp(int node){
    segTree[node]=segTree[lson]+segTree[rson];
}

void build(int node,int begin,int end){
    lazy[node]=0;
    if(begin==end){
        segTree[node]=1;
        return;
    }
    build(lson,begin,mid);
    build(rson,mid+1,end);
    pushUp(node);
}

void pushDown(int node,int begin,int end){
    if(!lazy[node]) return;
    segTree[lson]=(mid-begin+1)*lazy[node];//+=改成=,直接更新到底部
    segTree[rson]=(end-mid)*lazy[node];
    lazy[lson]=lazy[node];
    lazy[rson]=lazy[node];
    lazy[node]=0;
}

void update(int node,int begin,int end,int left,int right,int k){
    if(left>end||right<begin) return;
    if(left<=begin&&right>=end){
        segTree[node]=(end-begin+1)*k;//+=改成=,直接更新到底部
        lazy[node]=k;//+=改成=,因為此時lazy即使沒有下傳也不疊加
        return;
    }
    pushDown(node,begin,end);
    update(lson,begin,mid,left,right,k);
    update(rson,mid+1,end,left,right,k);
    pushUp(node);
}

int query(int node,int begin,int end,int left,int right){
    if(left>end||right<begin) return 0;
    if(left<=begin&&right>=end) return segTree[node];
    pushDown(node,begin,end);
    int sum=0;
    sum+=query(lson,begin,mid,left,right);
    sum+=query(rson,mid+1,end,left,right);
    return sum;
}
int main(){
    scanf("%d",&T);
    int cas=1;
    while(T--){
        scanf("%d%d",&N,&Q);
        build(1,1,N);
        while(Q--){
            scanf("%d%d%d",&X,&Y,&Z);
            update(1,1,N,X,Y,Z);
        }
        printf("Case %d: The total value of the hook is %d.\n",cas++,query(1,1,N,1,N));
    }
}

三、區(qū)間染色問題

ZOJ 1610 Count the Colors
題目鏈接:https://vjudge.net/problem/11553/origin
代碼：

#include<bits/stdc++.h>
#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1)
#define maxn 8005
using namespace std;
int col[maxn*4];//col[node]表示node管轄的區(qū)間的顏色 
int sum[maxn];//表示某點的顏色 
int res[maxn];

void pushDown(int node){
    col[lson]=col[rson]=col[node];
    col[node]=-1;
}

void update(int node,int begin,int end,int left,int right,int k){
    if(left>end||right<begin) return;
    if(left<=begin&&right>=end){
        col[node]=k;
        return;
    }
    if(col[node]!=-1) pushDown(node);
    update(lson,begin,mid,left,right,k);
    update(rson,mid+1,end,left,right,k);
}
//不用建樹,直接在query里存儲顏色即可腕让，因為染色不用求區(qū)間和或者最值 
void query(int node,int begin,int end,int left,int right){
    if(begin==end){
        sum[begin]=col[node];//存儲每個點的顏色 
        return;
    }
    if (col[node] != -1) pushDown(node);
    query(lson,begin,mid,left,right);
    query(rson,mid+1,end,left,right);
}
int main(){
    int n,x1,x2,c;
    while(scanf("%d",&n)!=EOF){
        memset(col,-1,sizeof(col));
        memset(sum,-1,sizeof(sum));
        memset(res,0,sizeof(res));
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&x1,&x2,&c);
            if(x1==x2) continue;//為了保證R-1>=L 
            update(1,0,maxn-1,x1,x2-1,c);//為防止重疊,更新區(qū)間[L,R-1]
        /*注意begin=0 end=maxn-1 而不是begin=1 end=n 因為只是涂n次,不一定在1-n范圍內(nèi)涂 */   
        }
        query(1,0,maxn-1,0,maxn-1);
        for(int i=0; i<maxn; i++) {
            while(i!=0&&sum[i]!=-1&&sum[i]==sum[i-1])//涂過同一顏色也加1 
            i++;
            res[sum[i]]++;
        }
        for(int i=0; i<maxn; i++)
        if(res[i])
            printf("%d %d\n",i,res[i]);
        printf("\n");
    }
    return 0;
} 

POJ 2528 Mayor's posters
題目鏈接:http://poj.org/problem?id=2528
代碼:

/*解法：離散化孤钦，如下面的例子（題目的樣例），因為單位1是一個單位長度纯丸，將下面的
      1   2   3   4  6   7   8   10
      —   —   —   —  —   —   —   —
      1   2   3   4  5   6   7   8
離散化  X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] = 8; X[8] = 10
于是將一個很大的區(qū)間映射到一個較小的區(qū)間之中了偏形，然后再對每一張海報依次更新在寬度為1~8的墻上(用線段樹），最后統(tǒng)計不同顏色的段數(shù)觉鼻。
但是只是這樣簡單的離散化是錯誤的俊扭，
如三張海報為：1~10 1~4 6~10
離散化時 X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 6, X[ 4 ] = 10
第一張海報時：墻的1~4被染為1；
第二張海報時：墻的1~2被染為2坠陈，3~4仍為1萨惑；
第三張海報時：墻的3~4被染為3，1~2仍為2仇矾。
最終庸蔼，第一張海報就顯示被完全覆蓋了，于是輸出2贮匕，但實際上明顯不是這樣姐仅，正確輸出為3。
新的離散方法為：在相差大于1的數(shù)間加一個數(shù)，例如在上面1 4 6 10中間加5（算法中實際上1掏膏，4之間劳翰，6，10之間都新增了數(shù)的）
X[ 1 ] = 1, X[ 2 ] = 4, X[ 3 ] = 5, X[ 4 ] = 6馒疹， X[ 5 ] = 10
這樣之后佳簸，第一次是1~5被染成1；第二次1~2被染成2行冰；第三次4~5被染成3
最終溺蕉，1~2為2，3為1悼做，4~5為3疯特，于是輸出正確結(jié)果3。*/ 
#include<cstdio> 
#include<cstring>
#include<algorithm>
#define lson (node<<1)
#define rson ((node<<1)|1)
#define mid ((begin+end)>>1)
using namespace std;

#define maxn 10005
//不用建樹,直接在query里記錄hash即可肛走，因為染色不用求區(qū)間和或者最值漓雅，也不用pushUp 
int m, li[maxn], ri[maxn];
int poster[maxn<<3], col[maxn<<4], ans; //col記錄當(dāng)前該位置最上面一層的海報種類,即染色問題的顏色 
//poster記錄海報位置 
bool hash[maxn];//hash用于標(biāo)記某種種類的海報是否計算過,若已計算過標(biāo)記為true,不再重復(fù)計算 

void pushDown(int node) {
     col[lson] = col[rson] = col[node];//類似lazy標(biāo)記，向下傳遞后清空
     col[node] = -1;
}

void update(int node,int begin, int end,int left, int right, int k) {
    if(left>end||right<begin) return;
    if (begin >= left && end <= right) {
         col[node] = k;
         return;
     }
    if(col[node] != -1) pushDown(node);
    update(lson,begin,mid,left,right,k);
    update(rson,mid+1,end,left,right,k);
}

void query(int node,int begin,int end) {
    if (begin == end) {
        if (!hash[col[node]]) {
        ans++;
        hash[col[node]] = true;
       }
       return;
    }
    if (col[node] != -1) pushDown(node);
    query(lson,begin,mid);
    query(rson,mid+1,end);
}

int binarySearch(int ll, int hh, int xx) {
    int mm;
    while (ll <= hh) {
        mm = (ll + hh) >> 1;
        if (poster[mm] == xx) return mm;
        else if (poster[mm] > xx)  hh = mm - 1;
        else ll = mm + 1;
    }
    return -1;
}

int main()
{
    int t, n, i;
    scanf ("%d", &t);
    while (t--) {
        memset(col, -1, sizeof (col));//-1表示沒有染色
        memset (hash, false, sizeof (hash));/*因為本題墻的長度為10000000,
直接做會超時,而實際海報數(shù)量只有10000,考慮把每張海報左右兩端的兩段映射到小范圍計算朽色，
所以考慮離散化,但傳統(tǒng)離散化會出錯,要如果有兩個位置相鄰的數(shù)字?jǐn)?shù)值不相鄰,考慮在中間
插入一個比大的數(shù)小1的數(shù)*/
        int cnt = 0;
        scanf ("%d", &n);
        for (i = 1; i <= n; i++) {
             scanf ("%d %d", &li[i], &ri[i]);
             poster[++cnt] = li[i];
             poster[++cnt] = ri[i];
        }
        sort(poster+1, poster+cnt+1);
        m = 1;
        for (i = 2; i <= cnt; i++) {
             if (poster[i] != poster[i-1]) poster[++m] = poster[i];//去重 
        }
        for (i = m; i > 1; i--) {
            if (poster[i] - poster[i-1] > 1) poster[++m] = poster[i] - 1;//在末尾加入要增加的點 
        }
        sort(poster+1, poster+m+1);//重新排序 
        for (i = 1; i <= n; i++) {
            int l = binarySearch(1, m, li[i]);//在離散化后的poster數(shù)組里二分查找每一組的左右端點
            int r = binarySearch(1, m, ri[i]);
            update(1,1,m,l,r,i);
        }
        ans = 0;
        query(1, 1, m);
        printf("%d\n", ans);
    }
    return 0;
}

四邻吞、矩形面積交/面積并

HDU 1542 Atlantis(矩形面積并)
題目鏈接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1542
代碼:

#include<bits/stdc++.h> 
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid ((l+r)>>1)
#define maxn 2005
using namespace std;

int n;
double y[maxn];
//沿x軸掃描,沿y軸建樹,線段樹的結(jié)點是縱向的線段,最下面一層結(jié)點以排序后相鄰的y1,y2為邊界 
struct LINE     //  存儲線段信息；
{
    double x;   //  該線段的x坐標(biāo)葫男；
    double y_up,y_down;     //  豎向線段的上下端點抱冷；
    int flag;//矩形的左邊界為1,右邊界為-1 
}line[maxn];
struct node//線段樹的結(jié)點,不再是單個點,是一個區(qū)間 
{
    double l,r;     //  區(qū)間的左右邊界,即某段掃描線的上下端點 
    double x;       //  記錄上一個橫坐標(biāo)位置，用于求面積梢褐；
    int cover;      //  記錄覆蓋的線段數(shù);即同一方向的線段數(shù);由flag累加 
    bool flag;      //  標(biāo)記只有一個區(qū)間的節(jié)點,即在線段樹最底層的結(jié)點,我們將一個個連續(xù)的區(qū)間離散化成一個結(jié)點旺遮；
}node[maxn<<2];
bool cmp(LINE a,LINE b)
{
    return a.x<b.x;
}
void build(int rt,int l,int r)      //  建樹；
{
    node[rt].l=y[l];    //  維護(hù)區(qū)間盈咳；
    node[rt].r=y[r];
    node[rt].x=-1;
    node[rt].flag=false;
    node[rt].cover=0;
    if(l+1==r){             //  區(qū)間是連續(xù)的;
        node[rt].flag=true; //  標(biāo)記為結(jié)點; 
        return;
    }
    build(lson,l,mid);
    build(rson,mid,r);   //  因為將一個個連續(xù)區(qū)間離散成點耿眉，所以此處mid不需要+1；
}
double Insert_query(int rt,double x,double l,double r,int flag) 
/*查詢+更新x處（l,r）區(qū)間面積鱼响，l和r代表的是區(qū)間查詢區(qū)間的邊界鸣剪，node[rt].l和node[rt].r代表的是結(jié)點邊界*/
{
    if(l>=node[rt].r||r<=node[rt].l) return 0;  //  該方向結(jié)點不包含所要查詢的區(qū)間；
    if(node[rt].flag){  //  找到只有一個區(qū)間的葉子結(jié)點丈积；
        if(node[rt].cover>0){
            double pre=node[rt].x;
            double ans=(x-pre)*(node[rt].r-node[rt].l); //  計算面積筐骇；
            node[rt].x=x;       //  更新定位x位置，便于下次計算面積桶癣；
            node[rt].cover+=flag;   //  更新覆蓋的線段數(shù)拥褂；
            return ans;
        }
        else{
            node[rt].x=x;
            node[rt].cover+=flag;
            return 0;//沒有產(chǎn)生面積并也要return 0 
        }
    }
    double ans1,ans2;
    ans1=Insert_query(lson,x,l,r,flag);    
    ans2=Insert_query(rson,x,l,r,flag); 
    return ans1+ans2;
}
int main()
{
    int Case=0;
    double x1,x2,y1,y2;
    while(~scanf("%d",&n)&&n){
        int cnt=0;
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            y[cnt]=y1;
            line[cnt].x=x1;
            line[cnt].y_down=y1;
            line[cnt].y_up=y2;
            line[cnt++].flag=1;   //  表示左邊線段；
            y[cnt]=y2;
            line[cnt].x=x2;
            line[cnt].y_down=y1;
            line[cnt].y_up=y2;
            line[cnt++].flag=-1;  //  表示右邊線段牙寞；
        }
        sort(y,y+cnt);        //  將所有高度由小到大排序饺鹃，將區(qū)間建樹表示
        sort(line,line+cnt,cmp);      //  因為掃描線從左到右掃描莫秆，所以按照橫坐標(biāo)從小到大排序后逐一插入線段樹
        build(1,0,cnt-1);
        double area=0;
        for(int i=0;i<cnt;i++){
            area+=Insert_query(1,line[i].x,line[i].y_down,line[i].y_up,line[i].flag);
        }
        printf("Test case #%d\nTotal explored area: %.2lf\n\n",++Case,area);
    }
    return 0;
}

HDU 1255 覆蓋的面積(矩形面積交)
題目鏈接:http://acm.split.hdu.edu.cn/showproblem.php?pid=1255
代碼:

#include<bits/stdc++.h>
#define lson (rt<<1)
#define rson ((rt<<1)|1)
#define mid ((l+r)>>1)
#define maxn 2005
using namespace std;
int T,N;


double y[maxn];

struct LINE{
    double x;
    double y_up,y_down;
    int flag;
}line[maxn];

struct node{
    double l,r;
    double x;
    int cover;
    bool flag;
}node[maxn<<2];


bool cmp(LINE a,LINE b){
    return a.x<b.x;
}

void build(int rt,int l,int r){
    node[rt].l=y[l];
    node[rt].r=y[r];
    node[rt].x=-1;
    node[rt].flag=false;
    node[rt].cover=0;
    if(l+1==r){
        node[rt].flag=true;
        return;
    }
    build(lson,l,mid);
    build(rson,mid,r);
}

double Insert_query(int rt,double x,double l,double r,int flag){
    if(l>=node[rt].r||r<=node[rt].l) return 0;
    if(node[rt].flag){
        if(node[rt].cover>1){
            double pre=node[rt].x;
            double ans=(x-pre)*(node[rt].r-node[rt].l);
            node[rt].x=x;
            node[rt].cover+=flag;
            return ans;
        }
        else{
            node[rt].x=x;
            node[rt].cover+=flag;
            return 0; 
        }
    }
    double ans1,ans2;
    ans1=Insert_query(lson,x,l,r,flag);
    ans2=Insert_query(rson,x,l,r,flag);
    return ans1+ans2;
}
int main(){
    scanf("%d",&T);
    while(T--){
        int cnt=0;
        scanf("%d",&N);
        while(N--){
            double x1,y1,x2,y2;
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            y[cnt]=y1;
            line[cnt].x=x1;
            line[cnt].y_down=y1;
            line[cnt].y_up=y2;
            line[cnt++].flag=1;
            y[cnt]=y2;
            line[cnt].x=x2;
            line[cnt].y_down=y1;
            line[cnt].y_up=y2;
            line[cnt++].flag=-1;
        }
        sort(y,y+cnt);
        sort(line,line+cnt,cmp);
        build(1,0,cnt-1);
        double area=0;
        for(int i=0;i<cnt;i++){
            area+=Insert_query(1,line[i].x,line[i].y_down,line[i].y_up,line[i].flag);
        }
        printf("%.2lf\n",area);
        
    }
}