题目描述如题已知一个数列你需要进行下面两种操作将某区间每一个数加上 x求出某一个数的值。输入格式第一行包含两个整数 N、M分别表示该数列数字的个数和操作的总个数。第二行包含 N 个用空格分隔的整数其中第 i 个数字表示数列第 i 项的初始值。接下来 M 行每行包含 2 或 4 个整数表示一个操作具体如下操作 1 格式1 x y k含义将区间 [x,y] 内每个数加上 k操作 2 格式2 x含义输出第 x 个数的值。输出格式输出包含若干行整数即为所有操作 2 的结果。输入输出样例输入 #1复制运行5 5 1 5 4 2 3 1 2 4 2 2 3 1 1 5 -1 1 3 5 7 2 4输出 #1复制运行6 10说明/提示样例 1 解释故输出结果为 6 和 10。数据规模与约定对于 30% 的数据N≤8M≤10对于 70% 的数据N≤104M≤104对于 100% 的数据1≤N,M≤5×1051≤x,y≤n保证任意时刻序列中任意元素的绝对值都不大于 230。一、 题目分析本题是树状数组的第二种经典模型区间修改单点查询。操作特性频繁地对一个连续区间[x,y]内的所有元素加上一个值k并随时抽查某一个位置x 的当前值。数据规模N,M≤5×10^5这意味着暴力的O(N)修改或查询都会导致程序在1s的时限内超时。必须寻找一种将修改和查询都压低到O(logN)级别的数据结构。二、 思考过程在向学生推导时可以展示以下三次思维的迭代过程纯暴力法普通数组每次区间修改需要for循环遍历[x,y]时间复杂度O(N)单点查询 O(1)。操作M次必超时。差分数组法普通差分引入差分数组 D[i]A[i]−A[i−1]。区间修改瞬间变成 O(1)只需修改端点D[x]k, D[y1]−k。但单点查询需要求D的前缀和时间退化为O(N)。操作M次依然会超时。终极形态树状数组差分既然差分数组的修改极快只是“求前缀和”太慢那我们就把差分数组存进专门用来光速求前缀和的树状数组里这样区间修改转化为两次单点修改和单点查询转化为前缀求和的时间复杂度被完美平衡到了 O(logN)。三、 解题思路本题的核心是完成逻辑与物理的分离逻辑上我们在操作一个差分数组D。对原数组[x,y]区间加k等价于让差分数组D[x]增加 kD[y1]减少 k。原数组的单点值A[x]等于差分数组的前缀和。物理上我们在代码里只声明一个树状数组C。所有的update操作都是在借用树状数组的 O(logN)通道去更新底层的差分状态所有的query操作都是在借用树状数组通道去秒速求取差分数组的前缀和。四、 算法设计建树读取初始数组 A[i] 时动态计算差分值A[i]-A[i-1]并立刻调用update(i, A[i]-A[i-1])塞入树状数组。区间修改操作 1读取x,y,k。调用update(x, k)和update(y1,-k)。单点查询操作 2读取x。直接调用并输出query(x)的结果。五、 时空复杂度分析时间复杂度建树阶段共N次单点修改时间O(NlogN)。操作阶段M次操作每次操作最多调用2次树状数组函数时间O(MlogN)。总体时间复杂度O((NM)logN)对5×10^5的数据规模可轻松在0.1s内跑完。空间复杂度仅需常数个长度为N的一维数组总体空间复杂度O(N)。六、 易错点总结2^30带来的整型溢出题目约定元素的绝对值不大于2^30逼近int的极限 2^31−1。树状数组C[i]存储的是多个差分值的叠加且后续有多次区间累加操作有概率在中途计算时爆int产生负数。全员上long long更优。y1越界风险极易RE或越界污染当修改区间右端点yN时update(y1,-k)会访问到N1的位置。如果数组只开了刚好500000就会越界。数组大小务必多开个10到15的余量如500015。IO 竞速问题极易 TLE百万级别的输入输出不要直接使用cin/cout要配合ios::sync_with_stdio(false); cin.tie(0);不要使用endl。虽然本题用了也能过七、 完整代码#include iostream using namespace std; //涉及树状数组求和最好全部开long long typedef long long ll; int n,m; ll c[500010];//树状数组 ll a[500010];//原数列 ll d[500010];//原数列的差分数组 //返回x二进制表示下最右边的最低位的1所表示的整数 int lowbit(int x){ return x(-x); } //树状数组单点更新 x代表更新树状数组中所有包含原数列差分数组第x项的位置val代表增减的值将底层数组-差分数组的第x项加上val) void update(int x,ll val){ for(int ix;in;ilowbit(i)){ c[i]val; } } //查询 树状数组标准前缀求和 求底层数组差分数组d前x项的和 ll query(int x){ ll ret0; while(x0){ retc[x]; x-lowbit(x); } return ret; } int main(){ //IO加速 ios::sync_with_stdio(false); cin.tie(0); cinnm; //边读入原数组 边利用差分思想建树 for(int i1;in;i){ cina[i]; //存储原数列的差分数组 这里仅做演示 d数组其实并不需要 d[i]a[i]-a[i-1]; //我们直接用树状数组c去存储d数组即可 update(i,d[i]); } //接下来要进行m次操作 for(int i1;im;i){ //每次操作包含2或4个整数 int flag; cinflag; if(flag1){//将区间[x,y]内每个数加上k int x,y; ll k; cinxyk; //差分将区间修改变成两次单点修改 update(x,k);//起点增加k update(y1,-k);//终点之后的第一个点减少k } else{//输出第x个数的值 int x; cinx; //因为底层维护的是差分数组 //其前缀和就是原数组的单点真实值 coutquery(x)\n; } } return 0; }