303. 区域和检索 - 数组不可变 Range Sum Query Immutable
给定一个整数数组 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：
输入：
["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))
提示：
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^50 <= i <= j < nums.length- 最多调用
10^4次sumRange方法
代码：
package main import "fmt" type NumArray struct { prefixSum []int } func Constructor(nums []int) NumArray { n := len(nums) prefixSum := make([]int, n+1) for i := 0; i < n; i++ { prefixSum[i+1] = prefixSum[i] + nums[i] } return NumArray{prefixSum} } func (this *NumArray) SumRange(left int, right int) int { // 返回区间和 return this.prefixSum[right+1] - this.prefixSum[left] } func main() { nums := []int{-2, 0, 3, -5, 2, -1} obj := Constructor(nums) fmt.Println(obj.SumRange(0, 2)) fmt.Println(obj.SumRange(2, 5)) fmt.Println(obj.SumRange(0, 5)) }
输出：
1
-1
-3
304. 二维区域和检索 - 矩阵不可变 Range Sum Query 2d Immutable
给定一个二维矩阵 matrix，以下类型的多个请求：
- 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为
(row1, col1)，右下角 为(row2, col2)。
实现 NumMatrix 类：
NumMatrix(int[][] matrix)给定整数矩阵matrix进行初始化int sumRegion(int row1, int col1, int row2, int col2)返回 左上角(row1, col1)、右下角(row2, col2)所描述的子矩阵的元素 总和 。
示例 1：
输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
[null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^5 <= matrix[i][j] <= 10^50 <= row1 <= row2 < m0 <= col1 <= col2 < n- 最多调用
10^4次sumRegion方法
代码：
package main import "fmt" type NumMatrix struct { prefixSum [][]int } func Constructor(matrix [][]int) NumMatrix { m, n := len(matrix), len(matrix[0]) prefixSum := make([][]int, m+1) for i := range prefixSum { prefixSum[i] = make([]int, n+1) } for i := 1; i <= m; i++ { for j := 1; j <= n; j++ { prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i][j-1] + prefixSum[i-1][j] - prefixSum[i-1][j-1] } } return NumMatrix{prefixSum} } func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int { return this.prefixSum[row2+1][col2+1] - this.prefixSum[row2+1][col1] - this.prefixSum[row1][col2+1] + this.prefixSum[row1][col1] } func main() { numMatrix := [][]int{ {3, 0, 1, 4, 2}, {5, 6, 3, 2, 1}, {1, 2, 0, 1, 5}, {4, 1, 0, 1, 7}, {1, 0, 3, 0, 5}} obj := Constructor(numMatrix) fmt.Println(obj.SumRegion(2, 1, 4, 3)) fmt.Println(obj.SumRegion(1, 1, 2, 2)) fmt.Println(obj.SumRegion(1, 2, 2, 4)) }
输出：
8
11
12
307. 区域和检索 - 数组可修改 Range Sum Query Mutable
给你一个数组 nums ，请你完成两类查询。
- 其中一类查询要求 更新 数组
nums下标对应的值 - 另一类查询要求返回数组
nums中索引left和索引right之间（ 包含 ）的nums元素的 和 ，其中left <= right
实现 NumArray 类：
NumArray(int[] nums)用整数数组nums初始化对象void update(int index, int val)将nums[index]的值 更新 为valint sumRange(int left, int right)返回数组nums中索引left和索引right之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）
示例 1：
输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]
解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
提示：
1 <= nums.length <= 3 * 10^4-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length- 调用
update和sumRange方法次数不大于3 * 10^4
代码：
package main import "fmt" type NumArray struct { tree []int n int } func Constructor(nums []int) NumArray { n := len(nums) tree := make([]int, n*4) if n > 0 { buildTree(tree, nums, 1, 0, n-1) } return NumArray{tree, n} } func buildTree(tree []int, nums []int, node, start, end int) { if start == end { tree[node] = nums[start] return } mid := start + (end-start)/2 leftNode, rightNode := node*2, node*2+1 buildTree(tree, nums, leftNode, start, mid) buildTree(tree, nums, rightNode, mid+1, end) tree[node] = tree[leftNode] + tree[rightNode] } func (this *NumArray) Update(index int, val int) { updateTree(this.tree, 1, 0, this.n-1, index, val) } func updateTree(tree []int, node, start, end, index, val int) { if start == end { tree[node] = val return } mid := start + (end-start)/2 leftNode, rightNode := node*2, node*2+1 if index <= mid { updateTree(tree, leftNode, start, mid, index, val) } else { updateTree(tree, rightNode, mid+1, end, index, val) } tree[node] = tree[leftNode] + tree[rightNode] } func (this *NumArray) SumRange(left int, right int) int { return queryTree(this.tree, 1, 0, this.n-1, left, right) } func queryTree(tree []int, node, start, end, left, right int) int { if start > right || end < left { return 0 } if start >= left && end <= right { return tree[node] } mid := start + (end-start)/2 leftSum := queryTree(tree, node*2, start, mid, left, right) rightSum := queryTree(tree, node*2+1, mid+1, end, left, right) return leftSum + rightSum } func main() { numArray := []int{1, 3, 5} obj := Constructor(numArray) fmt.Println(obj.SumRange(0, 2)) obj.Update(1, 2) fmt.Println(obj.SumRange(0, 2)) }
输出：
9
8
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
