目录
303. 区域和检索 - 数组不可变 Range Sum Query Immutable 🌟
304. 二维区域和检索 - 矩阵不可变 Range Sum Query 2d Immutable 🌟🌟
307. 区域和检索 - 数组可修改 Range Sum Query Mutable 🌟🌟
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/