GESP 八级 · GESP202609 C++ 八级 第 14 题

对长度为 n 的数组使用差分数组支持 m 次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个过程的渐进时间复杂度为（　　）。

差分数组的核心思想是将区间操作转化为端点修改。每次区间加操作只需修改差分数组的两个位置，耗时O(1)。最后通过一次前缀和还原数组，耗时O(n)。总操作次数为m次区间加+1次前缀和，故复杂度为O(m+n)。

选项A误以为每次区间加需遍历整个区间，忽略了差分数组的本质；选项B/C混淆了前缀和与二分查找的复杂度关系；选项D看似简单却精准抓住了"一次前缀和"这一关键约束。

1. 考纲定位

本题对应GESP八级《算法与数据结构》模块中"差分数组"考点。命题人专门设置此题，就是要卡住那些只会暴力区间更新、不懂差分优化的考生——他们看到区间加操作，第一反应是O(n)遍历，完全没意识到端点修改的O(1)特性。

2. 解题思维

看到"区间加操作"先想：能否用差分把区间操作转化为点操作？关键观察是：区间[l,r]加v，等价于diff[l]+=v且diff[r+1]-=v。这样m次操作仅需2m个修改，O(m)完成。最后还原时，从diff[1]开始累加到diff[n]，O(n)遍历。总复杂度O(m+n)。