CJPD03｜棋盘矩形权值 题解

核心方法

二维前缀和

思路

定义 s[i][j] 为左上角 (1,1) 到 (i,j) 的矩形和。查询时用容斥：右下整块减去上方和左方，再加回重复减去的左上角。

复杂度

时间复杂度 $O(nm+q)$，空间复杂度 $O(nm)$。