簡述

什么是樹狀陣列呢，顧名思義就是樹一樣的陣列，本質就是用陣列模擬樹形結構，　　

樹狀陣列有什么用呢，樹狀陣列可以實作單點更新，單點查詢，區間查詢和區間更新，維護的東西和線段樹可以類比的，就是滿足區間加法性質的屬性，例如最值，和，gcd等，

樹狀陣列可以干的東西線段樹也能干，但線段樹干的東西樹狀陣列不一定能干，樹狀陣列的復雜度和線段樹同級，但常數更低且代碼量更為簡答，所以我們能用樹狀陣列就用樹狀陣列，這樣就不容易TLE了，

lowbit操作

首先我們來了解一個操作，lowbit(x)，這個操作取出x二進制最低位的1，例：lowbit(10100)=100

ll lowbit(ll x){
    return x&(-x);
}

為什么是x&(-x)呢？我們知道對一個數取負就是對這個數取反加一，我們設原數的二進制為xxx1000...，該數取反為yyy0111...，令其加一，我們可以發現，取反加一后的數只有一位是1，且該位置就是原數最低位的1，所以我們令x&(-x)就可以得到x的lowbit了，

樹的樣子

對于一般的二叉樹，形狀是這樣的　

　　此時我們令其偏一下身子，使其右傾變為這樣

　如果每個節點都存東西，那就不叫樹狀陣列叫線段樹了，那他們有什么不同呢？我們來看下圖：　　

底下的代表我們輸入的a陣列，上面的代表我們的樹狀陣列c陣列，從空間上來說，樹狀陣列只需要存二叉樹的根和左子樹就行，因為右子樹可以由根減左子樹獲得，則有：

?C[1] = A[1];　　
?C[2] = A[1] + A[2];　　
?C[3] = A[3];　　
?C[4] = A[1] + A[2] + A[3] + A[4];　　
?C[5] = A[5];　　
?C[6] = A[5] + A[6];　　
?C[7] = A[7];　　
?C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];　　
可以發現，這顆樹是有規律的，我們可以發現，C[i]存了lowbit(i)個的和，

單點更新，區間求和

單點更新

例如我們需要令a[1]+=k，則需要維護c1，c2，c4，c8這些包含a1的節點，我們可以發現這些需要維護的節點是層次關系：c1<c2<c4<c8，也就是說我們只要更新本節點以及本節點的所有父親就可以實作更新操作，而本結點兄弟維護的葉子數和本節點維護的相同，還記得之前我們觀察的規律C[i]存了從i開始往前數共lowbit(i)個位置的和嗎，我們只需要加上lowbit(本節點的下標)，即可得到本節點的父親，一直遞回到根，就完成了更新，

區間求和

例如我們需要查詢區間3到5的和，其值等于a3+a4+a5，如果我們得到前綴和sum[i]，其值就等于sum[5]-sum[2]，而樹狀陣列恰恰就是利用了前綴和求出區間和，　　

例如我們要求sum(7)，那么sum(7)=c[7]+c[6]+c[4]，我們可以很容易看出，6是由7-lowbit(7)得到的，4是由6-lowbit(6)得到的，而4減它的lowbit就等于0了，我們可以知道，sum(i)可由每個c位置的貢獻求出，每個位置為上個位置減lowbit，為什么可以這樣呢，我們來看i=2的冪時，這時c[i]就完全包含1到i這i個元素，無需做任何處理，當i不是2的冪時，需要一個一個處理，直到i消掉低位的1變為2的冪，例如i=7的時候，一開始lowbit(7)=1，也就是說c[7]只維護了一個節點那就是a[7]，令其減loewbit，得i=6，此時c6維護了a5和a6兩個節點，減去lowbit得i=4，包含1到i所有節點，故加上貢獻后結束，　　

所以下一個有貢獻的位置是當前位減lowbit(當前)，

構建

此時c陣列就是這個樹狀陣列了，c[x]保存的是從下標x開始 a[x]+a[x-1]+a[x-2]+a[x-k] ，至于有幾個a[]相加，這里有一個計算方法，把x化為二進制，從右向左找到第一個1的位置，這個位置所代表的十進制的數字k就意味著c[x]=a[x]+a[x-1]+a[x-2]+...+a[x-k-1];

void build(){
    for (int i=1; i<=n; i++)
        for (int j=i; j>=i-lowbit(i)+1; j--)
            c[i]+=a[j];
}

void update(int x,int val,int n){
    //x位置的值加上val,n為總葉子個數 
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=val;
    } 
}
ll sum(int x){
	ll ans1=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		ans1+=c[i];
	}
	return ans1;
}
ll sum(int x,int y){//區間查詢
	return sum(y)-sum(x-1);
}

區間更新，單點求值

如果單純的對原陣列的樹狀陣列進行區間求和，不難看出這是一件復雜度爆炸的事情；所以我們不妨對原陣列求其差分陣列，然后對差分陣列建立樹狀陣列，那么區間修改就變為了對差分陣列的\(左右端點的兩次單點修改\)，是不是就快多了呢？

同樣，單點查詢就可以看作是對差分陣列的區間求和，這樣又轉換成了最基本的樹狀陣列操作問題，

void build(){
for(int i=1;i<=n;i++){
	cin>>a[i];
	b[i]=a[i]-a[i-1];  //b是差分陣列，求b的樹狀陣列可以將區間修改變為兩次單點修改，將單點查詢改為一次區間求和 
          c[i]=b[i];
          for(int j=i-lowbit(i)+1;j<=i-1;j++){  //構建樹狀陣列 
		   c[i]+=b[j];
		}
	}
}

void update(int x,int y,int k){//區間[x,y]加上k
  for(int j=x;j<=n;j+=lowbit(j)){  
		c[j]+=k;
  }
  for(int j=y+1;j<=n;j+=lowbit(j)){  //兩次單點修改 
		c[j]-=k;
  }

}
int  get(int x){//單點求值
int ans=0;
  for(int j=x;j>0;j-=lowbit(j)){ //區間求和，將區間拆分成多個區間的和 
		ans+=tree[j];
}
return ans;
}

模版

#include<iostream>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
ll lowbit(ll x){
    return x&(-x);
}
void update(int x,int val,int n){
    
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=val;
    } 
}
ll sum(int x){
	ll ans1=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		ans1+=c[i];
	}
	return ans1;
}
ll sum(int x,int y){
	return sum(y)-sum(x-1);
}
void build(){
    for (int i=1; i<=n; i++)
        for (int j=i; j>=i-lowbit(i)+1; j--)
            c[i]+=a[j];
}
int main()
{
    
    return 0;
}

7.28已更新

標籤：其他

上一篇：復雜度分析

下一篇：leetcode 452. Minimum Number of Arrows to Burst Balloons 用最少數量的箭引爆氣球(中等)