首页 > 代码库 > 【学习整理】树状数组 区间修改+查询
【学习整理】树状数组 区间修改+查询
前言:对于区间修改和区间查询这样的简单问题,打一大堆线段树确实是不划算,所以学习了区间修改+区间修查询的树状数组。
我们定义 为原数列, ,显然 。
若想要将区间 的数全部 则只需要将 , 即可。
所以,我们维护一个数组
在将区间 的数全部 则还需同时将 , 。
结论:
例题:CODEVS1082 线段树练习3
http://codevs.cn/problem/1082/
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n,q; long long a[200005],c[3][200005]; long long lowbit(long long x){return x&(-x);} void modify(int x,long long pos,long long v){for(;pos<=n;pos+=lowbit(pos)) c[x][pos]+=v;} long long query(int x,long long pos){long long ret=0LL;for(;pos;pos-=lowbit(pos)) ret+=c[x][pos];return ret;} int main() { int i,j,opt; long long l,r,v,sum1,sum2; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%lld",&a[i]); modify(1,i,a[i]-a[i-1]); modify(2,i,(i-1)*(a[i]-a[i-1])); } scanf("%d",&q); for(i=1;i<=q;i++) { scanf("%d%lld%lld",&opt,&l,&r); if(opt==1) { scanf("%lld",&v); modify(1,l,v);modify(1,r+1,-v); modify(2,l,v*(l-1));modify(2,r+1,-v*r); } else { sum1=(l-1)*query(1,l-1)-query(2,l-1); sum2=r*query(1,r)-query(2,r); printf("%lld\n",sum2-sum1); } } return 0; }
【学习整理】树状数组 区间修改+查询
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。