淺談樹狀數組

最近學了樹狀數組，給我的感覺就是 這個數據結構好神奇啊^_^

首先她的常數比線段樹小，其次她的實現複雜度也遠低於線段樹 （並沒有黑線段樹的意思=-=）

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

關於樹狀數組的基礎知識與原理網上一搜一大堆，我就不贅述了，就談一些樹狀數組的應用好了

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）

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

——end ;