首页 > 代码库 > 树状数组区间修改
树状数组区间修改
codevs 1082
白书上很详尽。维护两个东西,一个是差量,也就是哪一段被更新了多少,还有一个也是差量,只不过是记录一共减了多少。(说不清)
然后根据白书上的式子,自己yy一下。还是不是很懂
#include<cstdio> #include<cstring> using namespace std; #define lowbit(x) x&-x #define N 200010 typedef long long ll; int n,q; ll sum[N],t1[N],t2[N]; void add1(int pos,int delta) { for(int i=pos;i<=n;i+=lowbit(i)) t1[i]+=delta; } void add2(int pos,int delta) { for(int i=pos;i<=n;i+=lowbit(i)) t2[i]+=delta; } ll sum1(int pos) { ll ret=0; for(int i=pos;i>0;i-=lowbit(i)) ret+=t1[i]; return ret; } ll sum2(int pos) { ll ret=0; for(int i=pos;i>0;i-=lowbit(i)) ret+=t2[i]; return ret; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&sum[i]); sum[i]+=sum[i-1]; } scanf("%d",&q); while(q--) { int opt,a,b; scanf("%d%d%d",&opt,&a,&b); if(opt==1) { int x; scanf("%d",&x); add1(a,-(a-1)*x); add1(b+1,b*x); add2(a,x); add2(b+1,-x); } else { printf("%lld\n",sum[b]-sum[a-1]+sum1(b)-sum1(a-1)+sum2(b)*b-sum2(a-1)*(a-1)); } } return 0; }
树状数组区间修改
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。