樹狀陣列介紹
樹狀陣列，顧名思義，就是樹狀的一維陣列，
二叉樹同樣也可以用一維陣列存盤，我們以二叉樹進行類比，
如圖所示，圖中節點的序號就是存在陣列中的下標，
記父節點序號為 \(p\),子節點序號為 \(s\)，
則有:
\(p\) \(=\) \(s\) \(/\) \(2\) (向下取整)，
左子節點 \(s_{left}\) \(=\) \(p\) \(* 2\) ，
右子節點 \(s_{right}\) \(=\) \(p\) \(*2+1\) ，
綜上可知，二叉樹能用一維陣列存，是由于其父子節點間存在一定關系，以至于不需要用額外的變數來表示資訊，
那類比到樹狀陣列中，可以發現：
\(c\)陣列即為樹狀陣列，\(c_i\) 表示區間\(a\)\([i-lowbit(i),i]\) 的和，
ps：點我了解lowbit運算是什么
同樣記父節點下標為 \(p\) ,子節點下標為 \(s\)，
則有：
\(p\) \(=\) \(s\) \(+\) \(lowbit(s)\)，
由這條公式亦可反推出：
\(s\) \(=\) \(p\) \(-\) \(2^i\)(\(0 \le i < p_{last}\))
這里的 \(p_{last}\) 指的是 \(p\) 二進制表示下最后一位 \(1\) 所在的位數，
例如：\(6\) 的二進制數表示為 \(110\),則它的 \(p_{last}\) 為 \(1\)，（這里的位數從右往左從\(0\)開始記），
因為公式 \(1\) 由 \(s\) 加上自身 \(lowbit(s)\) 得到 \(p\) 其程序一定會產生進位，且 \(lowbit(s)\) 一定小于 \(lowbit(p)\) ,所以可以倒推得到子節點，
由于以上關系，樹狀陣列不僅可以用一維陣列存，而且還衍生出了一系列用途，
樹狀陣列功能
單點增加
Q：給序列中的一個數 \(a[x]\) 加上 \(y\) ，此時如何維護樹狀陣列？
A:將所有包含 \(a[x]\) 的節點加上 \(y\) 即可，也就是 \(c[x]\) 和它所有的祖先節點，
ps:初始化時亦可運用此操作，
點擊查看代碼
void add(int x,int y){
for (; x <= N;x += x&-x) c[x] += y;
return ;
}
動態維護前綴和
之所以說動態維護，因為用樹狀陣列維護前綴和只需要 \(\log N\) 的時間復雜度，更為優秀，
Q：求 \(a\) 陣列 \(a_i \sim a_x\) 的和，
A：將數 \(x\) 分成若干個區間，
區間共同特點：若區間結尾為 \(R\)，則區間長度就等于 \(lowbit（R）\)，即 \(R\) 二進制分解下最小的整數次冪，
舉例：當 \(x\) = \(7\) 時
如圖所示，
區間劃分方式與樹狀陣列相同，前面又提到“\(c\)陣列即為樹狀陣列，\(c_i\) 表示區間\(a\)\([i-lowbit(i),i]\) 的和，”
因此只需要將這幾個區間所對應的 \(c_i\) 相加，即可得到前綴和，
點擊查看代碼
int ask(int x){
int ans = 0;
for (; x ; x -= x & -x) ans += c[x];
return ans;
}
例題【具體應用】
主要利用樹狀陣列可以快速求前綴和的優勢，以資料范圍為下標，快速統計區間內的個數（或所需要的資訊），適用于資料范圍適中（一般為 \(0 \le x \le 10^6\)）且需要多次求前綴和的題目，
【例題1】 三元上升子序列
【題目分析】
對于一個數 \(x\) ,計算其作為 \(j\) 時，位置在它前面比它小的數 \(x_{min}\)、位置在它后面比它大的數 \(x_{max}\),運用乘法原理的知識可知，將\(x_{min} \times x_{max}\),即可得到 \(x\) 作為 \(j\) 時的方案數 ，列舉所有 \(x\) ,即可得到總方案數，
【樹狀陣列作用】
統計 \(x_{min}\) 和 \(x_{max}\) 時，即可將數 \(x\) 的范圍作為樹狀陣列的下標，
此時兩種操作所代表的意思分別為：
\(add(x,1)\) 表示數值為 \(x\) 的數的個數 \(+1\)，
\(sum(y)\) 表示在已經掃描過的區間內，數值為從 \(1 \sim y\) 的所有數的個數，
順序掃描序列，對于數 \(x\) ,統計兩個資訊，
\(r_{i,0}\) 表示位置在數 \(x\) 前面，且比它小的數，
\(r_{i,1}\) 表示位置在數 \(x\) 前面，且比它大的數，
位置在數 \(x\) 后面，且比數 \(x\) 大的數就等于：
\(所有數 - 所有位置在 x 前面比 x 小的數 - r{i,1}\)，
【code】
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
ll tree[100005],n,num;
ll r[40005][2],a[100005];
void add(ll x,ll y){
for(;x<=100005;x+=(x&-x)) tree[x]+=y;
}
ll sum(ll x){
ll ans=0;
for(;x;x-=(x&-x)) ans+=tree[x];
return ans;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
a[i]=x;
num=max(num,x);
add(x,1);
r[i][0]=sum(x-1);
r[i][1]=sum(num)-sum(x);
}
ll ans=0;
for(int i=1;i<=n;i++)
ans+=r[i][0]*(sum(num)-sum(a[i])-r[i][1]);
cout<<ans<<endl;
return 0;
}
【summary】
此題算是初步認識了以數值范圍為下標的樹狀陣列的用法，下一大點求逆序對的思想與此相同，
【例題2】 [USACO04OPEN] MooFest G 加強版
【題目分析】
將奶牛按照音量從小到大進行排序，保證當前奶牛的音量一定最大，然后分類討論所有比當前奶牛音量小的奶牛與當前奶牛的距離(坐標比當前奶牛大的和坐標比當前奶牛小的)，兩者相加，乘上當前奶牛音量，列舉每個奶牛，即可得到答案，
【樹狀陣列作用】
定義兩個樹狀陣列，都是以距離的范圍作為下標， \(c\) 陣列用于統計對應距離的個數，\(t\) 陣列用于表示對應距離 \(\times\) 對應 距離個數的總數，通過二者，即可快速計算距離差，
【code】
計算程序的解釋已在代碼中注釋出來，
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
ll n,t[50005],c[50005];
struct A{
ll v,x;
}a[50005];
bool cmp(A xx,A yy){
if(xx.v==yy.v) return xx.x<yy.x;
return xx.v<yy.v;
}
void addc(ll x,ll y){
for(;x<=50000;x+=(x&-x)) c[x]+=y;
}
void addt(ll x,ll y){
for(;x<=50000;x+=(x&-x)) t[x]+=y;
}
ll sumc(ll x){
ll sum=0;
for(;x;x-=(x&-x)) sum+=c[x];
return sum;
}
ll sumt(ll x){
ll sum=0;
for(;x;x-=(x&-x)) sum+=t[x];
return sum;
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].v,&a[i].x);
sort(a+1,a+n+1,cmp);
ll ans=0,max_num=0;
for(int i=1;i<=n;i++){
max_num=max(max_num,a[i].x);
//以下距離之間的比較限于所有音量比當前奶牛小的奶牛，
//a[i].x*sumc(a[i].x-1) 表示當前奶牛的距離*距離比當前奶牛小的奶牛個數，
//sumt(a[i].x-1) 表示所有距離比當前奶牛小的奶牛的距離和，
//sumt(max_num)-sumt(a[i].x) 表示所有距離比當前奶牛大的奶牛的距離之和，
//sumc(max_num)-sumc(a[i].x))*a[i].x 表示當前奶牛距離 * 距離比當前奶牛大的奶牛個數
ans+=a[i].v*(a[i].x*sumc(a[i].x-1)-sumt(a[i].x-1)+(sumt(max_num)-sumt(a[i].x))-(sumc(max_num)-sumc(a[i].x))*a[i].x) ;
addc(a[i].x,1);
addt(a[i].x,a[i].x);
}
cout<<ans<<endl;
return 0;
}
【summary】
這一題的重點給到題目中樹狀陣列 \(t\)，主要識訓為：以數值范圍為下標的樹狀陣列，能夠處理的資訊不僅限于個數，
【例題3】P1972 [SDOI2009] HH的項鏈
【題意分析】
本題核心：如何判斷一個區間內的貝殼是否重復？
當右端點 \(r\) 固定時，不論 \(l\) 取何值，對于任意一組重復的貝殼，都可以只統計最右端的貝殼，
原因：設一組重復貝殼中最右端的貝殼所在的位置為 \(pos_r\)，那么當 \(pos_r < l\) 時，其他貝殼也不可能算進統計中，當 $pos_r \ge l $時，無論其他貝殼是否被包括，對于區間的貢獻都只有 \(1\)，因此，只計算最右端的貝殼即可，
因此，只需要將所有詢問區間按 \(r\) 從小到大排序，計算答案即可，
【樹狀陣列作用】
以位置為下標，每遇到一個新的數 \(num(num \le r)\)，判斷它是否重復，如果重復，那么將上一個相同的數的貢獻值 \(-1\)，將當前數的貢獻值 \(+1\)，
對于一段區間 \([l,r]\)，答案為 \(sum(r)-sum(l-1)\)，
【code】
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,ask_r,prev,pos;
int vis[1000005],a[1000005],t[1000005],ans[1000005];
struct A{
int l,r,num;
}ask[1000005];
bool cmp(A x,A y){
return x.r<y.r;
}
int find(int pos){
ask_r=ask[pos++].r;
while(ask_r==ask[pos].r) pos++;
return pos-1;
}
void add(int x,int y){
for(;x<=n;x+=(x&-x)) t[x]+=y;
return;
}
int sum(int x){
int su=0;
for(;x;x-=(x&-x)) su+=t[x];
return su;
}
void replace(){
for(int i=ask[prev].r+1;i<=ask_r;i++){
if(vis[a[i]]!=0) add(vis[a[i]],-1);
add(i,1);
vis[a[i]]=i;
}
for(int i=prev+1;i<=pos;i++) ans[ask[i].num]=sum(ask[i].r)-sum(ask[i].l-1);
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d%d",&ask[i].l,&ask[i].r),ask[i].num=i;
sort(ask+1,ask+m+1,cmp);
while(1){
if(pos==m) break;
prev=pos;
pos=find(pos+1);
replace();
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
【\(summary\)】
此題不再以資料范圍為下標，而是以位置為下標，對于樹狀陣列的應用更加靈活，在想到以最右端的貝殼為有價值的貢獻時，對應到樹狀陣列的操作就可以是上一個重復的數的貢獻值 \(-1\)，當前數的貢獻值 \(+1\)，然后用前綴和統計區間內的個數，算進一步的開闊思維，
求逆序對
本質上也是通過樹狀陣列單點增加和區間求和的操作進行計算，作為一個專題單獨列出來，
桶排+樹狀陣列：
1.桶排部分：
對于一個序列 \(a\) , 我們建立一個 \(cnt\) 陣列，\(cnt[x]\) 表示 \(x\) 在序列 \(a\) 中出現過的次數，當 \(a_i=val\) 時，\(cnt[val]++\)，
2.樹狀陣列部分：
倒序掃描序列 \(a\)，對于新加入的數 \(a_i\)，查詢 \(cnt[1~a_i-1]\) 的前綴和，并將回傳的前綴和加入答案，前綴和部分就可以用樹狀陣列來維護，
操作簡單粗暴，但相當好用，
點擊查看代碼
for ( int i = n; i; i --) {
ans += ask (a[i] - 1);
add (a[i] , 1 );
}
【例題】
接下來通過兩道題進一步了解一下逆序對的考法，（不做一下真沒想到還能這樣考，）
【例題1】P2448 無盡的生命
【題意簡述】
看到題目顯而易見是求逆序對個數，
【思路分析】
看到資料范圍 \(x_i,y_i \le 2^{31}-1\)，\(k \le 10^5\)，資料值域大但是個數少，且與資料之間的大小關系有關，因此考慮離散化，
離散化簡單介紹
離散化實際就是一種映射，當資料值域過大而個數有限時，可以嘗試離散化，
具體程序以此題為例，假設給出這么一組資料
2
123456789 123456
987654321 123456
首先將所有出現過的數收集起來，存進 \(a\) 陣列，并進行排序，然后再去重保存進 \(pos\) 陣列當中，
接下來就可以建立映射關系，將數值大的數在 \(num\) 陣列中用數值小的數代替，但各個數之間的大小關系不變，接下來交換操作先用二分答案在 \(pos\) 陣列中檢索，然后通過映射在 \(num\) 陣列中進行交換，
最終被交換過的數之間的逆序對在 \(num\) 陣列中求即可，
被交換的數與未被交換的數之間的逆序對
考慮每個被交換的數對答案的貢獻，
設 \(x<y\),當 \(x\) 和 \(y\) 交換后，
對于 \(x\) 來說, \(x \sim y\) 之間所有未被交換的數都比 \(x\) 大，形成逆序對，
對于 \(y\) 來說，\(x \sim y\) 之間所有未被交換的數都比 \(y\) 小，形成逆序對，
逆序對個數都為\(x \sim y\) 之間所有未被交換的數，
溫馨提示：以下主要為代碼實作講解，本質思想同上，
對于交換過后的 \(num\) 陣列，\(num_i\) 表示的是位置 \(pos_i\) 上當前所在的數在 \(num\) 陣列中對應的數，記數 \(x\) 為位置 \(pos_i\) 上當前所在的數，
\(pos_{num_i}\) 表示數 \(x\) 現在所在的位置，
\(pos_i\) 表示數 \(x\) 原來在的位置，
\(\left\vert pos_i-pos_{num_i}-1\right\vert\) 表示兩個位置間所有的數，
\(\left\vert num_i-i-1\right\vert\) 表示兩個位置間所有被交換過的數，
因此所有未被交換的數就為 \(\left\vert pos_i-pos_{num_i}-1\right\vert - \left\vert num_i-i-1\right\vert\)，
【code】
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct A{
int x,y;
}a[100005];
int k,pos[200005],num[200005],cnt,len;
int t[100005];
void add(int x){
for(;x<=len;x+=(x&-x)) t[x]+=1;
}
long long sum(int x){
long long ans=0;
for(;x;x-=(x&-x)) ans+=t[x];
return ans;
}
int find(int x){
int l=1,r=len;
while(l<r){
int mid=(l+r)>>1;
if(pos[mid]<x) l=mid+1;
else if(pos[mid]>x) r=mid-1;
else return mid;
}
}
int main(){
scanf("%d",&k);
for(int i=1;i<=k;i++){
scanf("%d%d",&a[i].x,&a[i].y);
num[++cnt]=a[i].x;
num[++cnt]=a[i].y;
}
sort(num+1,num+cnt+1);
for(int i=1;i<=cnt;i++){
if(num[i]==num[i-1]) continue;
pos[++len]=num[i];
}
for(int i=1;i<=len;i++) num[i]=i;
for(int i=1;i<=k;i++){
int pos1=find(a[i].x);
int pos2=find(a[i].y);
swap(num[pos1],num[pos2]);
}
long long ans=0;
for(int i=len;i>=1;i--){
add(num[i]);
ans+=sum(num[i]-1);
ans+=abs(pos[num[i]]-pos[i]-1)-abs(num[i]-i-1);
}
cout<<ans<<endl;
return 0;
}
【summary】
重點在于與未交換的數之間的求解，題目中序列的長度可以長到一個陣列都存不下，但卻可以用公式求呢，
【例題2】P3531 [POI2012]LIT-Letters
【題目描述】
該題的重點在于如何從題面描述轉到求 \(逆序對\)，抓到重點：
-
交換 \(a\) 中相鄰兩個字符，求最少的交換次數，
-
\(a,b\) 中只含大寫字母，且資料保證 \(a\) 可以變成 \(b\)，
對 \(b\) 串中的字符進行順序編號（假設此時 \(b\) 中并沒有重復的字母），并對應到 \(a\) 串中，
例如：
3
ABC
BCA
對 \(BCA\) 進行順序編號，對應到 \(ABC\) 就是 \(312\)，
當序列 \(a\) 中存在數 \(a , b\)，滿足 $pos_a < pos_b $ , \(a > b\)，也就是形成逆序對，
而對于我們的目標，將 \(a\) 串變成 \(b\) 串，需滿足任意數 \(a , b\)，都有 \(pos_a < pos_b\) , \(a < b\)，
顯然我們需要通過一定操作，令逆序對都消失，以達到目標，
由于題目中的交換為交換相鄰的數，因此只要 \(a\) 與 \(b\) 不交換，它們之間的相對位置就不會變，也就不能達成目標，
綜上所述，最少的交換次數就是逆序對的個數，
當字母重復時，我們要如何讓編號對應到 \(a\) 呢？
顯然逆序對個數越少越好，因此對于相同的字母，按出現的順序進行順序編號，代碼中用單向鏈表實作，
【code】
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
int now[30],prev[30],nex[1000005];
char s[1000005],ss[1000005];
int a[1000005],t[1000005],lens;
void add(int x,int y){
for(;x<=lens;x+=(x&-x)) t[x]+=y;
return;
}
ll sum(int x){
ll ans=0;
for(;x;x-=(x&-x)) ans+=t[x];
return ans;
}
int main(){
scanf("%d",&lens);
cin>>(s+1);
cin>>(ss+1);
for(int i=1;i<=lens;i++){
int ch=s[i]-'A';
if(now[ch]==0) now[ch]=i;
nex[prev[ch]]=i;
prev[ch]=i;
}
for(int i=1;i<=lens;i++){
int ch=ss[i]-'A';
a[now[ch]]=i;
now[ch]=nex[now[ch]];
}
ll ans=0;
for(int i=lens;i>=1;i--){
add(a[i],1);
ans+=sum(a[i]-1);
}
cout<<ans<<endl;
return 0;
}
區間增加，單點查詢
【模板】樹狀陣列2
思路剖析
相信經過上面的頭腦風暴，再來看這題已經相當簡單了，
此時主要運用到差分的思想,差分是前綴和的逆運算，
當要在區間 \([x,y]\) 加上 \(k\) 時，我們進行以下操作：
\(add(x,k) , add(y+1,-k)\)
此時對于區間求前綴和對于 \(x \sim y\)，它的前綴和都為 \(k\)，而到 \(y+1\) ,又變成 \(0\)，此時的前綴和正好是區間增加的數，且不會對其它數產生影響，
因此，當查詢第 \(x\) 個數時，只需要輸出：
\(a_x(第 x 個數原本的數值) + sum（x）(變化的值)\)，
即可，
code
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[500005],c[500005],n,m;
void add(int x,int k){
for(;x<=n;x+=x&-x) c[x]+=k;
return;
}
int q(int x){
int sum=0;
for(;x;x-=x&-x) sum+=c[x];
return sum;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int type;
scanf("%d",&type);
if(type==1){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
add(x,k);
add(y+1,-k);
}
else{
int x;
scanf("%d",&x);
cout<<a[x]+q(x)<<endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/542271.html
標籤：其他