今天学了树状数组awa

这个数据结构在某些特殊的情况下可以代替前缀和
（如 洛谷P3374 等……）
目前的模板支持以下操作：
1.单个元素增值：1 x y
含义：将第x个数加上y
2.区间元素求和：2 x y
含义：输出从x到y之间每个数的和(包括x和y)

#include<iostream>
using namespace std;
//元素数量,操作数量，原数组，树状数组；
int n,m,lis[514114],tre[514114];
//lowbit函数；
inline int lbt(int x){return x & (-x);}
//增值函数（将第id个元素加x）；
void add(int id,int x){
    //原数组直接增加；
    lis[id]+=x;
    for(int i=id;i<=n;i+=lbt(i)){
        tre[i]+=x;
    }//树状数组↑一层一层的加；
}
//区间求和函数（计算从left到right之间每个数的和，包括left和right）；
int sum(int left,int right){
    //左区间和，右区间和；
    int anslwer=0,ansrwer=0;
    for(int i=left-1;i>0;i-=lbt(i)){anslwer+=tre[i];}//逐层；
    for(int i=right;i>0;i-=lbt(i)){ansrwer+=tre[i];} //计算；
    //区间和=右区间和-左区间和；
    return ansrwer-anslwer;
}
int main(){
    //输入元素数量于操作数量；
    scanf("%d %d",&n,&m);
    //输入原数组的同时初始化树状数组；
    for(int i=1;i<=n;i++){scanf("%d",&lis[i]);tre[i]=0;}
    for(int i=1;i<=n;i++){
        for(int ii=i-lbt(i)+1;ii<=i;ii++){
            tre[i]+=lis[ii];
        }//逐个构建；
    }//    树状数组；
    //开始进行操作；
    for(int i=1,mod,x,y;i<=m;i++){
        //输入操作编号与两个参数；
        scanf("%d %d %d",&mod,&x,&y);
        //若操作编号为1；
        if(mod==1){
            //第x项增加y（详情见 line 16~23）；
            add(x,y);
        }else if(mod==2){//若操作编号为1；
            //输出求和结果（详情见 line 24~32）；
            printf("%d\n",sum(x,y));
        }else{//否则；
            printf("Input Error!!!");
            return/*异常结束*/-1;
        }//只有输入错误时↑才会运行；
    }
    return/*结束*/0;
}
<z
^z

当前版本：1.5