脚撕LeetCode(307)Medium
题目地址：https://leetcode-cn.com/problems/range-sum-query-mutable/
给你一个数组 nums ，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。 实现 NumArray 类： NumArray(int[] nums) 用整数数组 nums 初始化对象 void update(int index, int val) 将 nums[index] 的值更新为 val int sumRange(int left, int right) 返回子数组 nums[left, right] 的总和（即，nums[left] + nums[left + 1], ..., nums[right]） https://leetcode-cn.com/problems/range-sum-query-mutable/
示例： 输入： ["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); // 返回 9 ，sum([1,3,5]) = 9 numArray.update(1, 2); // nums = [1,2,5] numArray.sumRange(0, 2); // 返回 8 ，sum([1,2,5]) = 9 https://leetcode-cn.com/problems/range-sum-query-mutable/
提示： 1 <= nums.length <= 3 * 104 -100 <= nums[i] <= 100 0 <= index < nums.length -100 <= val <= 100 0 <= left <= right < nums.length 最多调用 3 * 104 次 update 和 sumRange 方法 https://leetcode-cn.com/problems/range-sum-query-mutable/
一、暴力破解
爆破法，用拿到题第一想法，最直观的解决问题，时间复杂度：O(n)。区域和检索 O(1) 的更新查询；
执行结果：超时
class NumArray {
private int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public void update(int index, int val) {
nums[index] = val;
}
public int sumRange(int left, int right) {
int sum = 0;
for(int i = left; i <= right; i++) {
sum = sum + nums[i];
}
return sum;
}
}二、sqrt分解法
将数组分块，数据分为sqrt n 组，每组sqrt n个值
新建一个数组，将每一块的sum结果存在这个新的数组里面
时间复杂度：O(n)O(n) 预处理，O(sqrt n) 区域和检索，O(1)更新查询
空间复杂度：O(sqrt n)，我们需要额外的 sqrt n内存来存储所有块和。
执行结果：
15 / 15 个通过测试用例
状态：通过
执行用时: 121 ms
内存消耗: 69 MB
class NumArray {
private int[] nums;
private int[] b;
private int len;
public NumArray(int[] nums) {
this.nums = nums;
double l = Math.sqrt(nums.length);
len = (int) Math.ceil(nums.length / l);
b = new int[len];
for (int i = 0; i < nums.length; i++) {
b[i / len] += nums[i];
}
}
public void update(int index, int val) {
int b_l = index / len;
b[b_l] = b[b_l] - nums[index] + val;
nums[index] = val;
}
public int sumRange(int i, int j) {
int sum = 0;
int startBlock = i / len;
int endBlock = j / len;
if (startBlock == endBlock) {
for (int k = i; k <= j; k++) {
sum += nums[k];
}
} else {
for (int k = i; k <= (startBlock + 1) * len - 1; k++) {
sum += nums[k];
}
for (int k = startBlock + 1; k <= endBlock - 1; k++) {
sum += b[k];
}
for (int k = endBlock * len; k <= j; k++) {
sum += nums[k];
}
}
return sum;
}
}三、线段树
叶子节存放基本数据，父节点存放子节点得和，根节点存放所有得和。
构建树：时间复杂度：O(n)。空间复杂度：O(n)
update树：时间复杂度：O(logn)，空间复杂度：O(1)
query树：时间复杂度：O(logn)，空间复杂度：O(1)
执行结果：
15 / 15 个通过测试用例
状态：通过
执行用时: 109 ms
内存消耗: 68.6 MB
这里官方提供了一个139ms的方法，是每次update的时候需要根据子节点重新计算父节点的值，而我这里是直接将需要更新的值计算好直接update，没有好坏只有更适宜的场景，官方的解法我就不贴了。
class NumArray {
private int[] nums;
int[] tree;
int len;
public NumArray(int[] nums) {
len = nums.length;
tree = new int[2 * len];
System.arraycopy(nums, 0, tree, len, len);
for (int i = len - 1; i > +0; i--) {
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
}
public void update(int index, int val) {
int item = len + index;
// 需要增加或者删除得数字
int temp = val - tree[item];
while (item > 0) {
tree[item] += temp;
item /= 2;
}
}
public int sumRange(int left, int right) {
left += len;
right += len;
int sum = 0;
while (left <= right) {
if (left % 2 == 1) {
sum += tree[left];
left++;
}
if (right % 2 == 0) {
sum += tree[right];
right--;
}
left /= 2;
right /= 2;
}
return sum;
}
}爆破法就不讲了，后面的sqrt和线段树思路：
一、sqrt法
sqrt法的主要思路是将数据划分成等分块，然后等分块内的总和记录在另一个数组内，下次计算使用的时候直接从数组中取到整个的等分块部分的总和，然后再计算不是整个等分块的数据的和。
这种做法虽然好，但如果left和right指针刚好是等分块的第二位数和倒数第二位，那么其实还是需要计算的次数相对较多。
二、线段树法
线段树法的主要思路是将数据放在一个二叉树（用数组就可以描述）内，父节点存放的是直接子节点的和，根节点存放的是所有的和。
当我们需要查询的节点不是整个父节点时，就单独计算该节点，否则就计算父节点的值的和，当需要查询的节点是其父节点的所有子节点时，不单独计算子节点，而是直接计算父节点。
听起来挺拗口
其实就是，自底向上的计算方式，相近办法上升减少计算次数，如果无法上升（也就是需要计算的节点不是该节点的父节点的所有子节点，那么就单独计算该节点，否则上升）
总的来说，线段树的做法我是没想到的，果然还是数据结构太辣鸡了hhhhh，路还很漫长，我还菜的很
以上就是leetcode.307.区域和检索(Medium)的全部内容
腾讯云开发者
