Leetcode 307

上一个dalao的分析 , 放弃996了

/**
 * 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
 *
 * 多次修改某个数，求区间和：「树状数组」、「线段树」
 *
 * 多次整体修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间的数据范围）
 *
 * 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间的数据范围）
 *
 */

学了个树状数组方法。

class NumArray {
    int[] tree;

    int lowBits(int x){
        return x & -x;//保留二进制下最后出现的1的位置，其余位置置0
    }
    //当一个偶数与它的负值向与时，结果是能被这个偶数整除的最大的2的n次幂 , 比如10返回2
    //当一个奇数与它的负值向与时结果一定是1

    // 查询前缀和的方法
    int query(int x){
        int ans = 0;
        for (int i = x; i > 0 ; i -= lowBits(i)) {
            ans += tree[i];
        }
        return ans;
    }

    // 在树状数组 x 位置中增加值 u
    void add(int x ,int u){
        for (int i = x; i <= n ; i += lowBits(i)) {
            tree[i] += u;
        }
    }

    int[] nums;
    int n;

    // 初始化「树状数组」
    public NumArray(int[] nums) {
        this.nums = nums;
        n = nums.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            add(i + 1, nums[i]);
        }
    }

    // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - 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);
    }
}