資料結構——樹狀數組

我們今天來講一個應用比較廣泛的資料結構——樹狀數組

它可以在O（nlogn）的複雜度下進行單點修改區間查詢，下面我會分成三個子產品對樹狀數組進行詳細的解說，分别是樹狀數組基本操作、樹狀數組區間修改單點查詢的實作、樹狀數組查詢最值的實作

一.

樹狀數組一般分為三種操作，初始化、修改、查詢

在講基本操作之前，我們先來看一張圖

這張圖就是樹狀數組的存儲方式，對于沒有接觸過樹狀數組的人來說看懂上面這張圖可能有些困難，上圖的A數組就是我們的原數組，C數組則是我們需要維護的數組，這樣存儲能幹什麼呢，比如我們在查詢A[1~7]數組的字首和時，可以将C[4]、C[6]、C[7]三個數組的值加起來，那麼它就是我們要求的A[1~7]的字首和，那麼為什麼是C[4]、C[6]、C[7]三個數組呢

我們來看一下4、6、7在二進制下是什麼

7 = 22 + 21 + 20  = （111）2

6 = 22 + 21  = （110）2

4 = 22 = （100）2

于是我們發現，從7到4，我們的二進制的1從最後一位開始減少，再根據上圖，我們可以發現，C[i]數組存儲區間為[ i - 2k + 1,i]，其中k是二進制下i末尾的0的個數

這裡我們用lowbit（x）表示x在二進制下C[ i ]的存儲長度，lowbit的求法如下：

inline int lowbit(int x)
{
  return x&(-x);
}      

關于它的原理，如下：

二進制下的負數是将原來的整數取反後加1表示的，就像這樣：

原數字 x：（100101000）2

取反 ~x：（011010111）2

負數 ~x+1：（011011000）2

我們發現，這樣操作後，末尾1前面的數都被取反了，而後面的數全部變成了0，于是

x & (-x) = （000001000）2

這樣，我們就将C[ i ]每次的存儲長度求出來了

下面我們講樹狀數組的基本操作

inline void add(int x,int y) //給x加上y
{
  while(x <= n)
  {
    c[x] += y;
    x += lowbit(x);
  }
  return ;
}

inline int query(int x) //查詢1~7的字首和
{
  int ans = 0;
  while(x)
  {
    ans += c[x];
    x -= lowbit(x);
  }
  return ans;
}      

當我們求區間l ~ r的區間和時，可以用C[r] - C[l - 1]

如果你還是不太懂，就結合着上面的圖和代碼，感性了解一下

二.

下面我們講樹狀數組如何做到區間修改（單點查詢過于簡單我就不提了）

我們可以發現，當我們讓區間l ~ r加上v時，實際上相當于我們先将區間l ~ n加上v，再将區間r + 1 ~ n減去v

是以，第一種方法，我們可以再維護一個樹狀數組B用來存區間修改的情況，當我們查詢某一點i時，用B[1~i]的字首和加上我們原來維護的數組，就可以做到區間修改單點查詢了

不過，在這裡我們有一種巧妙的方法可以不用維護兩個樹狀數組，我們可以維護一個差分數組C，讓A[i] - A[i - 1]加入數組C，這樣我們在修改區間l ~ r時，隻要讓l加上v，再讓r + 1減去v就行了，證明非常簡單，因為l ~ r中的數同時加上了一個數，A[i] - A[i - 1]不變

這樣我們就用一個樹狀數組進行了區間修改單點查詢操作，在查詢一個數x時，A[x]就是C[1~x]的字首和

有一道洛谷的闆子題可供練習

洛谷 P3368

代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>

const int maxn = 1e6 + 6;
int n,m;
int cost[maxn];

inline int read()
{
  char ch = getchar();int x = 0,f = 1;
  while(ch<'0'||ch>'9'){if(ch == '-') f = -1; ch = getchar();}
  while(ch>='0'&&ch<='9'){x = x*10 + ch -'0'; ch = getchar();}
  return x*f;
}

inline int lb(int  x)
{
  return x&(-x);
}

inline void add(int a,int v)
{
  while(a<=n)
  {
    cost[a] += v;
    a += lb(a);
  }
}

inline int query(int a)
{
  int ans = 0;
  while(a)
  {
    ans += cost[a];
    a -= lb(a);
  }
  return ans;
}

int main(int argc, char const *argv[]) 
{
  n = read();
  m = read();
  int pre = 0;
  for(int i = 1;i <= n;i ++)
  {
    int val = read();
    add(i,val - pre);
    pre = val;
  }
  for(int i = 1;i <= m;i ++)
  {
    int flag,x,y,k;
    flag = read();
    if(flag == 1)
    {
      x = read();
      y = read();
      k = read();
      add(x,k);
      add(y+1,-k);
    }
    else
    {
      x = read();
      printf("%d\n",query(x));
    }
  }
  return 0;
}      

三.

下面我們來講樹狀數組查詢區間最值，雖然它的複雜度為O（nlognlogn），但是依然是我們可以接受的

我們來考慮如何維護最值，一個顯然的方法我們對于每個元素都讓它自身的值和覆寫它的C數組取最值，複雜度為O（nlogn），然後當我們要改變一個數的值的時候，将C數組清空然後重新維護，顯然這個複雜度并不理想

我們接着考慮有沒有更快的維護方法，于是我們發現，對于一個區間C[x]，能轉移到它的隻有C[x - 20]、C[x - 21]、C[x - 22]...C[x - 2 k],且2k < lowbit(x),2k+1 >= lowbit(x)

這樣，我們就維護出區間C[x]的最值了，且維護的複雜度為O（lognlogn）

代碼如下：

inline void modify(int x,int y) //把x的值改為y
{
  a[x] = y;
  while(x <= n)
  {
    c[x] = a[x];
    for(int i = 1;i < lowbit(x);i <<= 1) c[x] = std::max(c[x],c[x - i]);
    x += lowbit(x);
  }
  return ;
}      

查詢的方法也非常簡單，我們從查詢的右端點開始找被包含的C數組，若r - lowbit(r) >= l，就用C[r]維護最值，否則，我們就直接用A[r]維護最值

代碼如下：

inline int query(int l,int y) //查詢區間l ~ r的最大值
{
  int ans = 0;
  while(l <= r)
  {
    ans = std::max(ans,a[r]);
    r--;
    while(l <= r - lowbit(r))
    {
      ans = std::max(ans,c[r]);
      r -= lowbit(r);
    }
  }
  return ans;
}      

這裡有一道例題

HDU 1754

就是一個樹狀數組維護最值的闆子題，代碼如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

const int maxn = 2e5+5;
int n,m;
int a[maxn];
int cost[maxn];

inline int lb(int x)
{
    return x&(-x);
}

inline void modify(int x)
{
    while(x<=n)
    {
        cost[x] = a[x];
        for(int i = 1;i < lb(x);i<<=1) cost[x] = std::max(cost[x],cost[x-i]);
        x += lb(x);
    }
}

inline int query(int l,int r)
{
    int ans = 0;
    while(l <= r)
    {
        ans = std::max(ans,a[r]);
        r --;
        while(l <= r-lb(r)) 
        {
            ans = std::max(ans,cost[r]);
            r -= lb(r);
        }
    }
    return ans;
}

int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(a,0,sizeof(a));
        memset(cost,0,sizeof(cost));
        for(int i = 1;i <= n;i ++)
        {
            scanf("%d",&a[i]);
            modify(i);
        }
        for(int i = 1;i <= m;i ++)
        {
            char flag = getchar();
            while(flag!='Q'&&flag!='U')flag = getchar();
            if(flag=='Q')
            {
                int l,r;
                scanf("%d %d",&l,&r);
                printf("%d\n",query(l,r));
            }
            else if(flag=='U')
            {
                int x,v;
                scanf("%d %d",&x,&v);
                a[x] = v;
                modify(x);
            }
        }
    }
    return 0;
}       

轉載于:https://www.cnblogs.com/Ackers/p/10090713.html