307. 区域和检索 - 数组可修改

题目

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求 更新 数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right
实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值 更新 为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], …, nums[right]）

示例 1：

输入：
[“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); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2); // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

1 <= nums.length <= 3 10^4
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/range-sum-query-mutable
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个题和不同的是，涉及到了数组的更新问题，如果还使用前缀和数组，每更新一处的值就需要影响到前缀和数组的很多值，更新和查询都会达到#card=math&code=O%28n%29&id=xgv5C)时间复杂度。使用「线段树」或者「树状数组」可以将更新和查询操作都降到#card=math&code=O%28logn%29&id=gwg4b)复杂度。真正去学就发现也没有那么难，入门可以参考liweiwei的「文章」和「视频」。

目前我对「线段树」或者「树状数组」只是有一个基本的认识，了解了两者的特点和使用场景。比如「线段树」是一棵「平衡二叉树」（不一定是完全二叉树），「树状数组」是一棵「多叉树」，「线段树」可以用在「区间和查询」(还可以处理区间最值)和「单点更新」问题中，「树状数组」可以处理「前缀和查询」和「单点更新」问题，「树状数组」通过前缀和相减也可以获得区间和。总的来说，树状数组有的功能线段树都有，但反过来就不成立，且线段树代码复杂很多。两者都不适用于区间中有「添加和删除」元素的操作。

需要多应用才能更好地掌握这类进阶的数据结构，这里就不多做介绍了。至于本题，套用「线段树」或者「树状数组」的模板即可解答。

代码

线段树

class NumArray {
    private SegmentTree<Integer> segmentTree;
    public NumArray(int[] nums) {
        Integer[] data = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            data[i] = nums[i];
        }
        segmentTree = new SegmentTree<>(data, (a, b) -> a + b);
    }
    public void update(int i, int val) {
        segmentTree.set(i, val);
    }
    public int sumRange(int i, int j) {
        return segmentTree.query(i, j);
    }
}
interface Merge<E> {
    E merge(E e1, E e2);
}
class SegmentTree<E> {
    private E[] tree;
    private E[] data;
    private Merge<E> merge;
    public SegmentTree(E[] arr, Merge<E> merge) {
        this.merge = merge;
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[]) new Object[4 * arr.length];
        buildSegmentTree(0, 0, arr.length - 1);
    }
    private void buildSegmentTree(int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        int mid = l + (r - l) / 2;
        int leftChild = leftChild(treeIndex);
        int rightChild = rightChild(treeIndex);
        buildSegmentTree(leftChild, l, mid);
        buildSegmentTree(rightChild, mid + 1, r);
        tree[treeIndex] = merge.merge(tree[leftChild], tree[rightChild]);
    }
    public E query(int dataL, int dataR) {
        if (dataL < 0 || dataL >= data.length || dataR < 0 || dataR >= data.length || dataL > dataR) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        return query(0, 0, data.length - 1, dataL, dataR);
    }
    private E query(int treeIndex, int l, int r, int dataL, int dataR) {
        if (l == dataL && r == dataR) {
            return tree[treeIndex];
        }
        int mid = l + (r - l) / 2;
        int leftChildIndex = leftChild(treeIndex);
        int rightChildIndex = rightChild(treeIndex);
        if (dataR <= mid) {
            return query(leftChildIndex, l, mid, dataL, dataR);
        }
        if (dataL >= mid + 1) {
            return query(rightChildIndex, mid + 1, r, dataL, dataR);
        }
        E leftResult = query(leftChildIndex, l, mid, dataL, mid);
        E rightResult = query(rightChildIndex, mid + 1, r, mid + 1, dataR);
        return merge.merge(leftResult, rightResult);
    }
    public void set(int dataIndex, E val) {
        if (dataIndex < 0 || dataIndex >= data.length) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        data[dataIndex] = val;
        set(0, 0, data.length - 1, dataIndex, val);
    }
    private void set(int treeIndex, int l, int r, int dataIndex, E val) {
        if (l == r) {
            tree[treeIndex] = val;
            return;
        }
        int leftTreeIndex = leftChild(treeIndex);
        int rightTreeIndex = rightChild(treeIndex);
        int mid = l + (r - l) / 2;
        if (dataIndex >= mid + 1) {
            set(rightTreeIndex, mid + 1, r, dataIndex, val);
        }
        if (dataIndex <= mid) {
            set(leftTreeIndex, l, mid, dataIndex, val);
        }
        tree[treeIndex] = merge.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    }
    public int leftChild(int index) {
        return 2 * index + 1;
    }
    public int rightChild(int index) {
        return 2 * index + 2;
    }
}
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */

树状数组

class NumArray {
    FenwickTree fenwickTree;
    int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
        fenwickTree = new FenwickTree(nums);
    }
    public void update(int index, int val) {
        fenwickTree.update(index + 1, val - nums[index]);
        nums[index] = val;
    }
    public int sumRange(int left, int right) {
        return fenwickTree.query(right + 1) - fenwickTree.query(left);
    }
}
public class FenwickTree {
    private int[] tree;
    private int len;
    public FenwickTree(int n) {
        this.len = n;
        tree = new int[n + 1];
    }
    public FenwickTree(int[] nums) {
        this.len = nums.length;
        tree = new int[this.len + 1];
        for (int i = 1; i <= len; i++) {
            update(i, nums[i - 1]);
        }
    }
    public void update(int i, int delta) {
        while (i <= len) {
            tree[i] += delta;
            i += lowbit(i);
        }
    }
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }
    public static int lowbit(int x) {
        return x & (-x);
    }
}