如何优化数组L到R区间批量加值操作的代码运行效率

问题说明 #

现有长度为N的数组A，需要执行Q次操作，每次操作格式为X L R，含义是将数值X加到数组A中从位置L到R的所有元素上（L、R为1起始索引）。
给定参数示例：

N=5
A=[1, 4, 3, 2, 4]
Q=2
操作列表 = [[5, 1, 2],
            [-5, 1, 3]]

原有暴力实现采用双层循环，外层遍历Q次操作，内层遍历每次操作的区间逐元素加值，时间复杂度为O(QN)*，当N、Q规模达到1e4以上时运行耗时会明显升高，规模到1e5级别时基本会超时。

最优优化方案：差分数组 #

差分数组可以将整体时间复杂度降到O(N+Q)，核心逻辑是把区间操作的成本从O(区间长度)压缩到O(1)，最后统一计算所有增量的叠加效果，原理如下：

• 初始化长度为N+1的全0差分数组diff，多开1位是为了避免区间右边界到数组末尾时的索引越界
• 对每一次区间加X操作，仅做两次单点修改：
  • diff[L-1] += X：标记增量从L位置（转0索引为L-1）开始生效
  • diff[R] -= X：标记增量从R+1位置（转0索引为R）开始失效
• 所有操作处理完成后，遍历一次差分数组计算前缀和，得到每个位置需要叠加的总增量，和原数组对应位置相加即可得到最终结果。

优化后代码实现 #

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
# 初始化差分数组
diff = [0] * (N + 1)

for _ in range(Q):
    X, L, R = map(int, input().split())
    diff[L-1] += X
    diff[R] -= X

# 计算前缀和叠加增量
current_add = 0
for i in range(N):
    current_add += diff[i]
    A[i] += current_add

# 按需输出最终数组
# print(A)

效果验证 #

用题目给出的示例跑流程验证：

两次操作执行后，diff数组有效位为[0, 0, -5, 5, 0]
计算前缀和得到每个位置的增量依次为0、0、-5、0、0
叠加原数组后结果为[1, 4, -2, 2, 4]，和暴力实现逐元素计算的结果完全一致。

如果后续还需要穿插区间查询、单点修改的操作，可以替换为树状数组或线段树实现，但对于只有区间增量、最后统一取结果的场景，差分数组是代码量最小、运行速度最快的方案。

内容的提问来源于stack exchange，提问作者Akash Kumar