AcCoders 7961 Problem D:【省选基础数据结构 树状数组】树状数组 题解
2022/9/10 23:23:31
本文主要是介绍AcCoders 7961 Problem D:【省选基础数据结构 树状数组】树状数组 题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
树状数组板子,单点修改,区间查询,注意处理读入字符的问题。
//7961 Problem D:【省选基础数据结构 树状数组】树状数组 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=100005; ll c[MAXN],a[MAXN],n; #define lowbit(x) ((x)&-(x)) void add(ll x,ll y) { while(x<=n) { c[x]+=y; x+=lowbit(x); } return; } ll sum(ll x) { ll res=0; while(x) { res+=c[x]; x-=lowbit(x); } return res; } int main() { ll m,x,y; char op; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); add(i,a[i]); } /*for(int i=1;i<=n;i++) { cerr<<c[i]<<' '; } cerr<<endl;*/ scanf("%lld",&m); while(m--) { do { op=getchar(); } while(op!='C'&&op!='Q'); scanf("%lld%lld",&x,&y); if(op=='C') { add(x,-a[x]); a[x]=y; add(x,a[x]); } else if(op=='Q') { printf("%lld\n",sum(y)-sum(x-1)); } } return 0; } /* * AcCoders-省选基础5—数据结构 * http://www.accoders.com/problem.php?cid=2716&pid=3 * C++20 -O0 * 2022.9.10 */
这篇关于AcCoders 7961 Problem D:【省选基础数据结构 树状数组】树状数组 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享