基于二维前缀和的子矩阵求和结构，给定左上与右下（半开区间）坐标后可在 O(1) 时间返回任意子矩阵之和，预处理 O(N^2)。
Description: Calculate submatrix sums quickly, given upper-left and lower-right corners (half-open). Usage: SubMatrix
m(matrix); m.sum(0, 0, 2, 2); // top left 4 elements Time: O(N^2 + Q)
-
定义与接口（依据实现）
- 模板结构体 SubMatrix
持有二维前缀和数组 p（尺寸为 (R+1)×(C+1)）。 - 构造：给定原矩阵 v（R×C），按 p[r+1][c+1] = v[r][c] + p[r][c+1] + p[r+1][c] - p[r][c] 预处理。
- 查询：sum(u, l, d, r) 返回半开区间 [u,d)×[l,r) 的子矩阵和，计算式为 p[d][r] - p[d][l] - p[u][r] + p[u][l]。
- 模板结构体 SubMatrix
-
关键要点
- 坐标语义为“行列均半开”：上界 d、r 不包含在内；示例 m.sum(0,0,2,2) 覆盖 2×2 的左上子块。
- p 的行列各向右/向下偏移一位，便于常数时间处理边界。
- 适用于静态矩阵的多次求和查询；若需要动态修改可考虑二维树状数组或线段树。
-
复杂度
- 预处理 O(RC)；单次查询 O(1)；空间 O(RC)。
-
使用提示
- 输入矩阵须为规则二维容器且非空（实现中假设 v[0] 有效）。
- 注意整数溢出风险：根据数据范围选择合适的 T（如 long long）。