二维前缀和 pre[i][j] 表示从左上角 (1,1) 到右下角 (i,j) 的矩形内所有元素之和,递推式为:
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + a[i][j]。
其中「减去 pre[i-1][j-1]」这一步的作用是( )。
- A. 矩形 (1,1)-(i-1,j-1) 不包含在目标矩形内,必须扣除
- B. 矩形 (1,1)-(i-1,j-1) 在前两项中各被计入了一次,共被计入两次,需要减去一次
- C. 防止 i = 1 或 j = 1 时数组越界访问
- D. 因为 pre[i-1][j-1] 存放的是特殊值,不参与求和