首页 > 代码库 > 树状数组 模板 单点更新 区间求和
树状数组 模板 单点更新 区间求和
(来自luogu)原题目
lowbit(x)=2^k次幂，k为x末尾0的数量。大家可以模拟试试lowbit
(-x)=(~x)+1，把x取反+1
void update(int x,int k)表示a[x]+=k（单点更新）
int sum(int x)表示求1-x区间和
求x-y区间和只需要sum(y)-sum(x-1)即可
#include <iostream>#include <string>#include <cstring>#define lowbit(x) ((x)&(-(x)))//这里也可以写函数233using namespace std;int c[524288+1],n,m,x,y,z;void update(int x,int k)//a[x]+=k;
{ for(int i=x;i<=n;i+=lowbit(i)) c[i]+=k;}int sum(int x)//int ans=0;for(int i=1;i<=x;i++)ans+=a[i];return ans;
{ int ans=0; for(int i=x;i>0;i-=lowbit(i)) ans+=c[i]; return ans;}int main()
{ cin >> n >> m; for(int i=1;i<=n;i++) { cin >> x; update(i,x); } for(int i=1;i<=m;i++) { cin >> x >> y >> z; if(x==1)update(y,z); if(x==2)cout << sum(z)-sum(y-1) << endl; } return 0;}
233
树状数组 模板 单点更新 区间求和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。