線段樹詳解以及C++實現代碼
應用場景
假設有這樣的問題：有n個數，m次操作，操作分為：修改某一個數或者查詢一段區(qū)間的值
分析下，如果針對數組元素的修改可以是O(1)完成，求某個區(qū)間值需要O(n)才可以完成，如果m和n都很大的情況，這個復雜度就很難接受了。
我們之前學過的前綴和算法可以解決區(qū)間求和的問題，并且時間復雜度是O(1)，但如果涉及到修改操作，前綴和數組都需要重新計算，時間復雜度也是O(n)
有沒有什么辦法可以兼顧以上兩種操作，并且可以將時間復雜度降低？
這就是我們要學習的線段樹！把修改和查詢的時間復雜度都降到O(logn)！?。?/strong>
算法思想
先來看下線段樹長什么樣：
有以下數組（為方便計算，數組下標從1開始）
我們把它轉換成線段樹，是長這樣的：
1）葉子結點（綠色）存的都是原數組元素的值
2）每個父結點是它的兩個子節(jié)點的值的和
3）每個父結點記錄它表示區(qū)間的范圍，如上圖的“1-2”表示1到2的區(qū)間
下面我們來看看線段樹是如何降低操作復雜度的！
查詢操作
例如我們需要查詢2-5區(qū)間的和
使用遞歸的思想：
2~5的和
=2~3的和+4~5的和
=3+5+4~5的和
=3+5+11
=19
總之，就是沿著線段樹的劃分把區(qū)間分開，再加到一塊就行啦！
修改操作
例如，我們要把結點2的值由3->5，線段樹需要沿著紅色部分一個一個改，直到根結點：
不管是修改操作還是查詢操作，時間復雜度都是O(logn)
下一步我們來看怎么實現線段樹！
算法實現
首先我們需要將原始數組建立成一顆線段樹，然后在樹的基礎上提供查詢和修改的操作。
建樹
觀察上圖，我們發(fā)現線段樹是一棵近似完全二叉樹，利用完全二叉樹的性質，我們就可以直接用一個數組來存它。
就像上圖一樣把各個節(jié)點標上號，如果根節(jié)點編號是n,那它的左子樹編號是2n,右子樹的編號是2n+1
所以說，知道了根節(jié)點的編號，我們就可以快速有效的找到左右子樹的根節(jié)點
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]區(qū)間里的數，都加上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];
}
?。。。嚎紤]下按區(qū)間修改元素值的復雜度？
注意事項：
1）我們在實現線段樹時，實際存儲肯定大于原始數組，我們一般讓tree數組的長度為原始數據長度的3-4倍。
2）本文只是為了讓大家學習線段樹的實現原理，實際中我們可以將原始數組的start，end使用結構體存儲，這樣更簡潔
總結
到此這篇關于線段樹詳解以及C++實現的文章就介紹到這了,更多相關C++實現線段樹內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C語言約瑟夫環(huán)的實現的相關資料,這里主要是利用數據數據結果中循環(huán)鏈表來實現，需要的朋友可以參考下2017-08-08
C++?使用getline()從文件中讀取一行字符串方法示例
這篇文章主要介紹了C++?使用getline()從文件中讀取一行字符串方法示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-09-09
STL priority_queue（優(yōu)先隊列）詳解
這篇文章主要介紹了 STL priority_queue（優(yōu)先隊列）詳解的相關資料,需要的朋友可以參考下2016-10-10
這篇文章主要介紹了C語言連續(xù)生成隨機數的實現方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-01-01
C語言標準庫中提供了用于大小寫轉換的函數,使得這一操作變得簡單而高效,本文將詳細介紹如何在C語言中進行大小寫字母的轉換,包括相關的函數和示例代碼,需要的朋友可以參考下2024-03-03
這篇文章主要介紹了C++求階乘的兩種方法，有需要的朋友可以參考一下2013-12-12
C語言提供了豐富的標準庫函數,用于處理各種輸入輸出操作,下面這篇文章主要介紹了c語言中比較特殊的輸入函數的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-09-09
這篇文章主要介紹了c++訪問私有private成員變量的常用方法,需要的朋友可以參考下2020-08-08![C++ 動態(tài)內存分配詳解(new/new[]和delete/delete[])](http://img.jbzj.com/images/xgimg/bcimg8.png)
C++ 動態(tài)內存分配詳解(new/new[]和delete/delete[])
這篇文章主要介紹了C++ 動態(tài)內存分配詳解(new/new[]和delete/delete[]),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
學好C++必須做到的50條，絕對經典!想要學好C++的朋友一定要認真閱讀本文，更要做到以下50條2016-09-09