這篇文章將為大家詳細(xì)講解有關(guān)C語(yǔ)言中怎么實(shí)現(xiàn)一個(gè)樹狀數(shù)組，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供雷山網(wǎng)站建設(shè)、雷山做網(wǎng)站、雷山網(wǎng)站設(shè)計(jì)、雷山網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、雷山企業(yè)網(wǎng)站模板建站服務(wù)，十年雷山做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

C語(yǔ)言樹狀數(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));
    }
  }

關(guān)于C語(yǔ)言中怎么實(shí)現(xiàn)一個(gè)樹狀數(shù)組就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。