题目描述
这是 LeetCode 上的 307. 区域和检索 - 数组可修改 ,难度为 中等。
Tag : 「区间和」、「树状数组」
给你一个数组 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])
示例:
输入: ["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]) = 8 复制代码
提示:
- 1 <= nums.length <= 3 * 10^4104
- -100 <= nums[i] <= 100
- 0 <= index < nums.length
- -100 <= val <= 100
- 0 <= left <= right < nums.length
- 最多调用 3 * 10^4104 次 update 和 sumRange 方法
解题思路
这是一道很经典的题目,通常还能拓展出一大类问题。
针对不同的题目,我们有不同的方案可以选择(假设我们有一个数组):
- 数组不变,求区间和:「前缀和」、「树状数组」、「线段树」
- 多次修改某个数,求区间和:「树状数组」、「线段树」
- 多次整体修改某个区间,求区间和:「线段树」、「树状数组」(看修改区间的数据范围)
- 多次将某个区间变成同一个数,求区间和:「线段树」、「树状数组」(看修改区间的数据范围)
这样看来,「线段树」能解决的问题是最多的,那我们是不是无论什么情况都写「线段树」呢?
答案并不是,而且恰好相反,只有在我们遇到第 4 类问题,不得不写「线段树」的时候,我们才考虑线段树。
因为「线段树」代码很长,而且常数很大,实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。
总结一下,我们应该按这样的优先级进行考虑:
- 简单求区间和,用「前缀和」
- 多次将某个区间变成同一个数,用「线段树」
- 其他情况,用「树状数组」
树状数组
本题显然属于第 2 类问题:多次修改某个数,求区间和。
我们使用「树状数组」进行求解。
「树状数组」本身是一个很简单的数据结构,但是要搞懂其为什么可以这样「查询」&「更新」还是比较困难的(特别是为什么可以这样更新),往往需要从「二进制分解」进行出发理解。
因此我这里直接提供「树状数组」的代码,大家可以直接当做模板背过即可。
代码:
class NumArray { int[] tree; int lowbit(int x) { return x & -x; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i]; return ans; } void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tree[i] += u; } int[] nums; int n; public NumArray(int[] _nums) { nums = _nums; n = nums.length; tree = new int[n + 1]; for (int i = 0; i < n; i++) add(i + 1, nums[i]); } public void update(int i, int val) { add(i + 1, val - nums[i]); nums[i] = val; } public int sumRange(int l, int r) { return query(r + 1) - query(l); } } 复制代码
- 时间复杂度:
add
操作和query
的复杂度都是 O(\log{n})O(logn),因此构建数组的复杂度为 O(n\log{n})O(nlogn)。整体复杂度为 O(n\log{n})O(nlogn) - 空间复杂度:O(n)O(n)
树状数组模板
代码:
// 上来先把三个方法写出来 { int[] tree; int lowbit(int x) { return x & -x; } // 查询前缀和的方法 int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i]; return ans; } // 在树状数组 x 位置中增加值 u void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tree[i] += u; } } // 初始化「树状数组」,要默认数组是从 1 开始 { for (int i = 0; i < n; i++) add(i + 1, nums[i]); } // 使用「树状数组」: { void update(int i, int val) { // 原有的值是 nums[i],要使得修改为 val,需要增加 val - nums[i] add(i + 1, val - nums[i]); nums[i] = val; } int sumRange(int l, int r) { return query(r + 1) - query(l); } } 复制代码
最后
这是我们「刷穿 LeetCode」系列文章的第 No.307
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。