1
2
3
4
5
6
7
8

// 构建前缀和数组（长度 n+1，prefix[0] = 0）
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}

// 查询 [l, r] 的区间和（闭区间）
int rangeSum = prefix[r + 1] - prefix[l];

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 构建二维前缀和
vector<vector<int>> prefix(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1]
                     - prefix[i-1][j-1] + matrix[i-1][j-1];
    }
}

// 查询 (r1,c1) 到 (r2,c2) 的子矩阵和
int sum = prefix[r2+1][c2+1] - prefix[r1][c2+1]
        - prefix[r2+1][c1] + prefix[r1][c1];

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 核心：prefix[j] - prefix[i] = k  →  prefix[i] = prefix[j] - k
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    cnt[0] = 1;  // 空前缀
    int pre = 0, ans = 0;
    for (int x : nums) {
        pre += x;
        if (cnt.count(pre - k)) ans += cnt[pre - k];
        cnt[pre]++;
    }
    return ans;
}

1
2
3
4

// 区间增减：对 [l, r] 所有元素 +val
diff[l] += val;
diff[r + 1] -= val;
// 最后做前缀和还原