您好,登錄后才能下訂單哦!
這篇文章將為大家詳細講解有關C語言中怎么實現(xiàn)一個樹狀數(shù)組,文章內容質量較高,因此小編分享給大家做個參考,希望大家閱讀完這篇文章后對相關知識有一定的了解。
C語言樹狀數(shù)組的實例詳解
最近學了樹狀數(shù)組,給我的感覺就是 這個數(shù)據(jù)結構好神奇啊^_^
首先她的常數(shù)比線段樹小,其次她的實現(xiàn)復雜度也遠低于線段樹 (并沒有黑線段樹的意思=-=)
所以熟練掌握她是非常有必要的。。
關于樹狀數(shù)組的基礎知識與原理網上一搜一大堆,我就不贅述了,就談一些樹狀數(shù)組的應用好了
1,單點修改,求區(qū)間和
#define lowbit(x) (x&-x) // 設 x 的末尾零的個數(shù)為 y , 則 lowbit(x) == 2^y void Update(int i,int v) // 初始化與單點修改 { while(i <= n) { c[i] += v ; i += lowbit(i) ; } } inline int Sum(int i) // 區(qū)間求和 { int res = 0 ; while(i > 0) { res += c[i] ; i -= lowbit(i) ; } return res ; }
2,區(qū)間修改,單點查詢
這里要用到差分的思想
創(chuàng)建一個差分數(shù)組c[],令c[i] = a[i] - a[i-1] (a[i] 表示原本的第i個數(shù))
則a[i] = ( a[i] - a[i-1] ) + ( a[i-1] - a[i-2] ) + ...... + ( a[2] - a[1] ) +a[1]
= c[i] + c[i-1] + ...... + c[2] + c[1]
所以單點查詢變成了區(qū)間求和
那么區(qū)間修改怎么辦呢 ?
我們看這樣一個例子:
a 1 3 4 5 7 10
c 1 2 1 1 2 3
若我們令區(qū)間[2,4]加2,則
a 1 5 6 7 9 10
c 1 4 1 1 2 1
我們可以發(fā)現(xiàn)只有c[2]和c[5]的數(shù)值改變了,其實原理也很好想,區(qū)間內的前后元素差是不變的,只有(區(qū)間第一個元素與前一個元素的差) 和 (區(qū)間后第一個元素與區(qū)間末尾元素的差) 改變了。所以區(qū)間修改問題變成了單點修改問題。
for(int i=1;i<=n;i++) { a[i] = read() ; Update(i,a[i]-a[i-1]); } /* int x=0,y=0; // 注釋掉的內容是空間上的優(yōu)化(初學者建議先跳過) for(int i=1;i<=n;i++) { if(i%2) { x = read() ; Update(i,x-y); } else { y = read() ; Update(i,y-x) ; } } */ int ii ; int k,x,y; for(int i=1;i<=m;i++) { ii = read() ; if(ii == 1) { x = read() ; y = read() ; k = read() ; Update(x,k); Update(y+1,-k); } if(ii == 2) { x = read() ; printf("%d\n",Sum(x)); } }
關于C語言中怎么實現(xiàn)一個樹狀數(shù)組就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經查實,將立刻刪除涉嫌侵權內容。