原文博客鏈接：https://www.cnblogs.com/acgoto/p/8583952.html

?

對于學習的線段樹方面的，發現很多問題可以用它來求解，但是做題的時候發現，用線段樹太容易tle也，很多次也是卡時間過的，然后就發現了樹狀數組。

首先我們搞明白樹狀數組是用來干嘛的，樹狀數組是一個查詢和修改復雜度都為log(n)的數據結構。主要用于查詢任意兩位之間的所有元素之和，但是每次只能修改一個元素的值，經過簡單修改可以在log(n)的復雜度下進行范圍修改，但是這時只能查詢其中一個元素的值(如果加入多個輔助數組則可以實現區間修改與區間查詢)。

所以說，樹狀數組的求解和線段樹的求解有些重合，但是功能沒有線段樹的那么廣泛。但是對樹狀數組來說，其思想大概是用二進制的方法來實現。

先簡單介紹下基本二進制的使用方法：

&?按位與? ? ? ?如果兩個相應的二進制位都為1，則該位的結果值為1，否則為0
|?按位或? ? ? ? 兩個相應的二進制位中只要有一個為1，該位的結果值為1
^?按位異或? ? 若參加運算的兩個二進制位值相同則為0，否則為1
~?取反? ? ? ? ? ?~是一元運算符，用來對一個二進制數按位取反，即將0變1，將1變0
<<?左移? ? ? ? ?用來將一個數的各二進制位全部左移N位，右補0? （<<1則是乘2）
>>?右移? ? ? ? ?將一個數的各二進制位右移N位，移到右端的低位被舍棄，對于無符號數，高位補0（>>1則是除2）

?

原理：lowbit? ? ??

?lowbit這個函數的功能就是求某一個數的二進制表示中最低的一位1，舉個例子，x = 6，它的二進制為110，那么lowbit(x)就返回2，因為最后一位1表示2。

?

那么怎么求lowbit呢？把這個數的二進制寫出來，然后從右向左找到第一個1(這個1就是我們要求的結果，但是現在表示不出來，后來的操作就是讓這個1能表示出來)，這個1不要動和這個1右邊的二進制不變，左邊的二進制依次取反，這樣就求出的一個數的補碼，說這個方法主要是讓我們理解一個負數的補碼在二進制上的特征，然后我們把這個負數對應的正數與該負數與運算一下，由于這個1的左邊的二進制與正數的原碼對應的部分是相反的，所以相與一定都為0,；由于這個1和這個1右邊的二進制都是不變的，因此，相與后還是原來的樣子，故，這樣搞出來的結果就是lowbit(x)的結果。

?

自己來理解一下是怎么存的數據到c數組里面

#include <stdio.h> #include <iostream> #include <cstdlib> #include <cmath> #include <cctype> #include <string> #include <cstring> #include <algorithm> #include <stack> #include <queue> #include <set> #include <map> #include <ctime> #include <vector> #include <fstream> #include <list> #include <iomanip> #include <numeric> using namespace std; typedef long long ll; typedef unsigned long long ull; #define me0 memset(s,0,sizeof(s)) #define me1 memese(s,1,sizeof(s)) const int inf = 0x3f3f3f3f; const int N=100005; int a[N],b[N],c[N]; int lowbit(int x){return x&(-x); } void update(int i,int cc,int n){while(i<=n){c[i]+=cc;i+=lowbit(i);} } int main(int argc, char * argv[]) {std::ios::sync_with_stdio(false);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];update(i,a[i],n);}for(int i=1;i<=n;i++) cout<<c[i]<<" ";return 0; }

輸入：

5

1 2 3 4 5

運行結果：

1 3 3 10 5

結合圖一起看，

c[1]=1,

c[2]=a[1]+a[2]=3

c[3]=a[3]=3

c[4]=a[1]+a[2]+a[3]+a[4]=10

c[5]=a[5]=5

?

然后后面的看到大佬的博客就直接貼個博客鏈接了，感覺大佬講解的很詳細了。

貼個大佬的模板：

?

int lowbit(int i){return i & -i; } //-i 代表i的負數 計算機中負數使用對應的正數的補碼來表示 例如 : i=6（0110） 此時 k=1 -i=-6=(1001+1)=(1010) i&(-i)=(0010)=2=2^1void update(int x,int cc,int n){for(int i=x;i<=n;i+=lowbit(i)) //x為更新的位置,cc為更新后的數,n為數組最大空間 c[i]+=cc; }int sum(int x){ //求區間[1,x]內所有元素的和 int ans=0;for(int i=x;i;i-=lowbit(i))ans+=c[i]; // 從右往左累加求和 return ans; }

?

?

?

來題模板題目 hdu1166?

#include<bits/stdc++.h> using namespace std; int c[50004]; int lowbit(int i){return i&(-i); }void update(int x,int cc,int n){for(int i=x;i<=n;i+=lowbit(i)) //x為更新的位置,cc為更新后的數,n為數組最大空間 c[i]+=cc; }int sum(int x){ //求區間[1,x]內所有元素的和 int ans=0;for(int i=x;i;i-=lowbit(i))ans+=c[i]; // 從右往左累加求和 return ans; }int main(){ios::sync_with_stdio(false);int t,x,y,a;char s[10];cin>>t;for(int z=1;z<=t;z++){memset(c,0,sizeof(c));int n,a;cin>>n;for(int i=1;i<=n;i++){cin>>a;update(i,a,n);}cout<<"Case "<<z<<":"<<endl;while(1){cin>>s;if(s[0]=='E') break;cin>>x>>y;if(s[0]=='A'){update(x,y,n);}if(s[0]=='S'){update(x,-y,n);}if(s[0]=='Q'){cout<<sum(y)-sum(x-1)<<endl;}}}return 0; }

?

轉載于:https://www.cnblogs.com/wushengyang/p/10319111.html

總結

以上是生活随笔為你收集整理的树状数组（Binary Indexed Tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。