网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 307. 区域和检索 - 数组可修改 ，难度为 中等。
Tag : 「区间和」、「树状数组」、「线段树」
给你一个数组 nums，请你完成两类查询，其中一类查询要求更新数组下标对应的值，另一类查询要求返回数组中某个范围内元素的总和。
实现 NumArray 类：
NumArray(int[] nums)用整数数组nums初始化对象void update(int index, int val)将nums[index]的值更新为valint 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^41<=nums.length<=3∗104
- -100 <= nums[i] <= 100−100<=nums[i]<=100
- 0 <= index < nums.length0<=index<nums.length
- -100 <= val <= 100−100<=val<=100
- 0 <= left <= right < nums.length0<=left<=right<nums.length
- 最多调用 3 * 10^43∗104 次
update和sumRange方法
解题思路
这是一道很经典的题目，通常还能拓展出一大类问题。
针对不同的题目，我们有不同的方案可以选择（假设我们有一个数组）：
- 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
- 多次修改某个数（单点），求区间和：「树状数组」、「线段树」
- 多次修改某个区间，输出最终结果：「差分」
- 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
- 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
这样看来，「线段树」能解决的问题是最多的，那我们是不是无论什么情况都写「线段树」呢？
答案并不是，而且恰好相反，只有在我们遇到第 4/5 类问题，不得不写「线段树」的时候，我们才考虑线段树。
因为「线段树」代码很长，而且常数很大，实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。
总结一下，我们应该按这样的优先级进行考虑：
- 简单求区间和，用「前缀和」
- 多次将某个区间变成同一个数，用「线段树」
- 其他情况，用「树状数组」
树状数组
本题只涉及「单点修改」和「区间求和」，属于「树状数组」的经典应用。
「树状数组」本身是一个很简单的数据结构，但是要搞懂其为什么可以这样「查询」&「更新」还是比较困难的（特别是为什么可以这样更新），往往需要从「二进制分解」进行出发理解。
树状数组涉及的操作有两个，复杂度均为 O(\log{n})O(logn)：
void add(int x, int u)：含义为在 xx 的位置增加 uu（注意位置下标从 11 开始）；int query(int x)：含义为查询从 [1, x][1,x] 区间的和为多少（配合容斥原理，可实现任意区间查询）。
代码：
class NumArray { int[] tr; int lowbit(int x) { return x & -x; } void add(int x, int u) { for (int i = x; i <= n; i += lowbit(i)) tr[i] += u; } int query(int x) { int ans = 0; for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i]; return ans; } int[] nums; int n; public NumArray(int[] _nums) { nums = _nums; n = nums.length; tr = new int[n + 10]; for (int i = 0; i < n; i++) add(i + 1, nums[i]); } public void update(int index, int val) { add(index + 1, val - nums[index]); nums[index] = val; } public int sumRange(int left, int right) { return query(right + 1) - query(left); } } 复制代码
- 时间复杂度：插入和查询复杂度均为 O(\log{n})O(logn)
- 空间复杂度：O(n)O(n)
线段树
相比「树状数组」，另外一个更为进阶且通用的做法是使用「线段树」。
线段树的所有操作同样为 O(\log{n})，O(logn)，由于本题不涉及「区间修改」操作，因此我们的线段树只需要实现 pushup 操作（子节点往上更新父节点），而不需要实现用于懒标记的 pushdown 操作（父节点往下传递「更新」的操作）。
关于线段树设计的几种操作：
void build(int u, int l, int r)：含义为从编号为 uu 的节点开始，构造范围为 [l,r][l,r] 的树节点；void update(int u, int x, int v)：含义为从编号为uu的节点开始，在xx位置增加vv；
- 更具一般性（涉及区间修改）的操作应该为
void update(int u, int l, int r, int v)，代表在 [l, r][l,r] 范围增加 vv；
int query(int u, int l, int r)：含义为从编号为 uu 的节点开始，查询 [l, r][l,r] 区间和为多少。
注意：对于编号为
u的节点而言，其左子节点的编号为u << 1，其右节点的编号为u << 1 | 1。
代码（考虑为线段树增加 static 优化的代码见 P2P2，样例个数较少，优化不明显）：
class NumArray { Node[] tr; class Node { int l, r, v; Node(int _l, int _r) { l = _l; r = _r; } } void build(int u, int l, int r) { tr[u] = new Node(l, r); if (l == r) return; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); } void update(int u, int x, int v) { if (tr[u].l == x && tr[u].r == x) { tr[u].v += v; return ; } int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) update(u << 1, x, v); else update(u << 1 | 1, x, v); pushup(u); } int query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; int mid = tr[u].l + tr[u].r >> 1; int ans = 0; if (l <= mid) ans += query(u << 1, l, r); if (r > mid) ans += query(u << 1 | 1, l, r); return ans; } void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; } int[] nums; public NumArray(int[] _nums) { nums = _nums; int n = nums.length; tr = new Node[n * 4]; build(1, 1, n); for (int i = 0; i < n; i++) update(1, i + 1, nums[i]); } public void update(int index, int val) { update(1, index + 1, val - nums[index]); nums[index] = val; } public int sumRange(int left, int right) { return query(1, left + 1, right + 1); } } 复制代码
class NumArray { static int N = 30010; static Node[] tr = new Node[N * 4]; class Node { int l, r, v; Node(int _l, int _r) { l = _l; r = _r; } } void build(int u, int l, int r) { if (tr[u] == null) { tr[u] = new Node(l, r); } else { tr[u].l = l; tr[u].r = r; tr[u].v = 0; } if (l == r) return ; int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); } void update(int u, int x, int v) { if (tr[u].l == x && tr[u].r == x) { tr[u].v += v; return ; } int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) update(u << 1, x, v); else update(u << 1 | 1, x, v); pushup(u); } int query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].v; int mid = tr[u].l + tr[u].r >> 1; int ans = 0; if (l <= mid) ans += query(u << 1, l, r); if (r > mid) ans += query(u << 1 | 1, l, r); return ans; } void pushup(int u) { tr[u].v = tr[u << 1].v + tr[u << 1 | 1].v; } int[] nums; public NumArray(int[] _nums) { nums = _nums; int n = nums.length; build(1, 1, n); for (int i = 0; i < n; i++) update(1, i + 1, nums[i]); } public void update(int index, int val) { update(1, index + 1, val - nums[index]); nums[index] = val; } public int sumRange(int left, int right) { return query(1, left + 1, right + 1); } } 复制代码
- 时间复杂度：插入和查询复杂度均为 O(\log{n})O(logn)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.307 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
