[bzoj3155]Preprefix sum(樹狀數組) - Pumbit-Legion @ IT工程師數位筆記本

文章出處

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\n",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 }