首页 > 代码库 > 一维数状数组区间修改，查询
一维数状数组区间修改，查询
模板题CODEVS-1082
给你N个数，有两种操作：
1：给区间[a,b]的所有数增加X
2：询问区间[a,b]的数的和。
第一行一个正整数n，接下来n行n个整数，
再接下来一个正整数Q，每行表示操作的个数，
如果第一个数是1，后接3个正整数，
表示在区间[a,b]内每个数增加X,如果是2，
表示操作2询问区间[a,b]的和是多少。
一维树状数组可以考虑用差分来做，但是扩展不到二维。
所以我们令di=(ai~an)的增量
思路和差分一样，可以扩展到二维（现在还没懂）
#include<iostream>#include<cstdio>#include<algorithm>#define rep(i,a,b) for(int i=a;i<=b;i++)using namespace std;#define lowbit(x) x&(-x)int n,m,a[1000005],c1[1000005],c2[1000005];void update(int v,int val){ for(int pp=v;pp<=n;c1[pp]+=val,c2[pp]+=val*v,pp+=lowbit(pp));}int query(int l,int r){ int ans=0; for(int pp=r;pp>0;ans+=(r+1)*c1[pp],ans-=c2[pp],pp-=lowbit(pp)); l--; for(int pp=l;pp>0;ans-=(l+1)*c1[pp],ans+=c2[pp],pp-=lowbit(pp)); return ans;}int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) update(i,a[i]-a[i-1]); for(int i=1;i<=m;i++) { int p,l,r,val; scanf("%d %d %d",&p,&l,&r); if(p==1) { scanf("%d",&val); update(l,val); update(r+1,-val); }else { printf("%d\n",query(l,r)); } } return 0;}
一维数状数组区间修改，查询
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。