引入：

树状数组所处理的问题（简单罗列）：

  • 求出[a,b]之间的和
  • 求出前k项的和
  • 更新第k项的数据

具体实现：

数组A表示原始数组，数组C作为辅助数组C[i]表示在i之前所有和下标为i有关的数据的和

C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

例如：sum[7] = C7 + C6 +C4，这个式子中的7，6，4是根据每次对二进制位下的末尾进行-1操作得到的，具体的将数字化成二进制一看便知，当减到0的时候停止，这样就求出了前7项的和

树状数组中的关键函数：

lowbit(x)函数：

用来求x在二进制下从最低位开始的第一个1所在位置

int lowbit(int x){
    return x&(-x);
}

getsum(n)函数：

求出前n项的和

int getsum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

update(x,v)函数：

更新第x位置的值

void update(int x,int v){
    a[x] += v;
    while(x <= 32000){
        c[x] += v;
        x += lowbit(x);
    }
}

模板题：

数列操作(array)

Description

给定n个数列,规定有两种操作，一是修改某个元素，二是求子数列[a,b]的连续和。数列元素个数最多10万个，询问操作最多10万次。

Input

第一行2个整数n,m(n表示输入n个数，m表示m操作）

第二行n个整数

接下来m行，每行三个数k,a,b(k=0,表示求子数列 [a,b] 的连续和;k=1，表示第a个数加b)。

Output

若干行,表示k=0时，对应子数列 [a,b] 连续和。

Sample Input 1 

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

Sample Output 1

11
30
35
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+5;
int a[maxn],c[maxn],sum[maxn];
int n,m;

int lowbit(int x){
    return x&(-x);
}

int getsum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void update(int x,int v){
    a[x] += v;
    while(x <= n){
        c[x] += v;
        x += lowbit(x);
    }
}


int main(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++){
        int v;
        cin >> v;
        update(i,v);
    }
    for(int i = 0 ; i < m ; i++){
        int k,a,b;
        cin >> k >> a >> b;
        if(k) update(a,b);
        else cout << getsum(b) - getsum(a-1) << endl;
    }
    return 0;
}

单点修改+区间查询

单点修改+区间查询就是裸的树状数组

int lowbit(int x){
    return x&(-x);
}

int getsum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}


void update(int x,int v){
    while(x <= n){
        c[x] += v;
        x += lowbit(x);
    }
}

区间修改+单点查询

区间修改+单点查询需要借助差分数组，对于差分数组，更新[L,R]区间时，只要更新边界L和边界R+1（原因具体看差分数组的博客）

int lowbit(int x){
    return x&(-x);
}

int getsum(int x){
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void merge(int l,int r,int x){
    //端点l和端点r+1 
    update(l,x),update(r+1,-x);
}


void update(int x,int v){
    while(x <= n){
        c[x] += v;
        x += lowbit(x);
    }
}

区间修改+区间查询

同样需要借助差分数组，下面推一下具体的做法：

求a[i]的和如下：

a[1] = d[1]
a[2] = d[1] + d[2]
a[3] = d[1] + d[2] + d[3]
...
a[n] = d[1] + d[2] +...+ d[n]

所以求数组a的前缀和可以转变成如下公式：

∑i=1na[i]=∑i=1n∑j=1id[j]

由上面的推导过程可知，求前缀和的过程其实就是对数组d求和的过程，d[1]算了n次，d[2]算了n-1次，然后以此类推，所以可以将前缀和转为如下公式：

∑i=1nd[i](n-i+1)=∑i=1n{d[i]*(n+1)-d[i]*i}=(n+1)∑i=1nd[i]+∑i=1nd[i]*i

所以维护两个记录和的数组c1和c2，c1[i] = d[i],c2[i] = i*d[i]，这样在更新时，维护这两个数组即可，查询时[L,R]的和时用右侧端点的前缀和减去左侧端点-1的前缀和就是，就是所求的区间和

int lowbit(int x){
    return x&(-x);
}

int getsum(int x){
    int ans = 0;
    while(x > 0){
        ans += (1+x)*c1[x] - c2[x];
        x -= lowbit(x);
    }
    return ans;
}

void update(int x,int v){
    while(x <= n){
        c1[x] += v;
        c2[x] += x*v;
        x += lowbit(x);
    }
}

void merge(int l,int r,int x){
    //端点l和端点r+1 
    update(l,x),update(r+1,-x);
}