首页 > 代码库 > 树状数组区间加区间求和

树状数组区间加区间求和

2024-10-20 19:18:39   213人阅读

一般说来，树状数组比线段树好写得多，可是只用于单点修改。

然后最近学到一种区间修改的方式，区间加区间求和。

这里我们不直接维护原数组，而是引入另一个数组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 }

 

树状数组区间加区间求和


联系
我们