首页 > 代码库 > 树状数组区间加区间求和
树状数组区间加区间求和
一般说来,树状数组比线段树好写得多,可是只用于单点修改。
然后最近学到一种区间修改的方式,区间加区间求和。
这里我们不直接维护原数组,而是引入另一个数组b[i],表示和前一个数的差是多少。
这样的话a[i]就可以表示为b[1]+b[2]+b[3]……b[i],相对应的,sum(i)就是b[1]+b[1]+b[2]+b[1]+b[2]+b[3]……b[1]+b[2]+b[3]…b[i]=(n+1)*sum(b[i])-sum(b[i]*i)
这样就转化成维护b[i]的前缀和以及b[i]*i的前缀和了。修改的区间[l,r]时候,只有b[l]和b[r+1]两个点会变化,所以单点修改两次就能得到正解了。
下面是处理区间更新、求和的代码,有点冗余,懒得改了。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 long long n,m; 7 long long c1[200011],c2[200011]; 8 long long a[200011],b[200011]; 9 10 long long read() 11 { 12 long long x=0,f=1;char c=getchar(); 13 while (!isdigit(c)) {if (c==‘-‘)f=-1;c=getchar();} 14 while (isdigit(c)) {x=x*10+c-‘0‘;c=getchar();} 15 return x*f; 16 } 17 18 long long lowbit(long long x) 19 { 20 return x&-x; 21 } 22 23 void update1(long long pos,long long v) 24 { 25 while (pos<=n) 26 { 27 c1[pos]+=v;pos+=lowbit(pos); 28 } 29 } 30 31 void update2(long long pos,long long v) 32 { 33 while (pos<=n) 34 { 35 c2[pos]+=v;pos+=lowbit(pos); 36 } 37 } 38 39 long long query1(long long pos) 40 { 41 long long sum=0; 42 while (pos) 43 { 44 sum+=c1[pos];pos-=lowbit(pos); 45 } 46 return sum; 47 } 48 49 long long query2(long long pos) 50 { 51 long long sum=0; 52 while (pos) 53 { 54 sum+=c2[pos];pos-=lowbit(pos); 55 } 56 return sum; 57 } 58 59 int main() 60 { 61 n=read(); 62 for (long long i=1;i<=n;i++) 63 a[i]=read(); 64 b[1]=a[1]; 65 for (long long i=2;i<=n;i++) b[i]=a[i]-a[i-1]; 66 for (long long i=1;i<=n;i++) update1(i,b[i]),update2(i,b[i]*i); 67 m=read(); 68 for (long long i=1;i<=m;i++) 69 { 70 long long d=read(),x=read(),y=read(),v; 71 if (d==1) 72 { 73 v=read();update1(x,v);update1(y+1,-v);update2(x,x*v);update2(y+1,-(y+1)*v); 74 } 75 else 76 { 77 long long tmp1,tmp2;tmp1=(y+1)*query1(y)-query2(y);tmp2=x*query1(x-1)-query2(x-1); 78 cout << tmp1-tmp2 << "\n"; 79 } 80 } 81 return 0; 82 }
树状数组区间加区间求和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。