[bzoj3155]Preprefix sum(树状数组)

3155: Preprefix sum

Time Limit: 1 Sec Memory Limit: 512 MB
Submit: 1183 Solved: 546
[Submit][Status][Discuss]

Description

Input

第一行给出两个整数N，M。分别表示序列长度和操作个数

接下来一行有N个数，即给定的序列a1,a2,....an

接下来M行，每行对应一个操作，格式见题目描述

Output

对于每个询问操作，输出一行，表示所询问的SSi的值。

Sample Input

5 3
1 2 3 4 5
Query 5
Modify 3 2
Query 5

Sample Output

35
32

HINT

1<=N,M<=100000,且在任意时刻0<=Ai<=100000

Source

Katharon+#1

学过线段树都知道树状数组不能处理区间修改，无逆元的区间加法

但是树状数组其实用差分可以做区间修改单点查询

当然这道题和更强的区间修改求和关系不大，但形式确实很像

对于原数列a1,a2,a3,a4...

S为 1*a1, 1*a1+1*a2, 1*a1+1*a2+1*a3...

SS为1*a1, 2*a1+1*a2, 3*a1+2*a2+1*a3...

观察系数，发现从大到小变化，但序号却由小到大

比较一下，可以尝试把S乘一个i,消掉系数最大的

得到 1*a1, 2*a1+2*a2, 3*a1+3*a2+3*a3...

这样与SS作差，就可以又得到一个系数与序号正比的式子

0*a1, 0*a1+1*a2, 0*a1+1*a2+2*a3...

再观察，这就是个前缀和而已

所以维护一遍原前缀和，再维护(i-1)*a[i]的前缀和即可

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define LL long long
 5 int n,m;
 6 LL a[101000],bit1[101000],bit2[101000];
 7 int lb(int x){
 8     return x&(-x);
 9 }
10 LL q1(int x){
11     LL ans=0;
12     while(x){
13         ans+=bit1[x];
14         x-=lb(x);
15     }
16     return ans;
17 }
18 LL q2(int x){
19     LL ans=0;
20     while(x){
21         ans+=bit2[x];
22         x-=lb(x);
23     }
24     return ans;
25 }
26 int c1(int x,LL num){
27     while(x<=n){
28         bit1[x]+=num;
29         x+=lb(x);
30     }
31     return 0;
32 }
33 int c2(int x,LL num){
34     while(x<=n){
35         bit2[x]+=num;
36         x+=lb(x);
37     }
38     return 0;
39 }
40 int main(){
41     scanf("%d %d",&n,&m);
42     for(int i=1;i<=n;i++){
43         scanf("%lld",&a[i]);
44         c1(i,a[i]);
45         c2(i,(i-1)*a[i]);
46     }
47     for(int i=1;i<=m;i++){
48         char in[10];
49         scanf("%s",in);
50         if(in[0]=='Q'){
51             int x;
52             scanf("%d",&x);
53             printf("%lld
",x*q1(x)-q2(x));
54         }else{
55             int x;
56             LL y;
57             scanf("%d %lld",&x,&y);
58             LL tmp=y-a[x];
59             a[x]+=tmp;
60             c1(x,tmp);
61             c2(x,(x-1)*tmp);
62         }
63     }
64     return 0;
65 }

View Code

//p.s. 其实这道题提供了树状数组处理区间修改区间求和的一个方法

对于对一个数列进行区间修改区间求和，为了快速修改，需要进行差分，但求和就比较困难

对于区间求和，就相当于求区间差分前缀的前缀

应用上面的方法，就可以方便的解决这个问题

(完虐线段树oooooooooooooooooo)

//p.p.s.难道我讲的不清楚吗...