C++怎么實現線段樹

本篇內容介紹了“C++怎么實現線段樹”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

目錄

• 應用場景

• 算法思想

• 查詢操作

• 修改操作

• 算法實現

• 建樹

• 查詢

• 修改

  
  

應用場景

假設有這樣的問題：有n個數，m次操作，操作分為：修改某一個數或者查詢一段區間的值

分析下，如果針對數組元素的修改可以是O(1)完成，求某個區間值需要O(n)才可以完成，如果m和n都很大的情況，這個復雜度就很難接受了。

我們之前學過的前綴和算法可以解決區間求和的問題，并且時間復雜度是O(1)，但如果涉及到修改操作，前綴和數組都需要重新計算，時間復雜度也是O(n)

有沒有什么辦法可以兼顧以上兩種操作，并且可以將時間復雜度降低？

這就是我們要學習的線段樹！把修改和查詢的時間復雜度都降到O(logn)！！！

算法思想

先來看下線段樹長什么樣：

有以下數組（為方便計算，數組下標從1開始）

我們把它轉換成線段樹，是長這樣的：

1）葉子結點（綠色）存的都是原數組元素的值

2）每個父結點是它的兩個子節點的值的和

3）每個父結點記錄它表示區間的范圍，如上圖的“1-2”表示1到2的區間

下面我們來看看線段樹是如何降低操作復雜度的！

查詢操作

例如我們需要查詢2-5區間的和

使用遞歸的思想：

2~5的和

=2~3的和+4~5的和

=3+5+4~5的和

=3+5+11

=19

總之，就是沿著線段樹的劃分把區間分開，再加到一塊就行啦！

修改操作

例如，我們要把結點2的值由3->5，線段樹需要沿著紅色部分一個一個改，直到根結點：

不管是修改操作還是查詢操作，時間復雜度都是O(logn)

下一步我們來看怎么實現線段樹！

算法實現

首先我們需要將原始數組建立成一顆線段樹，然后在樹的基礎上提供查詢和修改的操作。

建樹

觀察上圖，我們發現線段樹是一棵近似完全二叉樹，利用完全二叉樹的性質，我們就可以直接用一個數組來存它。

就像上圖一樣把各個節點標上號，如果根節點編號是n,那它的左子樹編號是2n,右子樹的編號是2n+1

所以說，知道了根節點的編號，我們就可以快速有效的找到左右子樹的根節點

void build(int root,int start,int end){
    if(start == end){
        tree[root] = num[start];
        return;
    }
    int leftroot = root * 2;//左結點
    int rightroot = root * 2 + 1;//右結點
    int mid = (start+end)/2;
    build(leftroot,start,mid);//遞歸計算左結點
    build(rightroot,mid+1,end);//遞歸計算右結點
    tree[root] = tree[leftroot] + tree[rightroot];//根結點值=左根+右根
}

查詢

int query(int root,int start,int end,int l,int r){
    if(l<=start && r>= end){
        return tree[root];
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    int sum = 0;
    if(l<=mid){
        sum += query(leftroot,start,mid,l,r);
    }
    if(r>mid){
        sum += query(rightroot,mid+1,end,l,r);
    }
    return sum;
}

修改

/**
* 修改[l,r]區間里的數，都加上k值
* @param root
* @param start
* @param end
* @param l
* @param r
* @param k
*/
void update(int root,int start,int end,int l,int r,int k){
    if(start == end){
        tree[root] += k;
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    if(l<=mid){
        update(leftroot,start,mid,l,r,k);
    }
    if(r>mid){
        update(rightroot,mid+1,end,l,r,k);
    }
    tree[root] = tree[leftroot] + tree[rightroot];
}

！！！：考慮下按區間修改元素值的復雜度？

注意事項：

1）我們在實現線段樹時，實際存儲肯定大于原始數組，我們一般讓tree數組的長度為原始數據長度的3-4倍。

2）本文只是為了讓大家學習線段樹的實現原理，實際中我們可以將原始數組的start，end使用結構體存儲，這樣更簡潔

“C++怎么實現線段樹”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！