線段樹

線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個(gè)區(qū)間劃分成一些單元區(qū)間，每個(gè)單元區(qū)間對應(yīng)線段樹中的一個(gè)葉結(jié)點(diǎn)。

接下來的幾篇文章我可能會(huì)多總結(jié)一些關(guān)于線段樹的題目、擴(kuò)展及其用法，幫助一些不太懂線段樹的ACMer和未來忘記線段樹的自己……

例題

題目鏈接

題意

中文題題意就不解釋了。下面我們用糖果來進(jìn)行相關(guān)說明，桌上有n堆糖果，給你每堆糖果的初始數(shù)量，然后進(jìn)行一些操作，這些操作可以往指定的糖果堆里放糖果，也可以往指定的糖果堆里拿走糖果，也可以詢問第a~b堆糖果的總數(shù)是多少。對于每次詢問，輸出這幾堆糖果的總數(shù)

導(dǎo)學(xué)

可能讀者以前沒接觸過線段樹，我借這道題形容一下。如果你用數(shù)組來維護(hù)這一堆糖果，那么增加和減少可能比較方便，但是計(jì)算總和的時(shí)候每一次詢問操作都需要重新循環(huán)，肯定就超時(shí)了

那么使用線段樹的好處在哪里呢？比如10堆糖果，它把這線型的10堆糖果變成了樹型。整一棵樹的所有葉節(jié)點(diǎn)存儲(chǔ)的是每一堆糖果的數(shù)量，而其葉節(jié)點(diǎn)的父節(jié)點(diǎn)則存儲(chǔ)了該節(jié)點(diǎn)下所有子節(jié)點(diǎn)的糖果數(shù)的總和。依次往上，根節(jié)點(diǎn)存儲(chǔ)的也就是所有糖果堆的總和

增加/減少糖果時(shí)，找到該糖果所在的葉節(jié)點(diǎn)的位置，更新，并且更新所有與該葉節(jié)點(diǎn)有關(guān)的“父節(jié)點(diǎn)”，在查詢時(shí)，就不需要重新計(jì)算了，將指定父節(jié)點(diǎn)的位置相加即可。

解析

在這題中，首先建立一個(gè)空的線段樹，即假設(shè)每堆糖果的數(shù)量為0

void build(int l,int r,int p){ //構(gòu)造線段樹
    tree[p].left=l;   //節(jié)點(diǎn)所表示的范圍起點(diǎn)
    tree[p].right=r;  //節(jié)點(diǎn)所表示的范圍終點(diǎn)
    tree[p].value=0;  //糖果的數(shù)量初始置0
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,p*2);  //依次建立子節(jié)點(diǎn)，直到處理到葉節(jié)點(diǎn)為止
    build(mid+1,r,p*2+1);
}
……
cin>>n;   //糖果的堆數(shù)
build(1,n,1);

然后得到每一堆糖果的具體數(shù)量。對于每一堆的數(shù)量，其實(shí)就相當(dāng)于在原來置0的情況下，進(jìn)行依次增加操作，往第i堆中增加value個(gè)糖果。

void add(int k,int p,int value){
    if(tree[p].left==k&&tree[p].right==k){   //如果找到了對應(yīng)位置的葉子節(jié)點(diǎn)，就進(jìn)行增加操作
        tree[p].value+=value;
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;  //從子節(jié)點(diǎn)中尋找
    if(k<=mid) add(k,p*2,value);
    else add(k,p*2+1,value);
    tree[p].value = tree[2*p].value+tree[2*p+1].value;  //子節(jié)點(diǎn)更新了，父節(jié)點(diǎn)也要更新
}
……
for(i=1;i<=n;i++){
    scanf("%d",&num);
    add(i,1,num);
}

然后，在上述操作的基礎(chǔ)上，我們發(fā)現(xiàn)已經(jīng)解決了題目要求的增加和減少的命令了，因?yàn)闇p少n等于增加-n。還有最后一個(gè)查詢的操作，也就是查詢a~b堆的總數(shù)

void search(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r){  //如果這個(gè)節(jié)點(diǎn)的范圍完全吻合所需要查找的范圍
        sum+=tree[p].value;  //直接增加
        return;   //加完就跑
    }
    //如果這個(gè)節(jié)點(diǎn)的范圍不滿足怎么辦？
    int mid = (tree[p].left+tree[p].right)/2;  //取當(dāng)前范圍的中點(diǎn)
    if(r<=mid) search(l,r,2*p);  //如果所求范圍在中點(diǎn)左邊，往左子樹找
    else if(l>mid) search(l,r,2*p+1);  //如果所求范圍在中點(diǎn)右邊，往右子樹找
    else{
        //如果mid在所有范圍當(dāng)中，也就是左子樹也有，右子樹也有，那就都找，但是需要處理一下范圍，不能直接傳遞l和r
        search(l,mid,2*p);
        search(mid+1,r,2*p+1);
    }
}
……
sum=0;
search(num1,num2,1);
cout<<sum<<endl;

上面的查詢操作也是這個(gè)代碼的核心操作，和數(shù)組查詢不同的是，數(shù)組查詢每次都是在查詢?nèi)~節(jié)點(diǎn)，而線段樹幾乎不會(huì)到葉節(jié)點(diǎn)，總是到某個(gè)父節(jié)點(diǎn)就停下了，所以大大減少了操作次數(shù)

AC代碼

#include <iostream>
#include <string.h>
#include <stdio.h>
#define M 50005
using namespace std;
int sum;
struct node{
    int left;
    int right;
    int value;
}tree[4*M]; //大小為預(yù)定長度的4倍
void build(int l,int r,int p){ //構(gòu)造線段樹
    tree[p].left=l;   //節(jié)點(diǎn)所表示的范圍起點(diǎn)
    tree[p].right=r;  //節(jié)點(diǎn)所表示的范圍終點(diǎn)
    tree[p].value=0;  //糖果的數(shù)量初始置0
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,p*2);  //依次建立子節(jié)點(diǎn)，直到處理到葉節(jié)點(diǎn)位置
    build(mid+1,r,p*2+1);
}
void add(int k,int p,int value){
    if(tree[p].left==k&&tree[p].right==k){   //如果找到了對應(yīng)位置的葉子節(jié)點(diǎn)，就進(jìn)行增加操作
        tree[p].value+=value;
        return;
    }
    int mid=(tree[p].left+tree[p].right)/2;  //從子節(jié)點(diǎn)中尋找
    if(k<=mid) add(k,p*2,value);
    else add(k,p*2+1,value);
    tree[p].value = tree[2*p].value+tree[2*p+1].value;  //子節(jié)點(diǎn)更新了，父節(jié)點(diǎn)也要更新
}
void search(int l,int r,int p){
    if(tree[p].left==l&&tree[p].right==r){  //如果這個(gè)節(jié)點(diǎn)的范圍完全吻合所需要查找的范圍
        sum+=tree[p].value;  //直接增加
        return;   //加完就跑
    }
    //如果這個(gè)節(jié)點(diǎn)的范圍不滿足怎么辦？
    int mid = (tree[p].left+tree[p].right)/2;  //取當(dāng)前范圍的中點(diǎn)
    if(r<=mid) search(l,r,2*p);  //如果所求范圍在中點(diǎn)左邊，往左子樹找
    else if(l>mid) search(l,r,2*p+1);  //如果所求范圍在終點(diǎn)右邊，往右子樹找
    else{   //如果mid在所有范圍當(dāng)中，也就是左子樹也有，右子樹也有，那就都找，但是需要處理一下范圍，不能直接傳遞l和r
        search(l,mid,2*p);
        search(mid+1,r,2*p+1);
    }
}
int main(){
    char str[10];
    int T,n,i,k,num,num1,num2;
    cin>>T;
    for(k=1;k<=T;k++){
        cin>>n;   //堆數(shù)
        build(1,n,1);
        for(i=1;i<=n;i++){
            scanf("%d",&num);
            add(i,1,num);
        }
        cout<<"Case "<<k<<":"<<endl;
        while(scanf("%s",str)&&strcmp(str,"End")!=0){
            scanf("%d%d",&num1,&num2);
            if(strcmp(str,"Add")==0)
                add(num1,1,num2);
            else if(strcmp(str,"Sub")==0)
                add(num1,1,-num2);
            else{
                sum=0;
                search(num1,num2,1);
                cout<<sum<<endl;
            }
        }
    }
    return 0;
}