如何实现O(N+Q)复杂度的数组等差增量区间更新 类似差分数组用法

完全可以做到O(N+Q)的时间复杂度完成所有更新，核心是用二阶差分数组，原理和普通差分数组处理区间加常数的逻辑一致，只是针对等差序列更新做了升级。

操作规则 #

你的每次更新本质是给区间[start, end]依次加首项为1、公差为1的等差数列，单次更新可以在O(1)时间内完成，最后两次前缀和计算得到最终数组。

具体步骤如下：

• 初始化一个长度为N+2的二阶差分数组diff2，初始值全为0（多开2位是为了避免边界越界）。
• 对每一次更新操作，设起始下标为L=start，终止下标为R=end，做如下修改：

  diff2[L] += 1;
  diff2[R + 1] -= (R - L + 2);
  diff2[R + 2] += (R - L + 1);
  

  （注：公式推导后首项为1、公差为1的场景下，L+1位置的修改值为0，可直接省略操作）
• 所有更新完成后，对diff2做第一次前缀和，得到一阶差分数组diff1：

  // 以下为数组下标从1开始的写法，0起始下标对应调整即可
  diff1[1] = diff2[1];
  for (int i = 2; i <= N; i++) diff1[i] = diff1[i-1] + diff2[i];
  

• 对diff1做第二次前缀和，得到最终的目标数组v：

  v[1] = diff1[1];
  for (int i = 2; i <= N; i++) v[i] = v[i-1] + diff1[i];
  

复杂度说明 #

• Q次更新操作总时间复杂度为O(Q)
• 两次前缀和计算总时间复杂度为O(N)
• 整体复杂度为O(N+Q)，完全符合要求。

如果你的数组下标是从0开始的，只需要对应调整边界判断逻辑即可，核心规则不变。

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