二维前缀和

其实就是两步第一步计算f(i,j)到起始点默认为(1,1)前缀和公式f(i,j)f(i-1,j)f(i,j-1)-f(i-1,j-1)a[i,j];可以用图像来表示会更清楚此时所有格子都是白色的此时是11到ij-1此时是又加上了11到i-1j发现重复的是11到i-1j-1这块然后我们减去即可此时就只需要加上最后的点a[i,j]即可所以计算公式就是f(i,j)f(i-1,j)f(i,j-1)-f(i-1,j-1)a[i,j];第二步调用计算出任意两点间围成矩形的值从x1,y1到x2,y2ansf(x2​,y2​)−f(x2​,y1​−1)−f(x1​−1,y2​)f(x1​−1,y1​−1)