跳至主要內容

307. 区域和检索 - 数组可修改


307. 区域和检索 - 数组可修改open in new window

🟠   🔖  设计 树状数组 线段树 数组  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an integer array nums, handle multiple queries of the following types:

  1. Update the value of an element in nums.
  2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right 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 to update and sumRange.

题目大意

给定一个整数数组 nums,请你完成两类查询:

  1. 更新 数组 nums 下标对应的值
  2. 返回数组 nums 中索引 leftright (包含 leftright)之间的 nums 元素的 ,其中 left <= right

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • void update(int index, int val)nums[index] 的值 更新val
  • int sumRange(int i, int j) 返回数组 nums 中索引 leftright 之间的元素的 总和 ,包含 leftright 两点(也就是 nums[left] + nums[left + 1] + ... + nums[right]

解题思路

这个问题可以通过线段树来解决:

  1. 初始化:NumArray 类的构造函数中,首先将输入的数组 nums 存储起来,并构建一个线段树,表示整个数组的和。每个线段树节点包含一个区间的起始位置、结束位置和该区间的和。

  2. 更新操作: 当调用 update 方法时,根据给定的索引和新的值,更新数组 nums 对应位置的值,并在线段树中更新对应的节点的值。这个更新过程是通过递归地向下更新线段树节点实现的。

  3. 区间和查询: 当调用 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区域和检索 - 数组不可变open in new window[✓]设计 数组 前缀和
308二维区域和检索 - 矩阵可修改 🔒open in new window设计 树状数组 线段树 2+
2381字母移位 IIopen in new window数组 字符串 前缀和