std::vector<int> dpsum(const vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n + 1, 0); // dp 數(shù)組的長度是 n+1，并初始化為 0
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + arr[i - 1];
    }
    return dp;
}

int queryRangeSum(const vector<int>& dp, int l, int r) {
    return dp[r] - dp[l - 1];
}

#include <iostream>
#include <vector>
using namespace std;
// 預處理前綴和數(shù)組的函數(shù)
vector<int> dpSum(const vector<int>& arr) {
    int n = arr.size();
    std::vector<int> dp(n + 1, 0); // dp 數(shù)組的長度是 n+1，并初始化為 0
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + arr[i - 1];
    }
    return dp;
}
// 查詢區(qū)間和的函數(shù)
int queryRangeSum(const vector<int>& dp, int l, int r) {
    return dp[r] - dp[l - 1];
}
int main() {
    // 示例數(shù)組
    vector<int> arr = {1, 2, 3, 4, 5};
    // 預處理前綴和數(shù)組
    vector<int> dp = dpSum(arr);
    // 查詢區(qū)間 [2, 4] 的和（注意C++中數(shù)組索引從0開始，但這里的l,r是區(qū)間表示，從1開始考慮）
    int sum = queryRangeSum(dp, 2, 4);
    cout << "Sum of range [2, 4]: " << sum << endl; // 輸出 9 (2+3+4)
    return 0;
}

for(int i = 1; i <= n; i++) 
 for(int j = 1; j <= m; j++)
 cin >> arr[i][j];

 // 處理前綴和矩陣
 for(int i = 1; i <= n; i++)
 for(int j = 1; j <= m; j++)
 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 
1];

#include <iostream>
using namespace std;
const int N = 1010;
int arr[N][N];
long long dp[N][N];
int n, m, q;
int main() 
{
 cin >> n >> m >> q;
 // 讀?數(shù)據(jù)
 for(int i = 1; i <= n; i++) 
 for(int j = 1; j <= m; j++)
 cin >> arr[i][j];
 // 處理前綴和矩陣
 for(int i = 1; i <= n; i++)
 for(int j = 1; j <= m; j++)
 dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 
1];
 // 使?前綴和矩陣
 int x1, y1, x2, y2;
 while(q--)
 {
 cin >> x1 >> y1 >> x2 >> y2;
 cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 
1] << endl;
 }
}

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m=mat.size(),n=mat[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];
            }
        }
         vector<vector<int>> arr(m,vector<int>(n));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                int x1=max(i-k,0)+1;
                int y1=max(j-k,0)+1;
                int x2=min(i+k,m-1)+1;
                int y2=min(j+k,n-1)+1;
               arr[i][j]=dp[x1-1][y1-1]+dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]; 
            }
        }
        return arr;
    }
};

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int numSubarraySumEqualK(vector<int>& nums, int k) {
    unordered_map<int, int> count; // 哈希表，記錄前綴和出現(xiàn)的頻率
    count[0] = 1; // 初始化前綴和為0的頻率為1（表示空子數(shù)組）
    int prefixSum = 0; // 當前位置的前綴和
    int result = 0; // 和為k的子數(shù)組個數(shù)
    for (int num : nums) {
        prefixSum += num; // 計算當前位置的前綴和
        int target = prefixSum - k; // 計算目標前綴和
        if (count.find(target) != count.end()) {
            // 如果目標前綴和在哈希表中出現(xiàn)過，則增加結果
            result += count[target];
        }
        // 更新哈希表中當前前綴和的頻率
        count[prefixSum]++;
    }
    return result;
}
int main() {
    vector<int> nums = {1, 1, 1}; // 示例數(shù)組
    int k = 2; // 目標和
    int result = numSubarraySumEqualK(nums, k);
    cout << "和為" << k << "的子數(shù)組個數(shù)為: " << result << endl;
    return 0;
}