307. 区域和检索 - 数组可修改
307. 区域和检索 - 数组可修改
🟠 🔖 设计
树状数组
线段树
数组
🔗 力扣
LeetCode
题目
Given an integer array nums
, handle multiple queries of the following types:
- Update the value of an element in
nums
. - Calculate the sum of the elements of
nums
between indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.void update(int index, int val)
Updates the value ofnums[index]
to beval
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
inclusive (i.e.nums[left] + nums[left + 1] + ... + nums[right]
).
Example 1:
Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]
Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8
Constraints:
1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
- At most
3 * 10^4
calls will be made toupdate
andsumRange
.
题目大意
给定一个整数数组 nums
,请你完成两类查询:
- 更新 数组
nums
下标对应的值 - 返回数组
nums
中索引left
和right
(包含left
和right
)之间的nums
元素的 和 ,其中left <= right
实现 NumArray
类:
NumArray(int[] nums)
使用数组nums
初始化对象void update(int index, int val)
将nums[index]
的值 更新 为val
int sumRange(int i, int j)
返回数组nums
中索引left
和right
之间的元素的 总和 ,包含left
和right
两点(也就是nums[left] + nums[left + 1] + ... + nums[right]
)
解题思路
这个问题可以通过线段树来解决:
初始化: 在
NumArray
类的构造函数中,首先将输入的数组nums
存储起来,并构建一个线段树,表示整个数组的和。每个线段树节点包含一个区间的起始位置、结束位置和该区间的和。更新操作: 当调用
update
方法时,根据给定的索引和新的值,更新数组nums
对应位置的值,并在线段树中更新对应的节点的值。这个更新过程是通过递归地向下更新线段树节点实现的。区间和查询: 当调用
sumRange
方法时,需要查询数组中指定区间[i, j]
的和。在线段树中,可以通过递归地查询左右子树来获得区间[i, j]
的和:- 如果当前节点的区间完全包含在
[i, j]
中,则直接返回该节点的和。 - 否则,根据当前节点的中点将查询区间
[i, j]
分为左右两部分,递归地查询左右子树,并将两部分的和相加。
- 如果当前节点的区间完全包含在
代码
class NumArray {
// @param {number[]} nums
constructor(nums) {
this.nums = nums;
this.segmentTree = this.buildSegmentTree(nums, 0, nums.length - 1);
}
// @param {number[]} nums
// @param {number} start
// @param {number} end
buildSegmentTree(nums, start, end) {
if (start == end) {
return { start, end, left: null, right: null, sum: nums[start] };
}
const mid = Math.floor((start + end) / 2);
const left = this.buildSegmentTree(nums, start, mid);
const right = this.buildSegmentTree(nums, mid + 1, end);
const sum = left.sum + right.sum;
return { start, end, left, right, sum };
}
// @param {number} index
// @param {number} val
// @return {void}
update(index, val) {
this.updateSegmentTree(this.segmentTree, index, val);
}
updateSegmentTree(root, index, val) {
if (root.start == root.end) {
root.sum = val;
return;
}
const mid = Math.floor((root.start + root.end) / 2);
if (index <= mid) {
this.updateSegmentTree(root.left, index, val);
} else {
this.updateSegmentTree(root.right, index, val);
}
root.sum =
(root.left ? root.left.sum : 0) + (root.right ? root.right.sum : 0);
}
// @param {number} left
// @param {number} right
// @return {number}
sumRange(left, right) {
return this.querySegmentTree(this.segmentTree, left, right);
}
querySegmentTree(root, start, end) {
if (root.start > end || root.end < start) return 0;
if (root.start >= start && root.end <= end) return root.sum;
const mid = Math.floor((root.start + root.end) / 2);
const leftSum = this.querySegmentTree(root.left, start, Math.min(mid, end));
const rightSum = this.querySegmentTree(
root.right,
Math.max(mid + 1, start),
end
);
return leftSum + rightSum;
}
}
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
303 | 区域和检索 - 数组不可变 | [✓] | 设计 数组 前缀和 | |
308 | 二维区域和检索 - 矩阵可修改 🔒 | 设计 树状数组 线段树 2+ | ||
2381 | 字母移位 II | 数组 字符串 前缀和 |