數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)領(lǐng)域本科教育教學(xué)改革試點(diǎn)工作計(jì)劃（“101計(jì)劃”）研究成果10112.2樹狀數(shù)組第12章

高級(jí)查找12.2.1樹狀數(shù)組的用途12.2.2樹狀數(shù)組的lowbit運(yùn)算12.2.3樹狀數(shù)組區(qū)間求和12.2.4小結(jié)12.2.5作業(yè)12.2.1樹狀數(shù)組的用途12.2.1樹狀數(shù)組的用途數(shù)據(jù)結(jié)構(gòu)一種用于高效處理動(dòng)態(tài)數(shù)組前綴和查詢的數(shù)據(jù)結(jié)構(gòu)。它主要用于求解頻繁更新單個(gè)元素值、以及在給定索引位置計(jì)算前綴和的問題。樹狀數(shù)組的主要用途單點(diǎn)修改：更改指定元素ai的值區(qū)間求和：計(jì)算第i個(gè)元素到第j個(gè)元素的和(1)單點(diǎn)修改：O(1)(2)區(qū)間求和:O(n)(1)單點(diǎn)修改:O(n)(2)區(qū)間求和:O(1)簡(jiǎn)單循環(huán)操作預(yù)處理求前綴和:

時(shí)間復(fù)雜度分析12.2.3樹狀數(shù)組的lowbit運(yùn)算12.2.2樹狀數(shù)組的lowbit運(yùn)算數(shù)據(jù)結(jié)構(gòu)Lowbit(k)將k的二進(jìn)制表示中最低位的1保留，其余位都變?yōu)?.在計(jì)算機(jī)整數(shù)的補(bǔ)碼表示中，-k的二進(jìn)制表示是k的二進(jìn)制表示各位取反后再加一；因此，-k與k僅在Lowbit(k)所對(duì)應(yīng)的最低位二進(jìn)制位上同時(shí)為1，其余各位上都是相反的。所以，可以用位運(yùn)算k&-k快速計(jì)算出Lowbit(k)。12.2.3樹狀數(shù)組的區(qū)間求和12.2.3樹狀數(shù)組的區(qū)間求和數(shù)據(jù)結(jié)構(gòu)n=8的樹狀數(shù)組12.2.3樹狀數(shù)組的區(qū)間求和數(shù)據(jù)結(jié)構(gòu)12.2.3樹狀數(shù)組的區(qū)間求和算法：

樹狀數(shù)組區(qū)間求和GetS(c,k)輸入：樹狀數(shù)組c，整數(shù)下標(biāo)k30輸出：前綴和數(shù)組S第k項(xiàng)sk的值1sum←02while

k≠0do

3|sum←sum+c[k]4|k←k–Lowbit(k)//即k=f(x)5end6return

sum樹狀數(shù)組區(qū)間求和算法描述12.2.3樹狀數(shù)組的區(qū)間求和數(shù)據(jù)結(jié)構(gòu)12.2.3樹狀數(shù)組的區(qū)間求和樹狀數(shù)組單點(diǎn)修改a[k]修改，則

的c[i]的值都會(huì)改變所有符合條件的i可以由

得到。算法：

樹狀數(shù)組單點(diǎn)修改的偽代碼：Update(c,n,k,d)輸入：樹狀數(shù)組c，數(shù)組總長(zhǎng)度n，擬修改的元素位置k，擬修改增加值d輸出：更新后的樹狀數(shù)組c1while

k≤n

do//當(dāng)超出數(shù)組總長(zhǎng)度時(shí)停止2|c[k]←c[k]+d3|k←k+Lowbit(k)//即k=g(k)4end12.2.3樹狀數(shù)組的區(qū)間求和數(shù)據(jù)結(jié)構(gòu)12.2.3樹狀數(shù)組的區(qū)間求和

已知數(shù)組A=[6,8,1,4,7,3]，請(qǐng)建立樹狀數(shù)組并根據(jù)樹狀數(shù)組求出[2,5]的和值。樹狀數(shù)組例題12.2.3樹狀數(shù)組的區(qū)間求和數(shù)據(jù)結(jié)構(gòu)12.2.3樹狀數(shù)組的區(qū)間求和S[2,5]=S[5]-S[1]S[5]=C[5]+Sf[5]=C[5]+S[4]=C[5]+C[4]+Sf[4]=C[5]+C[4]=19+7=26S[1]=C[1]+Sf[1]=C[1]=6S[2,5]=26-6=20答案：12.2.3樹狀數(shù)組小結(jié)數(shù)據(jù)結(jié)構(gòu)12.2.4樹狀數(shù)組小結(jié)樹狀數(shù)組的本質(zhì)是通過一種巧妙的基于二進(jìn)制的方法劃分出n個(gè)區(qū)間，使得任意前綴區(qū)間都可以由這n個(gè)區(qū)間中不超過

個(gè)區(qū)間組合而成，且每一個(gè)元素最多被這n個(gè)區(qū)間中的

個(gè)區(qū)間包含。

樹狀數(shù)組最適合求區(qū)間和或區(qū)間積。事實(shí)上，只要任一區(qū)間內(nèi)的計(jì)算可以通過兩個(gè)前綴計(jì)算的逆運(yùn)算得到就可以，例如減法是加法的逆運(yùn)算，除法是乘法的逆運(yùn)算等等。但像求區(qū)間最大值、最小值這種運(yùn)算，就還是用線段樹比較方便了。12.2.3樹狀數(shù)組作業(yè)數(shù)據(jù)結(jié)構(gòu)12.2.5樹狀數(shù)組作業(yè)樹狀數(shù)組的本質(zhì)是通過一種巧妙的基于二進(jìn)制的方法劃分出n個(gè)區(qū)間，使得任意前綴區(qū)間都可以由這n個(gè)區(qū)間中不超過

個(gè)區(qū)間組合而成，且每一個(gè)元素最多被這n個(gè)區(qū)間中的

個(gè)區(qū)間包含。

樹狀數(shù)組最適合求區(qū)間和或區(qū)間積。事實(shí)上，只要任一區(qū)間內(nèi)的計(jì)算可以通過兩個(gè)前綴計(jì)算的逆運(yùn)算得到就可以，例如減法是加法的逆運(yùn)算，除法是乘法的逆運(yùn)算等等。但像求區(qū)間最大值、最小值這種運(yùn)算，就還是用線段樹比較方便了。12.1.5