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）

上述就是樹狀數組最基礎的兩個應用，日后更深入的學習后再來更新。

 如有疑問請留言或到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！