C語言樹狀數組的實例詳解
最近學了樹狀數組，給我的感覺就是 這個數據結構好神奇啊^_^
首先她的常數比線段樹小，其次她的實現復雜度也遠低于線段樹 （并沒有黑線段樹的意思=-=）
所以熟練掌握她是非常有必要的。。
關于樹狀數組的基礎知識與原理網上一搜一大堆，我就不贅述了，就談一些樹狀數組的應用好了
1，單點修改，求區間和
#define lowbit(x) (x&-x) // 設 x 的末尾零的個數為 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) // 區間求和 { int res = 0 ; while(i > 0) { res += c[i] ; i -= lowbit(i) ; } return res ;}2，區間修改，單點查詢
這里要用到差分的思想
創建一個差分數組c[]，令c[i] = a[i] - a[i-1] （a[i] 表示原本的第i個數）
則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]
所以單點查詢變成了區間求和
那么區間修改怎么辦呢 ？
我們看這樣一個例子：
a 1 3 4 5 7 10
c 1 2 1 1 2 3
若我們令區間[2,4]加2，則
a 1 5 6 7 9 10
c 1 4 1 1 2 1
我們可以發現只有c[2]和c[5]的數值改變了，其實原理也很好想，區間內的前后元素差是不變的，只有（區間第一個元素與前一個元素的差） 和 （區間后第一個元素與區間末尾元素的差） 改變了。所以區間修改問題變成了單點修改問題。
for(int i=1;i<=n;i++) { a[i] = read() ; Update(i,a[i]-a[i-1]); } /* int x=0,y=0; // 注釋掉的內容是空間上的優化（初學者建議先跳過） 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)); } }（洛谷有對應的模板題 P3374 與 P3368）
上述就是樹狀數組最基礎的兩個應用，日后更深入的學習后再來更新。
如有疑問請留言或到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
