【区间求和の解决方案】307. 区域和检索 - 数组可修改 :「树状数组」&「线段树」

题目描述

这是 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∗1041 <= nums.length <= 3 * 10^41<=nums.length<=3∗104
• −100<=nums[i]<=100-100 <= nums[i] <= 100−100<=nums[i]<=100
• 0<=index<nums.length0 <= index < nums.length0<=index<nums.length
• −100<=val<=100-100 <= val <= 100−100<=val<=100
• 0<=left<=right<nums.length0 <= left <= right < nums.length0<=left<=right<nums.length
• 最多调用 3∗1043 * 10^43∗104 次 update 和 sumRange 方法

解题思路

这是一道很经典的题目，通常还能拓展出一大类问题。

针对不同的题目，我们有不同的方案可以选择（假设我们有一个数组）：

1. 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
2. 多次修改某个数（单点），求区间和：「树状数组」、「线段树」
3. 多次修改某个区间，输出最终结果：「差分」
4. 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
5. 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）

这样看来，「线段树」能解决的问题是最多的，那我们是不是无论什么情况都写「线段树」呢？

答案并不是，而且恰好相反，只有在我们遇到第 4/5 类问题，不得不写「线段树」的时候，我们才考虑线段树。

因为「线段树」代码很长，而且常数很大，实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。

总结一下，我们应该按这样的优先级进行考虑：

1. 简单求区间和，用「前缀和」
2. 多次将某个区间变成同一个数，用「线段树」
3. 其他情况，用「树状数组」

树状数组

本题只涉及「单点修改」和「区间求和」，属于「树状数组」的经典应用。

「树状数组」本身是一个很简单的数据结构，但是要搞懂其为什么可以这样「查询」&「更新」还是比较困难的（特别是为什么可以这样更新），往往需要从「二进制分解」进行出发理解。

树状数组涉及的操作有两个，复杂度均为 O(log⁡n)O(\log{n})O(logn)：

• void add(int x, int u)：含义为在 xxx 的位置增加 uuu（注意位置下标从 111 开始）；
• int query(int x)：含义为查询从 [1,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(\log{n})O(logn)
• 空间复杂度：O(n)O(n)O(n)

线段树

相比「树状数组」，另外一个更为进阶且通用的做法是使用「线段树」。

线段树的所有操作同样为 O(log⁡n)，O(\log{n})，O(logn)，由于本题不涉及「区间修改」操作，因此我们的线段树只需要实现 pushup 操作（子节点往上更新父节点），而不需要实现用于懒标记的 pushdown 操作（父节点往下传递「更新」的操作）。

关于线段树设计的几种操作：

• void build(int u, int l, int r)：含义为从编号为 uuu 的节点开始，构造范围为 [l,r][l,r][l,r] 的树节点；
• void update(int u, int x, int v)：含义为从编号为 uuu 的节点开始，在 xxx 位置增加 vvv；
  • 更具一般性（涉及区间修改）的操作应该为 void update(int u, int l, int r, int v)，代表在 [l,r][l, r][l,r] 范围增加 vvv；
• int query(int u, int l, int r)：含义为从编号为 uuu 的节点开始，查询 [l,r][l, r][l,r] 区间和为多少。

注意：对于编号为 u 的节点而言，其左子节点的编号为 u << 1，其右节点的编号为 u << 1 | 1。

代码（考虑为线段树增加 static 优化的代码见 P2P2P2，样例个数较少，优化不明显）：

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(\log{n})O(logn)
• 空间复杂度：O(n)O(n)O(n)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.307 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。