X64论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

热搜: 样本 软件
查看: 87|回复: 1

[计算机竞赛] 树状数组模板程序讲解1(超详细)

[复制链接]

0

技术

1

魅力

1

原创

实习版主

Rank: 7Rank: 7Rank: 7

积分
2014
人气
64
分享
43

最佳新人活跃会员

发表于 2022-3-6 11:54:12 | 显示全部楼层 |阅读模式
原来论坛里有OIer,刚好我以前也搞过信息奥赛,就发过来几篇原创的教程吧

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

## 模板题目:
- [题目连接](https://www.luogu.com.cn/problem/P3374)
![](?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Ffbl9kX3lfc191X25fXw==,size_16,color_FFFFFF,t_70#pic_center)

## 模板代码:

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

![](#pic_center)


讲解请看代码注释
[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)寻找其他更适合适合你的教程~

评分

参与人数 1人气 +2 分享 +2 原创 +1 收起 理由
skystars + 2 + 2 + 1 补发原创

查看全部评分

来自广东
是一名OIer
也是一名中国红客
也是一名青年工程师
也是一名科技创新特长生
现在高一,就读松湖莞中
QQ:944898918
回复

使用道具 举报

1

技术

21

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
8660
人气
263
分享
42

优秀版主活跃会员最佳新人灌水之王

发表于 2022-3-6 12:47:26 | 显示全部楼层
感谢,终于弄懂了!
一个蒟蒻
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|X64论坛 ( 沪ICP备2020028431号-4 )|网站地图

GMT+8, 2022-5-20 06:20 , Processed in 0.062386 second(s), 13 queries , MemCache On.

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表