第C++高級(jí)數(shù)據(jù)結(jié)構(gòu)之線段樹目錄前言：高級(jí)數(shù)據(jù)結(jié)構(gòu)（Ⅲ）線段樹（SegmentTree）線段樹的原理樹的創(chuàng)建單點(diǎn)修改區(qū)間查找完整代碼及測(cè)試

前言：

高級(jí)數(shù)據(jù)結(jié)構(gòu)（Ⅲ）線段樹（SegmentTree）線段樹的原理樹的創(chuàng)建單點(diǎn)修改區(qū)間查找完整代碼及測(cè)試

高級(jí)數(shù)據(jù)結(jié)構(gòu)（Ⅲ）線段樹（SegmentTree）

線段樹的原理

線段樹是一種二叉搜索樹，對(duì)于線段樹中的每一個(gè)非葉子結(jié)點(diǎn)[a,b]，它的左兒子表示的區(qū)間為[a,(a+b)/2]，右兒子表示的區(qū)間為[(a+b)/2+1,b]。因此線段樹是平衡二叉樹，最后的子節(jié)點(diǎn)數(shù)目為N，即整個(gè)線段區(qū)間的長度，其空間復(fù)雜度為O(n)。

若對(duì)于一個(gè)數(shù)組使用前綴和數(shù)組保存它的區(qū)間和，那么查找區(qū)間和時(shí)間復(fù)雜度為O(1)，而區(qū)間修改時(shí)間復(fù)雜度為O(n)。使用線段樹可以快速查找或修改某個(gè)區(qū)間的值，時(shí)間復(fù)雜度為O(logN)。

線段樹中每一個(gè)結(jié)點(diǎn)代表一個(gè)區(qū)間，對(duì)于區(qū)間【1，7】線段樹的結(jié)構(gòu)如下圖

實(shí)例：

classSegmentTree{

privatestaticfinalint[]tree=newint[1000];

int[]arr;

SegmentTree(){

SegmentTree(int[]arr){

this.arr=arr;

//創(chuàng)建樹···

publicvoidbuildTree(){}

//單點(diǎn)修改更新樹

publicvoidupdateTree(){}

//區(qū)間查找

publicvoidqueryTree(){}

}

樹的創(chuàng)建

給定一個(gè)數(shù)組arr=[6,4,7,5,8,3,9]，創(chuàng)建它對(duì)應(yīng)的線段樹數(shù)組。

對(duì)于一個(gè)結(jié)點(diǎn)k，它的左孩子為2*k，右孩子為2*k+1，此公式適用于根結(jié)點(diǎn)從1開始。但我們?cè)跀?shù)組中存儲(chǔ)元素時(shí)下標(biāo)通常是從0開始的，即根結(jié)點(diǎn)從0開始，此時(shí)它的左孩子為2*k+1，右孩子為2*k+2。

如下圖所示，數(shù)組arr的長度為7，由于樹是以2為基數(shù)的，且線段樹中葉子結(jié)點(diǎn)保存的是arr中單個(gè)結(jié)點(diǎn)的值，我們可以將數(shù)組arr的長度設(shè)想為8（2^3=8，理解為新添了一個(gè)元素0，這對(duì)區(qū)間和并不影響），此時(shí)它對(duì)應(yīng)的線段樹就是一棵結(jié)點(diǎn)數(shù)為15（1+2+4+8）的滿二叉樹。相應(yīng)的結(jié)點(diǎn)值，映射到數(shù)組tree的值在圖中可清晰的看出。

那么，如何用處程序來創(chuàng)建一棵樹呢？

由于線段樹葉子結(jié)點(diǎn)都是數(shù)組arr中的某一元素，所以我們可以使用兩個(gè)變量low和high來標(biāo)記數(shù)組arr的區(qū)間，

若low==high，此時(shí)令tree[node]=arr[low]，并終止遞歸否則，將區(qū)間二分，分別計(jì)算左區(qū)間[low,mid]和右區(qū)間[mid+1,high],并在最后更新tree[node]

實(shí)現(xiàn)：

//創(chuàng)建樹

publicvoidbuildTree(){

this.buildTree(0,0,arr.length-1);

privatevoidbuildTree(intnode,intlow,inthigh){

if(low==high){

tree[node]=arr[low];

return;

intmid=low+(high-low)/2;

intlnode=2*node+1;

intrnode=2*node+2;

buildTree(lnode,low,mid);

buildTree(rnode,mid+1,high);

tree[node]=tree[lnode]+tree[rnode];

}

單點(diǎn)修改

若現(xiàn)在將arr[4]的值修改為1，需要怎樣操作呢？

從下圖綠色標(biāo)出的結(jié)點(diǎn)不難看出其更新過程，先將其所對(duì)應(yīng)的葉子結(jié)點(diǎn)修改，然后繼續(xù)向上修改其父節(jié)點(diǎn)即可。

當(dāng)long==highlow==index時(shí)更新兩個(gè)數(shù)組的值，否則，縮小區(qū)間，在相應(yīng)的區(qū)間搜索，最后更新結(jié)點(diǎn)和即可，相應(yīng)代碼如下

//單點(diǎn)修改更新樹

publicvoidupdateTree(intindex,intval){

this.updateTree(0,0,arr.length-1,index,val);

privatevoidupdateTree(intnode,intlow,inthigh,intindex,intval){

if(low==highlow==index){

arr[index]=val;

tree[node]=val;

return;

intmid=low+(high-low)/2;

intlnode=2*node+1;

intrnode=2*node+2;

if(index=lowindex=mid){

updateTree(lnode,low,mid,index,val);

}else{

updateTree(rnode,mid+1,high,index,val);

tree[node]=tree[lnode]+tree[rnode];

}

區(qū)間查找

若現(xiàn)在查找數(shù)組arr區(qū)間和[3,6]，如何利用線段樹呢？

在線段樹中，我們將它的和劃分為兩個(gè)區(qū)間[3]和[4,6]，如圖中的黃色結(jié)點(diǎn)

下面來看看相關(guān)代碼如何實(shí)現(xiàn)，給定一個(gè)查找區(qū)間[L,R]，同樣使用變量low和high維護(hù)對(duì)數(shù)組arr的二分查找邊界

若當(dāng)前區(qū)間lowR或者h(yuǎn)ighL，說明已超出查找范圍，返回0若[low,high]處于區(qū)間[L,R]內(nèi)，返回當(dāng)前結(jié)點(diǎn)的值tree[node]

然后繼續(xù)在左右區(qū)間查找并保存左右區(qū)間的值sumLeft和sumRight，最后返回sumLeft+sumRight即可

//區(qū)間查找

publicintqueryTree(intL,intR){

returnthis.queryTree(0,0,arr.length-1,L,R);

privateintqueryTree(intnode,intlow,

inthigh,intL,intR){

if(lowR||highL){

return0;

}elseif(low=Lhigh=R){

returntree[node];

intmid=low+(high-low)/2;

intlnode=2*node+1;

intrnode=2*node+2;

intsumleft=queryTree(lnode,low,mid,L,R);

intsumRight=queryTree(rnode,mid+1,high,L,R);

returnsumleft+sumRight;

}

完整代碼及測(cè)試

classSegmentTree{

privatestaticfinalint[]tree=newint[1000];

int[]arr;

SegmentTree(){

SegmentTree(int[]arr){

this.arr=arr;

//創(chuàng)建樹

publicvoidbuildTree(){

this.buildTree(0,0,arr.length-1);

privatevoidbuildTree(intnode,intlow,inthigh){

if(low==high){

tree[node]=arr[low];

return;

intmid=low+(high-low)/2;

intlnode=2*node+1;

intrnode=2*node+2;

buildTree(lnode,low,mid);

buildTree(rnode,mid+1,high);

tree[node]=tree[lnode]+tree[rnode];

//單點(diǎn)修改更新樹

publicvoidupdateTree(intindex,intval){

this.updateTree(0,0,arr.length-1,index,val);

privatevoidupdateTree(intnode,intlow,inthigh,intindex,intval){

if(low==highlow==index){

arr[index]=val;

tree[node]=val;

return;

intmid=low+(high-low)/2;

intlnode=2*node+1;

intrnode=2*node+2;

if(index=lowindex=mid){

updateTree(lnode,low,mid,index,val);

}else{

updateTree(rnode,mid+1,high,index,val);

tree[node]=tree[lnode]+tree[rnode];

//區(qū)間查找

publicintqueryTree(intL,intR){

returnthis.queryTree(0,0,arr.length-1,L,R);

privateintqueryTree(intnode,intlow,inthigh,intL,intR){

if(lowR||highL){

return0;

}elseif(low=Lhigh=R){

returntree[node];

intmid=low+(high-low)/2;

intlnode=2*node+1;

intrnode=2*node+2;

intsumleft=queryTree(lnode,low,mid,L,R);

intsumRight=queryTree(rnode,mid+1,high,L,R);

returnsumleft+sumRight;

//輸出線段樹的值

publicvoidprintTree(){

intsize=15;//size值的大小由arr數(shù)組的大小而定

for(inti=0;isize;i++){

System.out.print(tree[i]+"");

System.out.println();

publicclassSegmentTreeTest{

publicstaticvoidmain(String[]args){

int[]arr={6,4,7,5,8,3,9};

SegmentTreest=newSegmentTree(arr);

//創(chuàng)建線段樹

st.buildTree();

st.printTree();

//422220101211964758300

//查找區(qū)間[3,6]

intsum=st.queryTree(3,6);

System.out.println(sum);

//25

//單點(diǎn)修改更新樹,令arr[4]=1

st.updateTree(4,1);

st.printTree();

//35221310124964751300

}

樹結(jié)點(diǎn)版本：

此版本不使用數(shù)組保存，而是以結(jié)點(diǎn)來保存值，相應(yīng)代碼不難實(shí)現(xiàn)，如下：

importjava.util.ArrayDeque;

importjava.util.Deque;

classSegNode{

intval;

SegNodelnode;

SegNodernode;

SegNode(){}

SegNode(intval){

this.val=val;

classSegTree{

SegNoderoot;

int[]arr;

SegTree(){}

SegTree(int[]arr){

this.arr=arr;

this.bulidTree();

//創(chuàng)建樹

publicvoidbulidTree(){

root=this.buildTree(0,arr.length-1);

privateSegNodebuildTree(intlow,inthigh){

if(low==high){

returnnewSegNode(arr[low]);

SegNodenode=newSegNode();

intmid=low+(high-low)/2;

node.lnode=buildTree(low,mid);

node.rnode=buildTree(mid+1,high);

node.val=node.lnode.val+node.rnode.val;

returnnode;

//單點(diǎn)修改更新樹

publicvoidupdateTree(intindex,intval){

root=updateTree(root,0,arr.length-1,index,val);

privateSegNodeupdateTree(SegNodenode,intlow,inthigh,intindex,intval){

if(low==highlow==index){

arr[index]=val;

node.val=val;

returnnode;

intmid=low+(high-low)/2;

if(index=lowindex=mid){

node.lnode=updateTree(node.lnode,low,mid,index,val);

}else{

node.rnode=updateTree(node.rnode,mid+1,high,index,val);

node.val=node.lnode.val+node.rnode.val;

returnnode;

//查找區(qū)間

publicintqueryTree(intL,intR){

returnqueryTree(root,0,arr.length-1,L,R);

privateintqueryTree(SegNodenode,intlow,inthigh,intL,intR){

if(lowR||highL){

return0;

}elseif(low=Lhigh=R){

returnnode.val;

intmid=low+(high-low)/2;

intsumLeft=queryTree(node.lnode,low,mid,L,R);

intsumRight=queryTree(node.rnode,mid+1,high,L,R);

returnsumLeft+sumRight;

//輸出樹(層次遍歷)

publicvo