查看某块地图中资源数量时,可以逐格相加,也可以先建立累计表,再用几次加减得到矩形总量。理解重复计算的重叠区域,有助于排查框选统计多算或少算一行的问题。
下面使用独立的一组输入,逐步记录规则如何产生结果。建议先自行推演,再寻找与记录第一次不同的位置;检查时间单位、端点归属和处理顺序。所有约定均限定在本例中,其他作品采用不同实现并不自动意味着出错。
本例约定与输入
格子数值是非负整数,累计表额外带一行一列零边界;查询矩形采用左上包含、右下排除的坐标范围。用右下累计减去上方和左方,再加回两者的重叠。
地图6列5行,数值如下 [1, 4, 0, 1, 4, 6] [6, 3, 8, 0, 0, 5] [1, 0, 2, 2, 0, 7] [7, 0, 5, 8, 9, 8] [7, 7, 6, 2, 7, 4] 查询[x1,y1,x2,y2]:[[0, 0, 6, 5], [0, 0, 1, 1], [5, 4, 6, 5], [4, 4, 6, 5], [0, 2, 5, 5], [2, 2, 5, 4], [1, 0, 3, 5], [0, 3, 6, 4], [4, 4, 5, 5], [2, 1, 4, 2]]
过程与结果
原图第0行[1, 4, 0, 1, 4, 6],累计表对应第1行[0, 1, 5, 5, 6, 10, 16];左侧零边界保留。
原图第1行[6, 3, 8, 0, 0, 5],累计表对应第2行[0, 7, 14, 22, 23, 27, 38];左侧零边界保留。
原图第2行[1, 0, 2, 2, 0, 7],累计表对应第3行[0, 8, 15, 25, 28, 32, 50];左侧零边界保留。
原图第3行[7, 0, 5, 8, 9, 8],累计表对应第4行[0, 15, 22, 37, 48, 61, 87];左侧零边界保留。
原图第4行[7, 7, 6, 2, 7, 4],累计表对应第5行[0, 22, 36, 57, 70, 90, 120];左侧零边界保留。
矩形[0,6)×[0,5):120-0-0+0=120,范围内有30格。
矩形[0,1)×[0,1):1-0-0+0=1,范围内有1格。
矩形[5,6)×[4,5):120-87-90+61=4,范围内有1格。
矩形[4,6)×[4,5):120-87-70+48=11,范围内有2格。
矩形[0,5)×[2,5):90-27-0+0=63,范围内有15格。
矩形[2,5)×[2,4):61-27-22+14=26,范围内有6格。
矩形[1,3)×[0,5):57-0-22+0=35,范围内有10格。
矩形[0,6)×[3,4):87-50-0+0=37,范围内有6格。
矩形[4,5)×[4,5):90-61-70+48=7,范围内有1格。
矩形[2,4)×[1,2):23-6-14+5=8,范围内有2格。
十次统计结果为[120, 1, 4, 11, 63, 26, 35, 37, 7, 8];第一次整图总量120。
如何独立复核
对每个查询直接枚举矩形内的原始格子求和,与累计表四项计算比较。单格、整图和靠边矩形尤其适合检查坐标约定,不要把排除式右下角当作最后一个格子的坐标。
累计表适合原图暂时不变时反复查询。原始格子发生变化以后,旧表就不再对应新数据;本例不讨论动态更新结构,也不能因为查询公式正确就忽略表的生成时机。
测试时保留原始数据与中间状态,再只改变一个条件作比较。先检查空状态、相等边界、重复输入和最后一步,再比较整体结果;不要为了让最后的数字相同而跳过前面已经出现的差异。明确规则后,复核才有可以重复的依据。