一批操作都对连续格子加上同一个高度时,逐格反复修改会产生许多重复工作。也可以先把每次影响的开始与结束记下来,再沿地图累计恢复结果。
一维地图有十二格,每个操作给出起点l、终点r和增加量v,范围为左闭右开。差分表在l处加v,在r处减v,长度为十三;最后从左到右累加差分,与原高度相加得到新地形。
本例输入与约定
原高度[1, 3, 1, -1, 2, -2, 5, 4, 5, 7, 5, 2];每条操作为起点、终点、增加量。
完整计算记录
操作 | 操作后的十三项差分 [8, 9, -4] | [0, 0, 0, 0, 0, 0, 0, 0, -4, 4, 0, 0, 0] [5, 11, -4] | [0, 0, 0, 0, 0, -4, 0, 0, -4, 4, 0, 4, 0] [10, 12, -4] | [0, 0, 0, 0, 0, -4, 0, 0, -4, 4, -4, 4, 4] [3, 12, 5] | [0, 0, 0, 5, 0, -4, 0, 0, -4, 4, -4, 4, -1] [10, 11, 1] | [0, 0, 0, 5, 0, -4, 0, 0, -4, 4, -3, 3, -1] [0, 8, 5] | [5, 0, 0, 5, 0, -4, 0, 0, -9, 4, -3, 3, -1] [9, 12, 5] | [5, 0, 0, 5, 0, -4, 0, 0, -9, 9, -3, 3, -6] [6, 8, 5] | [5, 0, 0, 5, 0, -4, 5, 0, -14, 9, -3, 3, -6] [3, 6, 5] | [5, 0, 0, 10, 0, -4, 0, 0, -14, 9, -3, 3, -6] [3, 6, -2] | [5, 0, 0, 8, 0, -4, 2, 0, -14, 9, -3, 3, -6] 累计修改量:[5, 5, 5, 13, 13, 9, 11, 11, -3, 6, 3, 6] 最终高度:[6, 8, 6, 12, 15, 7, 16, 15, 2, 13, 8, 8]
表中编号仅用于识别本例的元素。读取一个结果时,应先核对它对应的输入、处理顺序和边界约定;布尔值表示条件是否成立,空集合表示没有符合要求的对象,不应把这些字段混成同一种数值。
复核方法与适用范围
终点所在格不受该次操作影响,但差分表必须能保存地图末尾位置十二的停止标记。每次加减成对出现,所以完整差分表总和为零;负数增加量表示下调,并非无效输入。
这种写法适合先收集修改、再统一恢复的批量流程。如果每次修改后都立即查询任意区间,需要另外安排数据结构;本例也没有高度上下限,限制值会改变叠加方式。
练习时可以先独立计算最前面的一步,再检查最后的整体不变量。若结论不同,应保留各步记录,定位第一处差异;只调整最终数字会掩盖规则理解上的问题。改变输入后也要重新演算,而不是照抄这一例的输出。
