轉(zhuǎn)載：https://blog.csdn.net/I_believe_CWJ/article/details/80374326

更簡潔方便的數(shù)據(jù)結(jié)構(gòu)--樹狀數(shù)組（基于線段樹的實(shí)現(xiàn)）

?

1.單點(diǎn)更新+區(qū)間求和（基本線段樹，簡單，自行了解）

?

2.區(qū)間更新+單點(diǎn)求值（基于單點(diǎn)更新+區(qū)間求和）

?

例：HDU 1556-Color the ball

操作1：修改某段區(qū)間[l, r]的值
操作2：求某項(xiàng)的值

前面我們簡單介紹了BIT的作用：可以快速求出某段區(qū)間的值，但是我們?nèi)绾慰焖傩薷哪扯螀^(qū)間的值呢？
這里我們引入另一個數(shù)組，叫做差分?jǐn)?shù)組b[]，這個數(shù)組內(nèi)裝的是什么值呢？
下面給大家解釋一下，這里我們的b[i] = a[i]-a[i-1]那么我們的a[i] = b[1]+b[2]+b[3]+....+b[i]，所以我們求某個單點(diǎn)的值就又轉(zhuǎn)化成了一個區(qū)間求和。
例如：a[] = 1 3 5 9 7 10
那么：b[] = 1 2 2 4 -2 3

那么我們進(jìn)行區(qū)間更新的時候怎么操作呢？
同樣對于上面的那個例子，我們要給區(qū)間[2,4]內(nèi)的每一項(xiàng)加1，那么此時我們的b[] = 1 3 2 4 -3 3，與原來的b[]數(shù)組相比，由于差分的效果，我們的b[]數(shù)組是不是只是把b[2]+1，b[5]-1，除了b[l]和b[r+1]，其他地方的差值沒有變吶，所以對于區(qū)間更新+單點(diǎn)求值的問題，我們又轉(zhuǎn)化成了單點(diǎn)更新+區(qū)間求和的問題啦！

求和：所以我們求a[i]就求b[]數(shù)組的sum(i)即可
更新：我們更新a[l, r]+x就add(l, x), add(r+1, -x)即可
?

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #define bug printf("*********\n"); #define mem0(a) memset(a, 0, sizeof(a)); #define mem1(a) memset(a, -1, sizeof(a)); using namespace std; typedef long long LL;int bit[100010], n;int sum(int i) {int ans = 0;while(i > 0) {ans += bit[i];i -= (i&-i);}return ans; }void add(int i, int k) {while(i <= n) {bit[i] += k;i += (i&-i);} }int main() {int l ,r;while(~scanf("%d", &n) && n) {mem0(bit); //因?yàn)殚_始所有的差分值都為0/*如果有初值的話，就a[0] = 0for(int i = 1; i <= n; i ++) {scanf("%d", &a[i]);add(i, a[i] - a[i-1]);}*/for(int i = 0; i < n; i ++) {scanf("%d%d", &l, &r);add(l, 1);add(r+1, -1);}for(int i = 1; i < n; i ++)printf("%d ", sum(i));printf("%d\n", sum(n));}return 0; }

3.區(qū)間更新+區(qū)間求和（基于區(qū)間更新+單點(diǎn)求和）還是差分的思想，重點(diǎn)！

例題：POJ 3468-A Simple Problem with Integers?

操作1：給區(qū)間[l, r]的所有數(shù)加上x
操作2：求區(qū)間[l ,r]內(nèi)的和

前面我們實(shí)現(xiàn)了區(qū)間更新+單點(diǎn)求和，那么神仙們一定不會放過區(qū)間更新+區(qū)間求和的騷操作，確實(shí)，大神們也實(shí)現(xiàn)了這一操作，接下來我就給大家講解一下，其實(shí)也是非常的簡單：
前面的區(qū)間更新+單點(diǎn)求值，我們的a[i] = b[1] + b[2] + b[3] +....+ b[i]，那么我們推一下區(qū)間求和

我們來看看a[1] + a[2] + a[3] + ... + a[n] = b[1] + (b[1]+b[2]) + (b[1]+b[2]+b[3]) + ... + (b[1]+b[2]+b[3]+...+b[n])

???????????????????????????????????????????????????????????????= n*(b[1]+b[2]+b[3]+...+b[n]) - (0*b[1]+1*b[2]+2*b[3]+...+(n-1)*b[n])

那么我們在定義一個數(shù)組c[i] = (i-1)*b[i]，那么我們的區(qū)間[1, n]的a[i]和就為n*sum(b[] ,n) - sum(c[], n)
我們在修改b[i]時同時對c[i]進(jìn)行維護(hù)即可，即add(b[], i, x) 的同時 add(c[], i, (i-1)x)

例如我們要求a[l] ~ a[r]的和，那么我們用b[]數(shù)組來代替所有的a[]會是什么樣呢？
結(jié)果就是：( n*sum(b[], r) - sum(c[], r) ) - ( n*sum(b[], l) - sum(c[], l) )。
?

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #define mem0(a) memset(a, 0, sizeof(a)); #define mem1(a) memset(a, -1, sizeof(a)); using namespace std; typedef long long LL;LL n, m, a[100010]; LL bit0[100010], bit1[100010]; char str[2];LL sum(LL *bit, LL k) {LL ans = 0;while(k > 0) {ans += bit[k];k -= (k & -k);}return ans; }void add(LL *bit, LL k, LL add) {while(k <= n) {bit[k] += add;k += (k & -k);} }int main() {LL l, r, w;while(~scanf("%lld%lld", &n, &m)) {mem0(bit0);mem0(bit1);a[0] = 0;for(int i = 1; i <= n; i ++) {scanf("%lld", &a[i]);add(bit0, i, a[i] - a[i-1]);add(bit1, i, (i-1)*(a[i] - a[i-1]));}while(m --) {scanf("%s", str);if(str[0] == 'C') {scanf("%lld%lld%lld", &l, &r, &w);add(bit0, l, w);add(bit0, r+1, -w);add(bit1, l, (l-1)*w);add(bit1, r+1, -r*w);}else {scanf("%lld%lld", &l, &r);LL ans = 0;ans -= (l-1)*sum(bit0,l-1)-sum(bit1,l-1);ans += r*sum(bit0,r)-sum(bit1,r);printf("%lld\n", ans);}}}return 0; }

總結(jié)：個人覺得樹狀數(shù)組的主要思想就是前綴和+差分思想

看了所有樹狀數(shù)組的代碼，相比之下，線段樹的代碼是不是就顯得格外的長，還容易出錯，下面貼出最后一個例題的線段樹AC的代碼，大家比較下就。。。

#include<stdio.h> #include<string.h> #include<iostream> #include<math.h> #include<time.h> #include<map> #include<string> #include<algorithm> #include<set> #define N 50000using namespace std;int a;struct node {int L;int R;long long num;long long lazy;int lenth; }leaves[100000<<2];void Push_Tree(int k) {if(leaves[k].lazy){leaves[2*k].num = leaves[2*k].num + leaves[k].lazy*leaves[2*k].lenth;leaves[2*k+1].num = leaves[2*k+1].num + leaves[k].lazy*leaves[2*k+1].lenth;leaves[2*k].lazy += leaves[k].lazy;leaves[2*k+1].lazy += leaves[k].lazy;leaves[k].lazy = 0;} }void Build_Tree(int l, int r, int k) {leaves[k].L = l;leaves[k].R = r;leaves[k].lazy = 0;leaves[k].lenth = r - l + 1;if(l == r){scanf("%lld", &leaves[k].num);return;}int mid = (l+r)/2;Build_Tree(l, mid, 2*k);Build_Tree(mid+1, r, 2*k+1);leaves[k].num = leaves[2*k].num+leaves[2*k+1].num; }void Update_Tree(int l, int r, int add, int k) {if(leaves[k].L == l && leaves[k].R == r){leaves[k].num += leaves[k].lenth * add;leaves[k].lazy += add;return;}Push_Tree(k);int mid = (leaves[k].L+leaves[k].R)/2;if(r <= mid) Update_Tree(l, r, add, 2*k);else if(l > mid)Update_Tree(l, r, add, 2*k+1);else{Update_Tree(l, mid, add, 2*k);Update_Tree(mid+1, r, add, 2*k+1);}leaves[k].num = leaves[2*k].num + leaves[2*k+1].num; }long long Search_Tree(int l, int r, int k) {if(leaves[k].L == l && leaves[k].R == r){return leaves[k].num;}Push_Tree(k);int mid = (leaves[k].L+leaves[k].R)/2;if(r <= mid) return Search_Tree(l, r, 2*k);else if(l > mid) return Search_Tree(l, r, 2*k+1);else{return Search_Tree(l, mid, 2*k) + Search_Tree(mid+1, r, 2*k+1);} }int main() {int n, m, x, y, s;char oder[2];scanf("%d%d", &n, &m);Build_Tree(1, n, 1);while(m--){scanf("%s", oder);if(oder[0] == 'C'){scanf("%d%d%d", &x, &y, &s);Update_Tree(x, y, s, 1);}if(oder[0] == 'Q'){scanf("%d%d", &x, &y);printf("%lld\n", Search_Tree(x, y, 1));}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的树状数组（单点+区间的所有操作）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。