307. 区域和检索 - 数组可修改
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
说明:
- 1.数组仅可以在 update 函数下进行修改。
- 2.你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
该题解法类似于 LeetCode 303. 区域和检索 - 数组不可变 - 简书
-
1. 暴力破解法
思路：遍历数组累加
- 在进行求和是遍历整个数组，找出我们所需区间 [i, j]的所有元素
- 将其累加即可
private int[] data;
public NumArray(int[] nums) {
data = nums;
}
public int sumRange(int i, int j) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += data[k];
}
return sum;
}
public void update(int i, int val) {
data[i] = val;
}
复杂度分析：
-
时间复杂度：O(n), 每次调用 sumRange()的复杂度都是 O(n)
-
空间复杂度：O(1), data 只是 nums 的一个引用
-
2. 预处理法(但由于数组可变，该解法超时)
思路：将每个索引之前所有元素之后放入一个数组中
- 事先现将 nums 中前 i 个元素存储进数组 sum 中, 其中 sum[0] = 0，所以我们需要多开辟一个空间
- 在计算区间 [i, j]的和，使用 j（包括j）之前所有的元素之和 减去 i（不包括i）之前的元素和即可
private int[] sum; // sum[i]存储前 i 个元素的和，sum[0] = 0
private int[] data;
public NumArray(int[] nums) {
data = nums;
sum = new int[nums.length + 1];
sum[0] = 0;
for (int i = 1; i < sum.length; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
}
}
public int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
public void update(int i, int val) {
data[i] = val;
for (int k = i + 1; k < sum.length; k++) {
sum[k] = sum[k - 1] + data[k - 1];
}
}
复杂度分析：
-
时间复杂度：O(n), n 为数组 nums 的长度, 每次 update() 都是 O(n) 的复杂度
-
空间复杂度：O(n)，新开辟的数组 sum
-
3. 线段树法(最优解法)
思路：递归思想构建线段树
- 构建线段树
- 相加操作时，如果区间的右边界没有超过中间索引(mid)时，则我们要查询的一定在左子树，如果区间的左边界超过中间索引，则要查询的一定在右子树，如果即在左子树，又在右子树，我们都需要处理，然后将每个部分求和即可
- 更新操作同理
线段树
private int[] data;
private int[] tree; //线段树
public NumArray(int[] nums) {
data = nums;
tree = new int[data .length * 4];
buildSegmentTree(0, 0, data.length - 1);
}
/**
* 构建线段树
* @param treeIndex
* @param l
* @param r
*/
private void buildSegmentTree(int treeIndex, int l, int r) {
if (l == r) {
tree[treeIndex] = data[l];
return;
}
int mid = l + (r - l) / 2;
int lefeTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
buildSegmentTree(lefeTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid + 1, r);
tree[treeIndex] = tree[lefeTreeIndex] + tree[rightTreeIndex];
}
/**
* 查询线段树中区间[queryL, queryR]的值
* @param queryL
* @param queryR
* @return
*/
public int sumRange(int queryL, int queryR) {
if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
throw new IllegalArgumentException("Index is Illegal");
}
return sumRange(0, 0, data.length - 1, queryL, queryR);
}
/**
*
* @param treeIndex 根节点
* @param l 左边界
* @param r 右边界
* @param queryL 查询的左区间
* @param queryR 查询的右区间
* @return
*/
private int sumRange(int treeIndex, int l, int r, int queryL, int queryR) {
if (l == queryL && r == queryR) {
return tree[treeIndex];
}
int mid = l + (r - l) / 2;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (queryL >= mid + 1) {
//查询区间在右子树
return sumRange(rightTreeIndex, mid + 1, r, queryL, queryR);
} else if (queryR <= mid) {
//查询区间在左子树
return sumRange(leftTreeIndex, l, mid, queryL, queryR);
}
int leftResult = sumRange3(leftTreeIndex, l, mid, queryL, mid);
int rightResult = sumRange3(rightTreeIndex, mid + 1, r, mid + 1, queryR);
return leftResult + rightResult;
}
/**
* 在以treeIndex为根的线段树中更新index的值为e
* @param index
* @param e
*/
public void update(int i, int e) {
if (index < 0 || index >= data.length) throw new IllegalArgumentException("Index is Illegal");
data[index] = e;
update(0, 0, data.length - 1, index, e);
}
/**
* 更新
* @param treeIndex 根节点索引
* @param l 左边界
* @param r 右边界
* @param index 更新的索引
* @param e 要更新的值
*/
private void update(int treeIndex, int l, int r, int index, int e) {
if (l == r) {
tree[treeIndex] = e;
return;
}
int mid = l + (r - l) / 2;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (index >= mid + 1) {
//在右子树
update(rightTreeIndex, mid + 1, r, index, e);
} else {
//左子树
update(leftTreeIndex, l, mid, index, e);
}
tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex];
}
/**
* 返回完全二叉树数组表示中，左孩子节点的索引
* @param index
* @return
*/
private int leftChild(int index) {
return 2 * index + 1;
}
/**
* 返回完全二叉树数组表示中，右孩子节点的索引
* @param index
* @return
*/
private int rightChild(int index) {
return 2 * index + 2;
}
复杂度分析：
- 时间复杂度：O(logn), 查询和更新均为 O(logn) 的时间复杂度
- 空间复杂度：O(4n), 最坏情况下，需要 4n 的空间，
最好情况下（n = 2 ^ k），需要 2n 空间
-
测试用例
public static void main(String[] args) {
int[] nums = {1, 3, 5};
NumArray2 numArray2 = new NumArray2(nums);
System.out.println(Arrays.toString(nums));
System.out.println("sumRange(0, 2) ->:" + numArray2.sumRange(0, 2));
numArray2.update(1, 2);
System.out.println("sumRange(0, 2) ->" + numArray2.sumRange(0, 2));
}
-
结果
[1, 3, 5]
sumRange(0, 2) ->:9
sumRange(0, 2) ->8
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
网友评论