C語言樹狀數(shù)組的實(shí)例詳解

最近學(xué)了樹狀數(shù)組，給我的感覺就是 這個(gè)數(shù)據(jù)結(jié)構(gòu)好神奇啊^_^

首先她的常數(shù)比線段樹小，其次她的實(shí)現(xiàn)復(fù)雜度也遠(yuǎn)低于線段樹 （并沒有黑線段樹的意思=-=）

所以熟練掌握她是非常有必要的。。

關(guān)于樹狀數(shù)組的基礎(chǔ)知識(shí)與原理網(wǎng)上一搜一大堆，我就不贅述了，就談一些樹狀數(shù)組的應(yīng)用好了

1，單點(diǎn)修改，求區(qū)間和

#define lowbit(x) (x&-x) // 設(shè) x 的末尾零的個(gè)數(shù)為 y , 則 lowbit(x) == 2^y 
void Update(int i,int v) // 初始化與單點(diǎn)修改 
{
  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ū)間修改，單點(diǎn)查詢

這里要用到差分的思想

創(chuàng)建一個(gè)差分?jǐn)?shù)組c[]，令c[i] = a[i] - a[i-1] （a[i] 表示原本的第i個(gè)數(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]

所以單點(diǎn)查詢變成了區(qū)間求和

那么區(qū)間修改怎么辦呢 ？

我們看這樣一個(gè)例子：

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ù)值改變了，其實(shí)原理也很好想，區(qū)間內(nèi)的前后元素差是不變的，只有（區(qū)間第一個(gè)元素與前一個(gè)元素的差） 和 （區(qū)間后第一個(gè)元素與區(qū)間末尾元素的差） 改變了。所以區(qū)間修改問題變成了單點(diǎn)修改問題。

  for(int i=1;i<=n;i++)
  {
    a[i] = read() ;
    Update(i,a[i]-a[i-1]);
  } 
/*  int x=0,y=0;    // 注釋掉的內(nèi)容是空間上的優(yōu)化（初學(xué)者建議先跳過）
  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));
    }
  }

（洛谷有對應(yīng)的模板題 P3374 與 P3368）

上述就是樹狀數(shù)組最基礎(chǔ)的兩個(gè)應(yīng)用，日后更深入的學(xué)習(xí)后再來更新。

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