1
class NumArray {
2
    vector<int> s;
3
public:
4
    NumArray(vector<int>& nums) {
5
        s.resize(nums.size() + 1);
6
        for(int i = 0; i < nums.size(); i++){
7
            s[i + 1] = s[i] + nums[i];
8
        }
9
    }
10

11
    int sumRange(int left, int right) {
12
        return s[right + 1] - s[left];
13
    }
14
};

1
class Solution {
2
public:
3
    int subarraySum(vector<int>& nums, int k) {
4
        int n = nums.size();
5
        vector<int> s(n + 1);
6
        for (int i = 0; i < n; i++) {
7
            s[i + 1] = s[i] + nums[i];
8
        }
9

10
        unordered_map<int, int> cnt;
11
        int ans = 0;
12
        for (int sj : s) {
13
            // 注意不要直接 += cnt[sj-k]，如果 sj-k 不存在，会插入 sj-k
14
            ans += cnt.contains(sj - k) ? cnt[sj - k] : 0;
15
            cnt[sj]++;
16
        }
17
        return ans;
18
    }
19
};

1
class Solution {
2
public:
3
    vector<long long> minOperations(vector<int>& nums, vector<int>& queries) {
4
        ranges::sort(nums);
5
        int n = nums.size();
6

7
        vector<long long> s(n + 1);
8
        for(int i = 0; i < n; i++){
9
            s[i + 1] = s[i] + nums[i];
10
        }
11

12
        int m = queries.size();
13
        vector<long long> ans(m);
14
        for(int i = 0; i < m; i++){
15
            int q = queries[i];
16
            long long j = ranges::lower_bound(nums,q) - nums.begin();
17
            long long left = q * j - s[j];
18
            long long right = s[n] - s[j] - q * (n - j) ;
19
            ans[i] = left + right;
20
        }
21
        return ans;
22
    }
23
};

1
class NumMatrix {
2
    vector<vector<int>> sum;
3

4
public:
5
    NumMatrix(vector<vector<int>>& matrix) {
6
        int m = matrix.size(), n = matrix[0].size();
7
        sum.resize(m + 1, vector<int>(n + 1));
8
        for (int i = 0; i < m; i++) {
9
            for (int j = 0; j < n; j++) {
10
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
11
            }
12
        }
13
    }
14

15
    // 返回左上角在 (r1, c1)，右下角在 (r2, c2) 的子矩阵元素和
16
    int sumRegion(int r1, int c1, int r2, int c2) {
17
        return sum[r2 + 1][c2 + 1] - sum[r2 + 1][c1] - sum[r1][c2 + 1] + sum[r1][c1];
18
    }
19
};