树状数组模板程序讲解1（超详细）

Andy

原来论坛里有OIer，刚好我以前也搞过信息奥赛，就发过来几篇原创的教程吧

> 本文主要介绍和解释树状数组的**单点修改**和**区间查询**的模板
> 区间修改和单点查询请看[树状数组模板程序讲解2（超详细）](https://blog.csdn.net/a_n_d_y_s_u_n__/article/details/119615085)

## 模板题目：
- [题目连接](https://www.luogu.com.cn/problem/P3374)

## 模板代码：

为了方便你对程序的理解，可以在不太清楚的地方结合此图思考一下，能节约思考时间。



讲解请看代码注释

[C++] 纯文本查看 复制代码

#include<iostream>
#include<cstdio>
using namespace std;
int f[2000001],n;  //f用来维护树状数组，n是 数列数字总个数
int lowbit(int a){  //lowbit函数，用来计算a在二进制下从右往左第一个`1`出现的位置（其实说白了就是用来跳转到f中和a有关的变量，实在不懂记住就可以，不用在这里浪费时间）
        return a&-a;  //计算方法，等同于a&(a^(a-1))
}
void add(int x,int k){  //把第x个数加上k
        while(x<=n){  //如果没有越界就一直循环
                f[x]+=k;  //把第x个数加上k
                x+=lowbit(x);  //跳转代码，快速找到包含了f[x]的所有前缀和
        }
        return; //结束（可写可不写）
}
int sum(int x){  //用来计算1~x的前缀和
        int ans(0);   //ans用来累加前缀和
        while(x>0){    //如果没越界
                ans+=f[x];  //ans累加前缀和
                x-=lowbit(x);   //利用lowbit跳转
        }
        return ans;  //返回ans
}
int main(){
        int i,m;
        cin>>n>>m;
        for(i=1;i<=n;++i){
                int a;
                scanf("%d",&a);  //输入
                add(i,a);   //其实直接赋值也可以，但比较复杂，反正初始值都是0，直接加并无大碍
        }
        for(i=1;i<=m;++i){
                int p,x,y;
                scanf("%d%d%d",&p,&x,&y);
                if(p==1){  //判断是那种询问
                        add(x,y);   //给第x个数加y，同时维护树状数组
                }else{
                        printf("%d\n",sum(y)-sum(x-1));  //因为题目要求输出[x,y]的和，其实就等同于sum(y)-sum(x-1)，可以结合图片理解一下，能够减少代码量
                }
        }
}

------

如果还有其他问题可以在下方留言，也可以在[**这里**](https://blog.csdn.net/a_n_d_y_s_u_n__/article/details/119534584)寻找其他更适合适合你的教程~

skystars

感谢，终于弄懂了！