题目描述
对于一个长度为的序列，其前缀和为前个元素的和，即。而前缀和的前缀和就是把前缀和序列作为原序列，再求一次前缀和。记再次求得的前缀和序列的第位为
现在给定一个长度为的序列，要执行次操作，有两种操作：
将的值改为
询问的值
输入格式
第一行两个整数n,m，分别表示序列长度和操作个数 接下来一行有n个数，即给定的序列a1,a2,...,an 接下来m行，每行对应一个操作，格式见题面
输出格式
对于每个询问操作，输出一行，表示所询问的SS[i]的值
样例
【样例1输入】
5 3 1 2 3 4 5 Query 5 Modify 3 2 Query 5【样例1输出】
35 32【样例2输入】
5 3 0 0 0 0 0 Query 5 Modify 1 1 Query 5【样例2输出】
0 5【样例3输入】
5 3 11 45 51 77 32 Query 1 Modify 3 93 Query 4【样例3输出】
11 442数据范围与提示
1<=N,M<=100000,0<=Ai<=100000
保证输入合法，保证答案在long long 范围内
一些想法
这道题可以用双树状数组，但是不要用差分数组（因为这道题是求前缀和，而差分数组适用于区间求和，所以这题不适合用差分数组）。
先定义三个数组，一个储存原始数组的数，两个树状数组，用于处理前缀和。然后输入序列的数，然后将序列的数放入树状数组第 i 个位置。
输入操作，如果是修改操作，因为我们的函数是增加或减少的修改函数，但是这里是直接改变数值，那么我们可以先算出改变后的数与要改变的数差是多少，然后用修改函数将要改变的数增加差值就行了（修改树状数组），然后将原数组中要改变的数直接变成改变后的数，使三个数组同步。
查询前缀和的前缀和操作：直接调用函数输出，剩下的在自定义函数写即可。
自定义函数：
lowbit 函数：找一个数二进制中最后一个 1，树状数组划分区间用 lowbit 实现。
修改函数：这次也要新开一个数增加（不能用原数直接加），将维护数组的树状数组加增加的值（第一个数组），将维护 数组 × 位置（第二个数组） 也增加值（更新两个数组），注意这里乘的位置是函数调用的位置，不是循环中到达的位置。
通用查询数组前缀和函数（查询数组 1 ）：这个和之前的一样，求数组 1~对应数 的前缀和，除了在变量多加一个数组（因为不是固定数组，可能是不同的数组，所以直接用调用时的数组），也是向下跳转区间，累加，返回区间和（也就是将一个区间分解成多个小区间，累加起来）。
求前缀和的前缀和（ 查询数组 2 ）函数：公式：(当前位置+1) × (维护数组的数组前缀和) - (维护数组×位置的数组前缀和)。作用：利用双树状数组快速计算原始数组前缀和的前缀和。这里求两个数组的前缀和要用到通用查询数组前缀和函数（查询数组1）。
注意：要用 long long，以免超出界限。
AC代码
#include<bits/stdc++.h> using namespace std; long long n,m,a[100010],b1[100010],b2[100010]; long long lowbit(long long x){ return x&-x; } void zs(long long x,long long y){//修改 for(long long i=x;i<=n;i+=lowbit(i)){ b1[i]+=y; b2[i]+=x*y; } } long long sm1(long long b[],long long x){//查询函数1 long long sum=0; for(;x>0;x-=lowbit(x)) sum+=b[x]; return sum; } long long sm(long long x){//查询函数2 return (x+1)*sm1(b1,x)-sm1(b2,x); } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; zs(i,a[i]); } for(int i=1;i<=m;i++){ string p; cin>>p; if(p=="Modify"){ int x,y; cin>>x>>y; int s=y-a[x]; a[x]=y; zs(x,s); } else{ int x; cin>>x; cout<<sm(x)<<endl; } } return 0; }
