TZOJ 5694 区间和II(树状数组区间加区间和)

描述

给定n个整数，有两个操作：

（1）给某个区间中的每个数增加一个值；

（2）查询某个区间的和。

输入

第一行包括两个正整数n和q（1<=n, q<=100000），分别为序列的长度和操作次数；

第二行包含n个整数，a₁, a₂, ... , a_n，-1000000000 ≤ a_i ≤ 1000000000；

接下来又q行，每行为以下操作之一：

（1）更新，C i, j x：将 x加到元素a_i, a_i+1, ... , a_j中，其中-10000 ≤ x ≤ 10000；
（2）查询，Q i j：求元素ai, ai+1, ... , aj的和。

输出

针对每次查询操作，输出结果值。

样例输入

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

样例输出

4
55
9
15

题意

如上

题解

令

b[i]=a[i]-a[i-1]

那么

a[x]=Σb[i](1<=i<=x)

区间求和

Σa[i](1<=i<=x)

=ΣΣb[j](1<=i<=x,1<=j<=i)

=Σ(x-i+1)*b[i](1<=i<=x)

=(x+1)*Σb[i](1<=i<=x)-Σi*b[i](1<=i<=x)

那么同时维护b[i]和i*b[i]即可得到区间和

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 const int N=1e5+5;
 6 int n;
 7 ll b1[N],b2[N];
 8 void update(int x,ll w)
 9 {
10     for(int i=x;i<=n;i+=i&(-i))
11         b1[i]+=w,b2[i]+=w*x;
12 }
13 ll query(int x)
14 {
15     ll ans=0;
16     for(int i=x;i>0;i-=i&(-i))
17         ans+=b1[i]*(x+1)-b2[i];
18     return ans;
19 }
20 int main()
21 {
22     int q,a,b;
23     ll x,c;
24     char s[2];
25     scanf("%d%d",&n,&q);
26     for(int i=1;i<=n;i++)
27     {
28         scanf("%lld",&x);
29         update(i,x),update(i+1,-x);
30     }
31     while(q--)
32     {
33         scanf("%s%d%d",s,&a,&b);
34         if(s[0]=='C')
35         {
36             scanf("%lld",&c);
37             update(a,c),update(b+1,-c);
38         }
39         else printf("%lld
",query(b)-query(a-1));
40     }
41     return 0;
42 }

TZOJ 5694 区间和II(树状数组区间加区间和)

相关推荐