老規矩，推薦一篇原理講解清晰的博客！（樹狀數組(詳細分析+應用)，看不懂打死我!_樹形數組_鮮果維他命的博客-CSDN博客）

相對于線段樹，樹狀數組的優點就是代碼簡潔，容易修改。單缺點就是優點問題只有線段樹才能解決，樹狀數組有一定的局限性。

1，模板

（1）單點修改，區間查詢

int lowbit(int x) {return x & (-x);
}
int add_dandian(int pos, int k)
{for (int i = pos; i <= n; i += lowbit(i)) c[i] += k;
}
int search(int L, int R)
{//利用前綴和相減的性質，[L, R] = [1, R] ?[1, L ? 1]int ans = 0;for (int i = L - 1; i; i -= lowbit(i)) ans -= c[i];for (int i = R; i; i -= lowbit(i)) ans += c[i];return 0;
}

（2）區間修改，單點查詢

我們需要構造出原數組的差分數組b，然后用樹狀數組維護b數組即可

對于區間修改的話，我們只需要對差分數組進行操作即可，例如對區間[L,R]+k,那么我們只需要更

新差分數組add(L,k),add(R+1,-k)，這是差分數組的性質.

int lowbit(int x) {return x & (-x);
}
void update(int pos, int k)//pos表示修改點的位置,K表示修改的值也即+K操作
{for (int i = pos; i <= n; i += lowbit(i)) c[i] += k;
}void range_add(int L, int R, int k){update(L, k);update(R + 1, -k);
}int ask(int pos)//返回區間pos到1的總和
{int ans = 0;for (int i = pos; i; i -= lowbit(i)) ans += c[i];return ans;
}

（3)區間修改，區間查詢

void add(ll p, ll x){for(int i = p; i <= n; i += i & -i)sum1[i] += x, sum2[i] += x * p;
}
void range_add(ll l, ll r, ll x){add(l, x), add(r + 1, -x);
}
ll ask(ll p){ll res = 0;for(int i = p; i; i -= i & -i)res += (p + 1) * sum1[i] - sum2[i];return res;
}
ll range_ask(ll l, ll r){return ask(r) - ask(l - 1);
}

2，題目練習

（1）【模板】樹狀數組 1 - 洛谷

?AC代碼

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,a[N];int lowbit(int x)
{return x&(-x);
}
void add(int pos,int k);
int search(int l,int r);signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){//cin>>a[i];int x;cin>>x;add(i,x);}for(int i=0;i<m;i++){int flag,l,r;cin>>flag>>l>>r;if(flag==1) add(l,r);else cout<<search(l,r)<<endl;}return 0;
}void add(int pos,int k)
{for(int i=pos;i<=n;i+=lowbit(i)){a[i]+=k;}
}int search(int l,int r)
{int sum=0;for(int i=r;i;i-=lowbit(i)){sum+=a[i];}for(int i=l-1;i;i-=lowbit(i)){sum-=a[i];}return sum;
} 

（2）【模板】樹狀數組 2 - 洛谷

?? AC代碼

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int n,m,a[N],b[N];int lowbit(int x)
{return x&(-x);
}
void add(int pos,int k);
int find(int pos);signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];add(i,a[i]-a[i-1]);//差分 }for(int i=0;i<m;i++){int flag,l,r,k;cin>>flag;if(flag==1){cin>>l>>r>>k;add(l,k);add(r+1,-k);}else{cin>>l;cout<<find(l)<<endl;}}return 0;
}void add(int pos,int k)
{for(int i=pos;i<=n;i+=lowbit(i)) b[i]+=k;return;
}int find(int pos)
{int sum=0;for(int i=pos;i;i-=lowbit(i)) sum+=b[i];return sum;
}

（3）逆序隊? 逆序對 - 洛谷

AC代碼

#include <bits/stdc++.h>
using namespace std;
int n, a[5000001], b[5000001];
long long ans;
inline void msort(int l, int r)//歸并排序
{int mid = (l + r) / 2;//取中間 if(l == r)//若l == r了，就代表這個子序列就只剩1個元素了，需要返回 {return;}else{msort(l, mid);//分成l和中間一段，中間 + 1和r一段（二分） msort(mid + 1, r);}int i = l;//i從l開始，到mid，因為現在排序的是l ~ r的區間且要二分合并 int j = mid + 1;//j從mid + 1開始，到r原因同上int t = l;//數組b的下標，數組b存的是l ~ r區間排完序的值 while(i <= mid && j <= r)//同上i，j的解釋 {if(a[i] > a[j])//如果前面的元素比后面大(l ~ mid中的元素 > mid + 1 ~ r中的元素)(逆序對出現!!!) { ans += mid - i + 1;//由于l ~ mid和mid + 1 ~ r都是有序序列所以一旦l ~ mid中的元素 > mid + 1 ~ r中的元素而又因為第i個元素 < i + 1 ~ mid那么i + 1 ~ mid的元素都 > 第j個元素。所以+的元素個數就是i ~ mid的元素個數，及mid - i + 1(歸并排序里沒有這句話，求逆序對里有) b[t++] = a[j++];//第j個元素比i ~ mid的元素都小，那么第j個元素是目前最小的了，就放進b數組里 //++j;//下一個元素(mid + 1 ~ r的元素小，所以加第j個元素) }else{b[t++] = a[i++];//i小，存a[i] //++i;//同理 }}while(i <= mid)//把剩的元素(因為較大所以在上面沒選) {b[t++] = a[i++];//存進去 //++i; }while(j <= r)//同理 {b[t++] = a[j++];//++j;}for(int i = l; i <= r; ++i)//把有序序列b賦值到a里 {a[i] = b[i];}return;
}
int main()
{scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);}msort(1, n);//一開始序列是1 ~ n printf("%lld", ans);return 0;
}

（4）康托展開? 【模板】康托展開 - 洛谷

AC代碼

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int mod = 998244353;
int a[N], w[N]={1,1},tr[N], n,ans;int lowbit(int x) {return x & (-x);
}
void update(int pos, int k) {for (int i = pos; i <= n; i += lowbit(i)) tr[i] += k;return;
}
int query(int pos)
{int sum = 0;for (int i = pos; i; i -= lowbit(i)) sum+=tr[i];return sum;
}signed main()
{cin >> n;for (int i = 1; i <= n; i++) {//求階乘w[i] = (i * w[i - 1]) % mod;update(i, 1);}for (int i = 1; i <= n; i++) {cin >> a[i];ans = (ans + ((query(a[i]) - 1) * w[n-i]) % mod) % mod;update(a[i], -1);//減1后就變成0了}cout << ans+1 << endl;return 0;
}

（5）二維樹狀數組? 上帝造題的七分鐘 - 洛谷

思想：和二維前綴和的思路很相似

AC代碼

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int N = 3000;
int board[N][N];
int n, m;// 定義樹狀數組結構（樹狀數組三件套）
struct BIT
{int tr[N][N];  // 樹狀數組int lowbit(int x) {return x & (-x);  // 返回 x 的最低位的 1 所在位置}// 在坐標 (x, y) 處添加值 kvoid add(int x, int y, int k){for (int i = x; i <= n; i += lowbit(i)) {for (int j = y; j <= m; j += lowbit(j)) {tr[i][j] += k;  // 在 (i, j) 處加上值 k}}}// 查詢坐標 (x, y) 處的前綴和int query(int x, int y){int sum = 0;for (int i = x; i; i -= lowbit(i)) {for (int j = y; j; j -= lowbit(j)) {sum += tr[i][j];  // 查詢 (1, 1) 到 (x, y) 的前綴和}}return sum;}
} A, Ai, Aj, Aij;  // 定義四個不同的樹狀數組void Add(int x, int y, int k);
int Ans(int x, int y);int main()
{char ch;cin >> ch >> n >> m;  // 讀取矩陣大小while (cin >> ch) {int x1, x2, y1, y2;cin >> x1 >> y1 >> x2 >> y2;if (ch == 'L') {int num;cin >> num;Add(x1, y1, num);  // 在指定區域添加值 numAdd(x1, y2 + 1, -num);Add(x2 + 1, y1, -num);Add(x2 + 1, y2 + 1, num);}else {cout << Ans(x2, y2) - Ans(x1 - 1, y2) - Ans(x2, y1 - 1) + Ans(x1 - 1, y1 - 1) << endl;// 查詢并輸出給定矩形區域的和}}return 0;
}// 計算 (x, y) 處的結果
int Ans(int x, int y)
{return A.query(x, y) * (x * y + x + y + 1) - Ai.query(x, y) * (y + 1) - Aj.query(x, y) * (x + 1) + Aij.query(x, y);
}// 在坐標 (x, y) 處添加值 num
void Add(int x, int y, int num)
{A.add(x, y, num);Ai.add(x, y, num * x);Aj.add(x, y, num * y);Aij.add(x, y, num * x * y);
}