我们知道,数组上的前缀和S[i]=S[i-1]+a[i]
那么,怎样求二维前缀和呢?
二维前缀和:
绿色点的前缀和就是黄色、红色、灰色和绿色的点权和
怎样计算?
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
绿色部分的前缀和=(红色+灰色)+(黄色+灰色)-灰色+绿色
有了前缀和,怎样计算某一部分的点权和呢?
类似的,现在绿色部分的总和=S(4,4)-S(4,2)-S(2,4)+S(2,2)
我们设绿色部分的边长为rx*ry,a为总和,绿色部分右下角坐标为i,j
a[i][j]=s[i][j]-s[i-rx-1][j]-s[i][j-1-ry]+s[i-1-rx][j-1-ry];