差分数组

一、区间和检索（数组不可变）

1、先求数组的前缀和presum；

2、再求区间presum[right - 1] - presume[left]的值

LC303. 区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象

int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：
1
2
3
4
5
6
7
8
9
10
11
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

vector<int> presum;
NumArray(vector<int>& nums) {
    int n = nums.size();
    presum.resize(n+1);
  // 1、求前缀和
    for(int i = 0; i < n; i++) {
        presum[i+1] = presum[i] + nums[i];
    }
}

// 2、求区间【left-right】的和
int sumRange(int left, int right) {
    return presum[right+1]-presum[left];
}

二维前缀和模板：

1	presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + matrix[i - 1][j - 1];

求某段区间和[i,j]的模板：

1	presum[x2][y2] - presum[x1 - 1][y2] - presum[x2][y1 - 1] + presum[x1 - 1][y1 - 1];

LC304. 二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化

int sumRegion(int x1, int y1, int x2, int y2) 返回 左上角 (x1, y1) 、右下角 (x2, y2) 所描述的子矩阵的元素总和。

class NumMatrix {
public:
    vector<vector<int>>presum;
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        presum = vector(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                // 二维前缀和模板
                presum[i + 1][j + 1] = presum[i + 1][j] + presum[i][j + 1] - presum[i][j] + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int x1, int y1, int x2, int y2) {
        // 求某段区间[i,j]和的模板  
        return presum[x2 + 1][y2 + 1] - presum[x1][y2 + 1] - presum[x2 + 1][y1] + presum[x1][y1]; 
    }
};

二、区间和检索（数组可变）

差分数组通常用于区间修改的操作，例如对数组[4,1,3,5,2,7] 下标[1 ~ 3]的元素+5，[3 ~ 4]的元素 -6，得到[4,6,8,-4-4,7]

1、求差分数组

diff[0] = nums[0];
for(int i = 1; i < ; i++) {
	diff[i] = nums[i] - nums[i - 1]; // 4,-3,2,2,-3,5
}

2、根据修改的内容，修改差分数组

对范围[a-b]的数字 +k (关键)

// 做t次修改
while(t--) {
  diff[a] = diff[a] + k;
	diff[b + 1] = diff[b + 1] - k; 
} 
// 4,2,2,-4,-8,11

3、求差分数组的前缀和

1
2
3

for(int i = 1; i < n; i++) {
		diff[i] += diff[i - 1]; .. 
} // 4,6,8,4,-4,7

4、求得原数组

1
2
3

for(int i = 1; i < n; i++) {
		nums[i] = diff[i] + nums[i - 1]; // 4,6,8,-4-4,7
}

LC周赛 6292. 子矩阵元素加 1

给你一个正整数 n ，表示最初有一个 n x n 、下标从 0 开始的整数矩阵 mat ，矩阵中填满了 0 。

另给你一个二维整数数组 query 。针对每个查询 query[i] = [row1i, col1i, row2i, col2i] ，请你执行下述操作：

找出 左上角 为 (row1i, col1i) 且 右下角 为 (row2i, col2i) 的子矩阵，将子矩阵中的 每个元素 加 1 。也就是给所有满足 row1i <= x <= row2i 和 col1i <= y <= col2i 的 mat[x][y] 加 1 。

返回执行完所有操作后得到的矩阵 mat 。

vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
    vector<vector<int>>grid(n, vector<int>(n, 0));
    vector<vector<int>>diff(n + 1, vector<int>(n + 1, 0)); //  差分数组
    // 1、 先求差分数组
    for(int i = 0; i < queries.size(); i++) {
            int row1 = queries[i][0];
            int col1 = queries[i][1];
            int row2 = queries[i][2];
            int col2 = queries[i][3];
        for(int k = row1; k <= row2; k++) {
            diff[k][col1] += 1;
            diff[k][col2 + 1] -= 1;
        }
    }
    // 2、求差分数组的前缀和，即更改后数组
    for(int i = 0; i < n; i++) {
        int sum = 0;
        for(int j = 0; j < n; j++) {
            sum += diff[i][j];
            grid[i][j] = sum;
        }
    }
    return grid;
}

一、区间和检索（数组不可变）

LC303. 区域和检索 - 数组不可变

二、区间和检索（数组可变）

FEATURED TAGS

FRIENDS