动规,sum[i][j]表示从(0, 0)到(i, j)所有元素的和,开辟辅助空间的情况下O(n^2)可以完成转移,比如sumr[i][j]表示对于某一行i,从第0列到第j列所有元素的和;查询O(1),容斥一下就可以了。下面的程序在空间上其实还可以优化,可优化的地方在程序中做出了注释,很简单,就不做修改了。