這篇文章主要介紹“C++如何實(shí)現(xiàn)線段樹”，在日常操作中，相信很多人在C++如何實(shí)現(xiàn)線段樹問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”C++如何實(shí)現(xiàn)線段樹”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
成都創(chuàng)新互聯(lián)是專業(yè)的金東網(wǎng)站建設(shè)公司，金東接單;提供成都做網(wǎng)站、成都網(wǎng)站制作,網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行金東網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!
假設(shè)有這樣的問題：有n個(gè)數(shù)，m次操作，操作分為：修改某一個(gè)數(shù)或者查詢一段區(qū)間的值
分析下，如果針對數(shù)組元素的修改可以是O(1)完成，求某個(gè)區(qū)間值需要O(n)才可以完成，如果m和n都很大的情況，這個(gè)復(fù)雜度就很難接受了。
我們之前學(xué)過的前綴和算法可以解決區(qū)間求和的問題，并且時(shí)間復(fù)雜度是O(1)，但如果涉及到修改操作，前綴和數(shù)組都需要重新計(jì)算，時(shí)間復(fù)雜度也是O(n)
有沒有什么辦法可以兼顧以上兩種操作，并且可以將時(shí)間復(fù)雜度降低？
這就是我們要學(xué)習(xí)的線段樹！把修改和查詢的時(shí)間復(fù)雜度都降到O(logn)?。?！
先來看下線段樹長什么樣：
有以下數(shù)組（為方便計(jì)算，數(shù)組下標(biāo)從1開始）
我們把它轉(zhuǎn)換成線段樹，是長這樣的：
1）葉子結(jié)點(diǎn)（綠色）存的都是原數(shù)組元素的值
2）每個(gè)父結(jié)點(diǎn)是它的兩個(gè)子節(jié)點(diǎn)的值的和
3）每個(gè)父結(jié)點(diǎn)記錄它表示區(qū)間的范圍，如上圖的“1-2”表示1到2的區(qū)間
下面我們來看看線段樹是如何降低操作復(fù)雜度的！
例如我們需要查詢2-5區(qū)間的和
使用遞歸的思想：
2~5的和
=2~3的和+4~5的和
=3+5+4~5的和
=3+5+11
=19
總之，就是沿著線段樹的劃分把區(qū)間分開，再加到一塊就行啦！
例如，我們要把結(jié)點(diǎn)2的值由3->5，線段樹需要沿著紅色部分一個(gè)一個(gè)改，直到根結(jié)點(diǎn)：
不管是修改操作還是查詢操作，時(shí)間復(fù)雜度都是O(logn)
下一步我們來看怎么實(shí)現(xiàn)線段樹！
首先我們需要將原始數(shù)組建立成一顆線段樹，然后在樹的基礎(chǔ)上提供查詢和修改的操作。
觀察上圖，我們發(fā)現(xiàn)線段樹是一棵近似完全二叉樹，利用完全二叉樹的性質(zhì)，我們就可以直接用一個(gè)數(shù)組來存它。
就像上圖一樣把各個(gè)節(jié)點(diǎn)標(biāo)上號(hào)，如果根節(jié)點(diǎn)編號(hào)是n,那它的左子樹編號(hào)是2n,右子樹的編號(hào)是2n+1
所以說，知道了根節(jié)點(diǎn)的編號(hào)，我們就可以快速有效的找到左右子樹的根節(jié)點(diǎn)
重慶分公司
重慶分公司
void build(int root,int start,int end){
if(start == end){
tree[root] = num[start];
return;
}
int leftroot = root * 2;//左結(jié)點(diǎn)
int rightroot = root * 2 + 1;//右結(jié)點(diǎn)
int mid = (start+end)/2;
build(leftroot,start,mid);//遞歸計(jì)算左結(jié)點(diǎn)
build(rightroot,mid+1,end);//遞歸計(jì)算右結(jié)點(diǎn)
tree[root] = tree[leftroot] + tree[rightroot];//根結(jié)點(diǎn)值=左根+右根
}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ū)間里的數(shù)，都加上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];
}到此，關(guān)于“C++如何實(shí)現(xiàn)線段樹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
