如何高效实现数组的特定规则范围更新及后续索引查询

直接暴力处理每次更新肯定不行——每次更新要遍历O(v)个元素，更新次数多了时间复杂度直接炸。我们可以用二阶差分数组把每次更新的复杂度降到O(1)，最后通过两次前缀和计算得到所有位置的最终值。

规则拆解 #

先把更新规则拆成数学表达式：当在索引i处执行值为v的更新时，每个索引j的增量是max(v - |i-j|, 0)。这个增量可以分成两段线性函数：

• 左半段（j ≤ i且j ≥ i - v）：增量 = j + (v - i)（等价于v - (i - j)）
• 右半段（j ≥ i且j ≤ i + v）：增量 = -j + (v + i)（等价于v - (j - i)）

只有当v - |i-j| ≥ 0时才生效，所以有效范围的左边界L = max(0, i - v)，右边界R = min(n-1, i + v)（n是数组长度）。

二阶差分数组方案 #

我们维护两个差分数组：

• diff2：处理线性项（也就是j的系数）的二阶差分
• diff1：处理常数项的一阶差分

单次更新的操作步骤 #

对每个更新(i, v)：

1. 计算有效范围L = max(0, i - v)，R = min(n-1, i + v)
2. 处理左半段[L, i]：
   • 在diff2[L]加1，diff2[i+1]减1（记录线性项系数+1的区间）
   • 在diff1[L]加(v - i)，diff1[i+1]减(v - i)（记录常数项的区间）
3. 处理右半段[i+1, R]：
   • 在diff2[i+1]减1，diff2[R+1]加1（记录线性项系数-1的区间）
   • 在diff1[i+1]加(v + i)，diff1[R+1]减(v + i)（记录常数项的区间）

计算最终数组 #

所有更新完成后，通过两次前缀和计算得到每个位置的总增量：

1. 计算线性项系数数组coeff：对diff2求前缀和，coeff[j]就是位置j的线性项总系数
2. 计算常数项总和数组const_val：对diff1求前缀和，const_val[j]就是位置j的常数项总增量
3. 每个位置j的最终值 = 初始值 + coeff[j] * j + const_val[j]

示例验证 #

用题目中的例子测试：

• 初始数组：[1,1,1,1,1,1]（n=6）
• 更新操作：i=4，v=3
• 计算有效范围：L = max(0,4-3)=1，R=min(5,4+3)=5

处理左半段[1,4]：

• diff2[1] +=1，diff2[5] -=1
• diff1[1] += (3-4)=-1，diff1[5] -= (-1)=1

处理右半段[5,5]：

• diff2[5] -=1，diff2[6] +=1（超出数组长度，忽略）
• diff1[5] += (3+4)=7，diff1[6] -=7（超出数组长度，忽略）

计算coeff：
[0,1,1,1,1,-1]

计算const_val：
[0,-1,-1,-1,-1,7]

每个位置的增量：

• j=0：0*0+0=0 → 最终值1+0=1
• j=1：1*1 + (-1)=0 → 最终值1+0=1
• j=2：1*2 + (-1)=1 → 最终值1+1=2
• j=3：1*3 + (-1)=2 → 最终值1+2=3
• j=4：1*4 + (-1)=3 → 最终值1+3=4
• j=5：-1*5 +7=2 → 最终值1+2=3

结果和题目示例完全一致。

复杂度分析 #

• 单次更新：O(1)（仅修改4个差分数组位置）
• 计算最终数组：O(n)（两次前缀和遍历）
• 查询单个位置：O(1)（预处理完成后直接取值）

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