题目描述对于一个长度为的序列其前缀和为前个元素的和即。而前缀和的前缀和就是把前缀和序列作为原序列再求一次前缀和。记再次求得的前缀和序列的第位为现在给定一个长度为的序列要执行次操作有两种操作将的值改为询问的值输入格式第一行两个整数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数据范围与提示1N,M100000,0Ai100000保证输入合法保证答案在long long 范围内一些想法这道题可以用双树状数组但是不要用差分数组因为这道题是求前缀和而差分数组适用于区间求和所以这题不适合用差分数组。先定义三个数组一个储存原始数组的数两个树状数组用于处理前缀和。然后输入序列的数然后将序列的数放入树状数组第 i 个位置。输入操作如果是修改操作因为我们的函数是增加或减少的修改函数但是这里是直接改变数值那么我们可以先算出改变后的数与要改变的数差是多少然后用修改函数将要改变的数增加差值就行了修改树状数组然后将原数组中要改变的数直接变成改变后的数使三个数组同步。查询前缀和的前缀和操作直接调用函数输出剩下的在自定义函数写即可。自定义函数lowbit 函数找一个数二进制中最后一个 1树状数组划分区间用 lowbit 实现。修改函数这次也要新开一个数增加不能用原数直接加将维护数组的树状数组加增加的值第一个数组将维护 数组 × 位置第二个数组 也增加值更新两个数组注意这里乘的位置是函数调用的位置不是循环中到达的位置。通用查询数组前缀和函数查询数组 1 这个和之前的一样求数组 1~对应数 的前缀和除了在变量多加一个数组因为不是固定数组可能是不同的数组所以直接用调用时的数组也是向下跳转区间累加返回区间和也就是将一个区间分解成多个小区间累加起来。求前缀和的前缀和 查询数组 2 函数公式(当前位置1) × (维护数组的数组前缀和) - (维护数组×位置的数组前缀和)。作用利用双树状数组快速计算原始数组前缀和的前缀和。这里求两个数组的前缀和要用到通用查询数组前缀和函数查询数组1。注意要用 long long以免超出界限。AC代码#includebits/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 ix;in;ilowbit(i)){ b1[i]y; b2[i]x*y; } } long long sm1(long long b[],long long x){//查询函数1 long long sum0; for(;x0;x-lowbit(x)) sumb[x]; return sum; } long long sm(long long x){//查询函数2 return (x1)*sm1(b1,x)-sm1(b2,x); } int main(){ cinnm; for(int i1;in;i){ cina[i]; zs(i,a[i]); } for(int i1;im;i){ string p; cinp; if(pModify){ int x,y; cinxy; int sy-a[x]; a[x]y; zs(x,s); } else{ int x; cinx; coutsm(x)endl; } } return 0; }