樹狀數組
為什麼需要樹狀數組？
很多場景下，需要通過O（n）的複雜度求字首和，之後通過差分O（1）的複雜度，求指定區間的區間和。
但是，對于已經建立起來的字首和數組，如果改變某個單點的值，修改的代價是O（n）的。
樹狀數組的定義
- 可以通過樹狀數組實作O（logn）的修改，實作O（logn）的查詢
- 樹狀數組的大小于員數列大小相同
- 與字首和不同的是，樹狀數組的 i 位置的元素存儲的并不是前 i 個元素 而是從 i 開始，包括第 i 個元素的前 ti 個元素的和。
- 其中 ti 是最大的可以整除 i 的2的幂
- 例如：s[ i ] 為樹狀數組，d[ i ] 是原數組
-
i = 9， ti = 1 s [ 9 ] = d [ 9 ] -
i = 6 , ti = 2 s [ 6 ] = d [ 5 ] + d [ 6 ] -
i = 24 , ti = 8 s[ 24 ] = d [17] + d [ 18 ] + d [ 19 ] + d [ 20 ] + d [ 21 ] +...+ d [ 24 ] - 如果轉為二進制，ti 的 歸路更加明顯
- i = 9 (1001) ti = 1
- i = 6 (0110) ti = 2
-
i = 24 (11000) ti = 8
ti 為二進制最低位的1，與其後的0組成的2進制
lowbit(i)
求解ti的函數
原數 i ： 101011000
取反 ： 010100111
取反+1：010101000
和原數相與：000001000
lowbit(i) = i & ((~1) + 1) = i & ( -i )
樹狀數組的查詢
要查詢的資料是指定位置x的字首和 [1, x ]的字首和
對于區間 [ 1, 11 ] 可以使用 是 s[ 11 ] + s [ 10 ] + s [ 8 ] 表示
對于任何一個區間，都能被完整的表示出來
因為s[ i ] 可以表示前 ti 個數的和，
ans += s[ i ]
令 i = i - ti
ans += s[ i ]
。。。直到i = 1
ans += s[ 1 ]
傳回 ans
#define lb(x) (x & (-x))
long long ask(int x){
long long res = 0;
for(int i = x;i >= 1;i -= lb(i))
res += s[i];
return res;
}
樹狀數組的性質
性質1 ： 若目前結點為x，且令x + tx 為父節點 tx = lowbit(x) ，則梳妝數組将形成一個樹形結構
性質2 ： 結點x 記錄區間 （ x - tx，x ] 的資訊，其子節點記錄的區間是( x - tx, x ] 的子集，且不會互相覆寫。
性質3 ： 結點x 的記錄的區間為結點y 記錄的區間的子集，當且僅當y是結點x的祖先節點
樹狀數組的修改
修改的時候，改變原數組x位置的值，隻需要修改 s[x] 和所有祖先節點中的值，複雜度是O(logn)的，相比字首和，修改的複雜度小
怎麼找祖先節點？
在 i 位置 加上 lowbit(i)，就是祖先的位置
在i 位置加 v，每個祖先節點都要加v
void upd(int x,int v){
for(int i =x; i <= n;i += lb(i))
s[i] += v;
}
例題
求區間[ l, r ]的和， ask（r）- ask（l-1）
#include"bits/stdc++.h"
#define lb(x) (x & (-x))
using namespace std;
long long s[1000001];
int n,q;
long long ask(int x){
long long res = 0;
for(int i = x;i >= 1;i -= lb(i))
res += s[i];
return res;
}
void upd(int x,int v){
for(int i =x; i <= n;i += lb(i))
s[i] += v;
}
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
memset(s,0,sizeof(s));
cin>>n>>q;
for(int i = 1 ;i <= n;i++)
{
int t;
scanf("%d",&t);
upd(i,t);
}
for(int i = 0;i < q;i++)
{
int op,num1,num2;
scanf("%d %d %d",&op,&num1,&num2);
if(op ==1)
{
upd(num1,num2);
}
else
{
long long ansl = ask(num1-1);
long long ansr = ask(num2);
cout << (ansr - ansl) <<endl;
}
}
return 0;
}
用樹狀數組解決二維偏序問題
-
給定一個序列 a1, a2, a3, …, an，如果存在 i < j 且 ai >
aj，那麼我們稱之為逆序對，求給定序列中逆序對的數目。其中 1 ≤ ai, n ≤ 10^5。
- 對于任意一個ai，統計在其之前求大于 ai 的數的數量，即為以 ai 結尾的逆序對的數量
- 隻要枚舉a1 ~ an分别計算，再求和，即為所求的答案
例題2 二維偏序問題
給定一個序列 a1, a2, a3, …, an，如果存在 i < j 且 ai > aj，那麼我們稱
之為逆序對，求給定序列中逆序對的數目。其中 1 ≤ ai, n ≤ 10^5。
思路：開一個數組s[MAXN],對于a1查詢 a[MAXN]到a[a1 + 1]所有的和，也就是目前比a1大的元素有多少個，查詢的結果加到ans上，更新 a[a1] +1
例子
兩維坐标，按照某一維i例如運作時間排序，求另一維的逆序對數
#include"bits/stdc++.h"
using namespace std;
#define lb(x) (x & (-x))
int s[1000010],n;
//int cnt[1000010];
int ask(int x)
{
int ans = 0;
for(int i = x ;i >= 1; i -= lb(i))
ans += s[i];
return ans;
}
void upd(int x,int v)
{
for(int i = x; i<=1000009;i += lb(i))
s[i] += v;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
cin>>n;
memset(s,0,sizeof(s));
memset(cnt,0,sizeof(cnt));
vector<pair<int,int>> a;
for(int i= 0;i < n;i++)
{
int t,c;
scanf("%d %d",&t,&c);
a.push_back(make_pair(t+1,c+1));
}
sort(a.begin(),a.end());
for(int i = 0;i <n;i++)
{
int num = ask(1000009) - ask(a[i].second);
int score = i - num;
cnt[score]++;
upd(a[i].second,1);
}
for(int i = 0;i < n;i++)
printf("%d\n",cnt[i]);
return 0;
}
例題3 樹狀數組和動态規劃相結合 – 最長上升子序列
狀态：定義fi 表示以A為結尾的最長上升序列的長度
初始化 f1= 1
轉移過程： fi = max{ fj | j < i && Aj < Ai } + 1
輸出答案 max{f[i], i = 1…n}
再找最大的fj j < i && Aj < Ai 的過程中，要從1 到 i 周遊一遍才行，複雜度為O（n^2）
使用樹狀數組進行優化
樹狀數組儲存的内容，從前ti個資料的和， 變為前ti個數的最大值
如果讀到一個數 x ，ask(x - 1),得出結尾小于x的所有子序列的最長的長度，
tmp = ask（x - 1） + 1
upd(x , tmp)