您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++怎么實(shí)現(xiàn)線段樹”的有關(guān)知識,在實(shí)際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
應(yīng)用場景
算法思想
查詢操作
修改操作
算法實(shí)現(xiàn)
建樹
查詢
修改
假設(shè)有這樣的問題:有n個數(shù),m次操作,操作分為:修改某一個數(shù)或者查詢一段區(qū)間的值
分析下,如果針對數(shù)組元素的修改可以是O(1)完成,求某個區(qū)間值需要O(n)才可以完成,如果m和n都很大的情況,這個復(fù)雜度就很難接受了。
我們之前學(xué)過的前綴和算法可以解決區(qū)間求和的問題,并且時間復(fù)雜度是O(1),但如果涉及到修改操作,前綴和數(shù)組都需要重新計(jì)算,時間復(fù)雜度也是O(n)
有沒有什么辦法可以兼顧以上兩種操作,并且可以將時間復(fù)雜度降低?
這就是我們要學(xué)習(xí)的線段樹!把修改和查詢的時間復(fù)雜度都降到O(logn)!??!
先來看下線段樹長什么樣:
有以下數(shù)組(為方便計(jì)算,數(shù)組下標(biāo)從1開始)
我們把它轉(zhuǎn)換成線段樹,是長這樣的:
1)葉子結(jié)點(diǎn)(綠色)存的都是原數(shù)組元素的值
2)每個父結(jié)點(diǎn)是它的兩個子節(jié)點(diǎn)的值的和
3)每個父結(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,線段樹需要沿著紅色部分一個一個改,直到根結(jié)點(diǎn):
不管是修改操作還是查詢操作,時間復(fù)雜度都是O(logn)
下一步我們來看怎么實(shí)現(xiàn)線段樹!
首先我們需要將原始數(shù)組建立成一顆線段樹,然后在樹的基礎(chǔ)上提供查詢和修改的操作。
觀察上圖,我們發(fā)現(xiàn)線段樹是一棵近似完全二叉樹,利用完全二叉樹的性質(zhì),我們就可以直接用一個數(shù)組來存它。
就像上圖一樣把各個節(jié)點(diǎn)標(biāo)上號,如果根節(jié)點(diǎn)編號是n,那它的左子樹編號是2n,右子樹的編號是2n+1
所以說,知道了根節(jié)點(diǎn)的編號,我們就可以快速有效的找到左右子樹的根節(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]; }
?。。。嚎紤]下按區(qū)間修改元素值的復(fù)雜度?
注意事項(xiàng):
1)我們在實(shí)現(xiàn)線段樹時,實(shí)際存儲肯定大于原始數(shù)組,我們一般讓tree數(shù)組的長度為原始數(shù)據(jù)長度的3-4倍。
2)本文只是為了讓大家學(xué)習(xí)線段樹的實(shí)現(xiàn)原理,實(shí)際中我們可以將原始數(shù)組的start,end使用結(jié)構(gòu)體存儲,這樣更簡潔
“C++怎么實(shí)現(xiàn)線段樹”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。