二维前缀和

const int N= 1e3+5;
using ll = long long;

ll a[N][N] = {0};
ll pref[N][N] = {0};

// 输入 && 构建
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        cin >> a[i][j];
        pref[i][j] = a[i][j] + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
    }
}

// 查询子矩阵 (x1,y1) 到 (x2,y2) 的和
int sum = pref[x2][y2] - pref[x1-1][y2] - pref[x2][y1-1] + pref[x1-1][y1-1];