2D Subarray Sum

原始题目：LeetGPU - 2D Subarray Sum

题目描述

计算 $N \times M$ 二维 32 位整数数组的子矩形和。给定行范围 $[S_{ROW}, E_{ROW}]$ 和列范围 $[S_{COL}, E_{COL}]$（0-based，闭区间），求该子矩形内所有元素之和。

实现要求

• 不允许使用外部库。
• solve 函数签名必须保持不变。

示例

Input:  input = [[1,2,3],[4,5,6],[7,8,9]], S_ROW=0, E_ROW=1, S_COL=1, E_COL=2
Output: 2+3+5+6 = 16

约束条件

• $1 \le N, M \le 10{,}000$，$0 \le S\_ROW \le E\_ROW < N$，$0 \le S\_COL \le E\_COL < M$。

解题思路

与一维子数组类似，可使用二维前缀和 $prefix[i][j] = \sum_{r<i, c<j} input[r][c]$，子矩形和为 $prefix[E_R+1][E_C+1] - prefix[S_R][E_C+1] - prefix[E_R+1][S_C] + prefix[S_R][S_C]$。或直接对子矩形做并行规约。欢迎在 GitHub Discussions 分享你的解法。