數據結構——線段樹的基礎知識

#include
#include

typedef struct node Node;

struct node{
    int leftvalue;
    int rightvalue;      //分別用來記錄節點記錄的區間范圍
    Node *lchild;     //左孩子節點
    Node *rchild;    //右孩子節點
};

int flag = 1;      //用於標記當前遍歷到哪個節點
//節點的初始化
Node *Init(Node *_node,int lvalue,int rvalue){
    _node = (Node *)malloc(sizeof(Node));
    _node -> lchild = NULL;
    _node -> rchild = NULL;
    _node -> leftvalue = lvalue;
    _node -> rightvalue = rvalue;
    return _node;
}

//由區間[left,right]建立一棵線段樹

Node *Build(Node *_root,int left,int right){
    _root = Init(_root,left,right);    //節點初始化
    if(left != right){            //遞歸終止條件,表示已經線段樹建立到了葉節點
        _root -> lchild = Build(_root -> lchild,left,(left + right) / 2);
        _root -> rchild = Build(_root -> rchild,(left + right)/2+1,right);
    }
    return _root;        //回溯至最後一層時,則返回整棵樹的根節點
}

//中序遍歷,便於從左往右查看各節點存儲的線段區間

void inorder(Node *_node){
    if(_node){
        inorder(_node -> lchild);
        printf("第%d個遍歷的節點,存儲區間為:[%d,%d]\n",flag++,_node -> leftvalue,_node -> rightvalue);
        inorder(_node -> rchild);
    }
}

int main(){
    Node *root;
    root = Build(root,1,10);
    inorder(root);
    return 0;
}

我們發現，存儲的結果與一開始定義的完全一致，於是我們便成功的建立好了一棵空的線段樹。

3.線段樹的一些簡單應用：

(1).區間查詢問題：

我們以RMQ為例，即在給定區間內查詢最小值，假設我們已經將對應區間的最小值存入了線段樹的節點中，那麼我們利用剛剛

建立好的線段樹來解決這一問題，如果查詢的區間是[1,2],[3,3]這樣的區間，那麼我們直接找到對應節點解決這一問題即可。但是如

果查詢的區間是[1,6],[2,7]這樣的區間時，我們可以發現在線段樹中，無法找到這樣的節點，但是呢，我們可以找到樹中哪幾個節點

能夠組成我們所要求的區間，然後再取這幾個區間內的最小值不就解決問題了嗎？因此有了這樣的想法，我們對於任何在合理范圍

內的查詢，都可以找到若干個相連的區間，然後將這若干個區間合並，得到待求的區間。

通常，我們用來尋找這樣的一個區間的簡單辦法是：

function 在節點v查詢區間[l,r]

ifv所表示的區間和[l,r]交集不為空集 ifv所表示的區間完全屬於[l,r]

選取v

else

在節點v的左右兒子分別查詢區間[l,r]end if end if

偽代碼出自《線段樹》講稿 楊戈

因此根據以上偽代碼我們可以得出以下完整代碼：

#include
#include

typedef struct node Node;

struct node{
    int leftvalue;
    int rightvalue;      //分別用來記錄節點記錄的區間范圍
    Node *lchild;     //左孩子節點
    Node *rchild;    //右孩子節點
};

int flag = 1;      //用於標記當前遍歷到哪個節點
//節點的初始化
Node *Init(Node *_node,int lvalue,int rvalue){
    _node = (Node *)malloc(sizeof(Node));
    _node -> lchild = NULL;
    _node -> rchild = NULL;
    _node -> leftvalue = lvalue;
    _node -> rightvalue = rvalue;
    return _node;
}

//由區間[left,right]建立一棵線段樹

Node *Build(Node *_root,int left,int right){
    _root = Init(_root,left,right);    //節點初始化
    if(left != right){            //遞歸終止條件,表示已經線段樹建立到了葉節點
        _root -> lchild = Build(_root -> lchild,left,(left + right) / 2);
        _root -> rchild = Build(_root -> rchild,(left + right)/2+1,right);
    }
    return _root;        //回溯至最後一層時,則返回整棵樹的根節點
}

//中序遍歷,便於從左往右查看各節點存儲的線段區間

void inorder(Node *_node){
    if(_node){
        inorder(_node -> lchild);
        printf("第%d個遍歷的節點,存儲區間為:[%d,%d]\n",flag++,_node -> leftvalue,_node -> rightvalue);
        inorder(_node -> rchild);
    }
}

/**用於查詢一個給定的區間是由線段樹中哪幾個子區間構成的,為了簡化代碼,
 **因此保證輸入的區間范圍合法,這裡就不作輸入的合法性判斷了
 */
void Query(Node *_node,int left,int right){
    /**要查詢一個給定的區間是由線段樹中哪幾個子區間構成的
     **首先要滿足的是當前遍歷到的區間要和待查詢區間有交集,
     **否則的話不再繼續往當前節點的孩子節點繼續遍歷,原因很簡單
     **每個孩子節點存儲的區間范圍都是包含於父親節點的,父親節點與
     **待查詢區間無交集的話,則孩子節點一定無交集
     **/
     if(right >= _node -> leftvalue && left <= _node -> rightvalue){
        /**如果當前遍歷到的線段樹區間完全屬於待查詢區間,
         **那麼選取該區間,否則的話,繼續縮小范圍,
         **在當前節點的左孩子和右孩子節點繼續尋找
         **/
        if(left <= _node -> leftvalue && right >= _node -> rightvalue){
            printf("[%d,%d]\n",_node -> leftvalue,_node -> rightvalue);
        }
        else{
            Query(_node -> lchild,left,right);
            Query(_node -> rchild,left,right);
        }
     }

}

int main(){
    Node *root;
    root = Build(root,1,10);
    inorder(root);
    printf("區間[2,7]由線段樹中以下區間構成:\n");
    Query(root,2,7);
    return 0;
}

有了以上的區間拆分操作，那麼我們求解區間查詢最值問題就游刃有余了，聰明的你可以自己實現以下，O(∩_∩)O~

（2）.區間修改操作：

在這裡我們依然以RMQ問題為例，假如一開始的時候，線段樹中每個節點的權值都是1，那麼現在我要做的是，指定一個合法

的區間，然後對這個區間內所有的數加上或者減去某個數，如果我們按照區間的內的數一一的去遍歷並修改線段樹的節點的話，那

麼改動的節點數必然遠遠超過O(logn)個，而且會存在大量的重復遍歷操作，那麼要怎麼樣才能提高程序的效率呢？

首先，我們考慮給定的修改區間，按照前面我們討論過的問題，我們可以把待操作區間變成幾個相連的子區間，那麼我們試

想，當我們要修改一個給定區間時，我們對其所有子區間進行修改，這樣的話不就把整個待修改區間處理完畢了嗎？這樣的話

我們是否可以只通過修改幾個子區間節點的值，而不考慮它們的孩子節點，就完成所有的操作了呢？

實際上，如果不考慮這些子區間的孩子節點的話，是錯誤的，因為在父親節點所帶的權值發生變化時，比如說上圖示中區間

[1,2]中每個值都加上5，那麼我們把線段樹中表示區間[1,2]的節點修改完畢是否就可以了呢？答案顯然是錯誤的，因為該節點的左孩

子([1,1])和右孩子節點所表示的區間([2,2])中的值也都發生了變化。

所以在這裡我們為了方便，我們在節點定義中加入一個標記的量，用來存儲對節點的修改情況。顯然，當我們自上而下的訪

問某節點時，父親節點的標記要"傳給"孩子節點，即修改大的區間，其子區間也必然被改動。

有了以上的分析，我們可以總結操作：

首先找到樹中哪幾個節點表示的區間，能夠組成我們待修改的區間，然後從這些節點開始向下遍歷，將以這些節點為根節點

的子樹節點權值做相應的改變。（邊查找對應子區間，邊修改權值）

完整代碼如下：

#include
#include

typedef struct node Node;

struct node{
    int leftvalue;
    int rightvalue;      //分別用來記錄節點記錄的區間范圍
    Node *lchild;     //左孩子節點
    Node *rchild;    //右孩子節點
    int weight;      //表示節點的權值
    int mark;        //表示當前節點改變的值(權重加減處理)
};

int flag = 1;      //用於標記當前遍歷到哪個節點
//節點的初始化
Node *Init(Node *_node,int lvalue,int rvalue){
    _node = (Node *)malloc(sizeof(Node));
    _node -> lchild = NULL;
    _node -> rchild = NULL;
    _node -> leftvalue = lvalue;
    _node -> rightvalue = rvalue;
    _node -> weight = 1;          //為了方便,一開始的時候,線段樹每個節點的權值都設為1
    _node -> mark = 0;            //初始狀態時,所有節點的權重均為1,因此一開始的時候,線段樹每個節點的標記均為0
    return _node;
}

//由區間[left,right]建立一棵線段樹

Node *Build(Node *_root,int left,int right){
    _root = Init(_root,left,right);    //節點初始化
    if(left != right){            //遞歸終止條件,表示已經線段樹建立到了葉節點
        _root -> lchild = Build(_root -> lchild,left,(left + right) / 2);
        _root -> rchild = Build(_root -> rchild,(left + right)/2+1,right);
    }
    return _root;        //回溯至最後一層時,則返回整棵樹的根節點
}

//中序遍歷,便於從左往右查看各節點存儲的線段區間

void inorder(Node *_node){
    if(_node){
        inorder(_node -> lchild);
        printf("\n第%d個遍歷的節點,存儲區間為:[%d,%d]\n",flag,_node -> leftvalue,_node -> rightvalue);
        printf("\n第%d個遍歷的節點,權值為%d,標記為%d\n",flag++,_node -> weight,_node -> mark);
        inorder(_node -> rchild);
    }
}

/**用於查詢一個給定的區間是由線段樹中哪幾個子區間構成的,為了簡化代碼,
 **因此保證輸入的區間范圍合法,這裡就不作輸入的合法性判斷了
 */
void Query(Node *_node,int left,int right){
    /**要查詢一個給定的區間是由線段樹中哪幾個子區間構成的
     **首先要滿足的是當前遍歷到的區間要和待查詢區間有交集,
     **否則的話不再繼續往當前節點的孩子節點繼續遍歷,原因很簡單
     **每個孩子節點存儲的區間范圍都是包含於父親節點的,父親節點與
     **待查詢區間無交集的話,則孩子節點一定無交集
     **/
     if(right >= _node -> leftvalue && left <= _node -> rightvalue){
        /**如果當前遍歷到的線段樹區間完全屬於待查詢區間,
         **那麼選取該區間,否則的話,繼續縮小范圍,
         **在當前節點的左孩子和右孩子節點繼續尋找
         **/
        if(left <= _node -> leftvalue && right >= _node -> rightvalue){
            printf("[%d,%d]\n",_node -> leftvalue,_node -> rightvalue);
        }
        else{
            Query(_node -> lchild,left,right);
            Query(_node -> rchild,left,right);
        }
     }

}

/**對指定區間的值進行增添操作,顯然,當某個子區間的值進行修改了之後
 **以該節點為根節點的子樹區間的值均要修改
 **/

void change(Node *node){
    if(node){
        if(node -> lchild){
            node -> lchild -> mark += node -> mark;
            node -> lchild -> weight += node -> lchild -> mark;
            change(node -> lchild);
        }
        if(node -> rchild){
            node -> rchild -> mark += node -> mark;
            node -> rchild -> weight += node -> rchild -> mark;
            change(node -> rchild);
        }
    }
}

/**更改某個區間的權值,整棵線段樹節點值的變化為了簡化代碼,
 **因此保證輸入的區間范圍合法,這裡就不作輸入的合法性判斷，pos表示增減操作的值
 **/
void update(Node *node,int left,int right,int pos){

    //先查找待處理區間的組成區間,再修改區間的權值
    if(right >= node -> leftvalue && left <= node -> rightvalue){
        if(left <= node -> leftvalue && right >= node -> rightvalue){
            node -> mark = pos;
            node -> weight += node -> mark;
            //修改以該節點為根的子樹所有節點的權值和標記
            change(node);
        }
        else{
            update(node -> lchild,left,right,pos);
            update(node -> rchild,left,right,pos);
        }
     }
}



int main(){
    Node *root;
    root = Build(root,1,4);
    //[1,3]中每個數都加上5;
    update(root,1,3,5);
    inorder(root);
    return 0;
}

運行結果：

線段樹初學，有錯誤和不足之處還望指正，O(∩_∩)O謝謝，後續在深入學習的過程中，還會增加更多的關於線段樹的文章，

或者對本文中的應用范圍再進行擴充。