首页 > 代码库 > [bzoj3155]Preprefix sum(树状数组)
[bzoj3155]Preprefix sum(树状数组)
3155: Preprefix sum
Time Limit: 1 Sec Memory Limit: 512 MBSubmit: 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
1 2 3 4 5
Query 5
Modify 3 2
Query 5
Sample Output
35
32
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 }
[bzoj3155]Preprefix sum(树状数组)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。