dim2_partial_sum.cpp

vector<vector<int>> Dim2PartialSum(vector<vector<int>> &mat, int w, int h) {
  vector<vector<int>> psum(h + 1, vector<int>(w + 1, 0));
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      psum[i + 1][j + 1] =
          psum[i + 1][j] + psum[i][j + 1] + mat[i][j] - psum[i][j];
    }
  }

  return psum;
}

int Dim2PartialSumArea(vector<vector<int>> &psum, int x, int y, int w, int h) {
  return psum[y + h][x + w] - psum[y + h][x] - psum[y][x + w] + psum[y][x];
}