0017：【模板】树状数组

题目链接：https://www.luogu.com.cn/problem/P3374

题目描述：

已知一个数列，你需要进行下面两种操作：

1.将某一个数加上 x

2.求出某区间每一个数的和

看到这道题，首先想到的是直接数组模拟。

不用多说了吧？是人都会。

但是数组模拟求区间和的单次时间复杂度是O（n），本题的数据范围最大是（5*10^5）^2，很容易爆掉。（本题只有70分）

那么就要介绍一下这次的算法——树状数组了。

树状数组或二叉索引树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。

——摘自百度

说白了就是能让区间和计算变快的算法。我画个图演示一下大概的思想。

 

 

 C1=A1

C2=A1+A2

C3=A3

C4=A1+A2+A3+A4

C5=A5

C6=A5+A6

C7=A7

C8=A1+A2+A3+A4+A5+A6+A7+A8

 

 C数组就是像树一样将A数组的区间联系起来的树状数组。

那么如何用C数组找到A数组呢？

这就用到一条神奇的语句：

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

大家可以自行上c++模拟一下。

上代码：

#include<bits/stdc++.h>
using namespace std;
int A[500005],C[500005];
int n,m,i,j,a,b,c;
int lowbit(int x){//实现A数组与C数组的转换 
    return x&(-x);
}
void add(int w,int k){//将序列内某个元素加上k 
    while(w<=n){//将每个C数组中包含此元素的元素都加上k 
        C[w]+=k;
        w+=lowbit(w);
    }
}
int Q(int x){//从A1到Ax的区间和，用C数组求 
    int we=0;
    while(x>0){
        we+=C[x];
        x-=lowbit(x);//从x搜索，找出之前不包含A1~Ax的元素 
    }
    return we;
}
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        add(i,A[i]);
    }
    for(i=0;i<m;i++){
        scanf("%d",&a);
        if(a==1){
            scanf("%d%d",&b,&c);
            add(b,c);
        }else{
            scanf("%d%d",&b,&c);
            cout<<Q(c)-Q(b-1)<<endl;
        }
    }
}