【无标题】前缀和和差分

前缀和

一维前缀和

#include <vector>

class Code01_PrefixSumArray {
public:
    class NumArray {
    public:
        std::vector<int> sum;

        NumArray(std::vector<int>& nums) {
            sum.resize(nums.size() + 1);
            for (int i = 1; i <= nums.size(); i++) {
                sum[i] = sum[i - 1] + nums[i - 1];
            }
        }

        int sumRange(int left, int right) {
            return sum[right + 1] - sum[left];
        }
    };
};

一维差分

等差数列的差分

二维

二维前缀和

#include <vector>

class Code01_PrefixSumMatrix {
public:
    class NumMatrix {
    private:
        std::vector<std::vector<int>> sum;

    public:
        NumMatrix(std::vector<std::vector<int>>& matrix) {
            if (matrix.empty() || matrix[0].empty()) return;

            int n = matrix.size();
            int m = matrix[0].size();
            sum = std::vector<std::vector<int>>(n + 1, std::vector<int>(m + 1, 0));

            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    sum[i][j] = matrix[i-1][j-1];
                }
            }

            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    sum[i][j] += sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1];
                }
            }
        }

        int sumRegion(int a, int b, int c, int d) {
            return sum[c+1][d+1] - sum[c+1][b] - sum[a][d+1] + sum[a][b];
        }
    };
};