欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2017年10月15日 16:58:46   作者:zubizakeli  
這篇文章主要介紹了C語言樹狀數(shù)組的實例詳解的相關(guān)資料,希望通過本文能幫助到大家,讓大家理解掌握這部分內(nèi)容,需要的朋友可以參考下

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

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

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

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

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

1,單點修改,求區(qū)間和

#define lowbit(x) (x&-x) // 設(shè) 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)建一個差分?jǐn)?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ū)間內(nèi)的前后元素差是不變的,只有(區(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;    // 注釋掉的內(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ǔ)的兩個應(yīng)用,日后更深入的學(xué)習(xí)后再來更新。

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

相關(guān)文章

  • C語言詳解鏈?zhǔn)疥犃信c循環(huán)隊列的實現(xiàn)

    C語言詳解鏈?zhǔn)疥犃信c循環(huán)隊列的實現(xiàn)

    隊列(Queue)與棧一樣,是一種線性存儲結(jié)構(gòu),它具有如下特點:隊列中的數(shù)據(jù)元素遵循“先進先出”(First In First Out)的原則,簡稱FIFO結(jié)構(gòu)。在隊尾添加元素,在隊頭刪除元素,本篇來講解鏈?zhǔn)疥犃信c循環(huán)隊列的實現(xiàn)
    2022-04-04
  • C++的template模板中class與typename關(guān)鍵字的區(qū)別分析

    C++的template模板中class與typename關(guān)鍵字的區(qū)別分析

    這篇文章中我們來談一談C++的template模板中class與typename關(guān)鍵字的區(qū)別分析,同時會講到嵌套從屬名稱時的一些注意點,需要的朋友可以參考下
    2016-06-06
  • C++模板非類型形參的詳細(xì)講解

    C++模板非類型形參的詳細(xì)講解

    這篇文章主要給大家介紹了關(guān)于C++模板非類型形參的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作就有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2021-11-11
  • C語言 typedef:給類型起一個別名

    C語言 typedef:給類型起一個別名

    本文主要介紹C語言 typedef,這里整理了相關(guān)資料及簡單示例代碼幫助大家學(xué)習(xí)理解,有興趣的小伙伴可以參考下
    2016-08-08
  • Qt中PaintEvent繪制實時波形圖的實現(xiàn)示例

    Qt中PaintEvent繪制實時波形圖的實現(xiàn)示例

    本文主要介紹了Qt中PaintEvent繪制實時波形圖的實現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-06-06
  • c語言中形參與實參的關(guān)系解讀

    c語言中形參與實參的關(guān)系解讀

    這篇文章主要介紹了c語言中形參與實參的關(guān)系,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-07-07
  • C++ OpenCV實戰(zhàn)之手寫數(shù)字識別

    C++ OpenCV實戰(zhàn)之手寫數(shù)字識別

    這篇文章主要為大家詳細(xì)介紹了如何使用machine learning機器學(xué)習(xí)模塊進行手寫數(shù)字識別功能,文中的示例代碼講解詳細(xì),感興趣的可以了解一下
    2022-08-08
  • 在C語言編程中使用變量的基礎(chǔ)教程

    在C語言編程中使用變量的基礎(chǔ)教程

    這篇文章主要介紹了在C語言編程中使用變量的基礎(chǔ)教程,特別需要注意C語言中的指針變量,需要的朋友可以參考下
    2016-02-02
  • C++實現(xiàn)順序表的方法

    C++實現(xiàn)順序表的方法

    本文給大家?guī)砹薈++實現(xiàn)順序表的方法,代碼簡單易懂,附有注釋,感興趣的朋友一起看下吧
    2016-08-08
  • C++名稱空間特性

    C++名稱空間特性

    這篇文章主要介紹了C++名稱空間特性,文章圍繞C++名稱空間特性的相關(guān)資料展開詳細(xì)內(nèi)容,需要的小伙伴可以參考一下下文具體內(nèi)容,希望對你的學(xué)習(xí)有所幫助
    2022-01-01

最新評論