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

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

这里因为要对数组进行频繁修改了，所以前缀和不能胜任了

【树状数组】

class NumArray {

    int[] tree, nums;
    int n;

    int lowbit(int x){
        return x & -x;
    }

    void add(int x, int val){
        while(x <= n){
            tree[x] += val;
            x += lowbit(x);
        }
    }

    int ask(int x){
        int ret = 0;
        while(x > 0){
            ret += tree[x];
            x -= lowbit(x);
        }
        return ret;
    }
    

    public NumArray(int[] nums) {
        n = nums.length;
        this.nums = nums;
        tree = new int[n + 1];
        for(var 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 ask(right + 1) - ask(left);
    }
}

【线段树】

class NumArray {

    int[] f, a;
    int n;

    void build(int k, int l, int r){
        if(l == r) f[k] = a[l - 1];
        else{
            int mid = (l + r) >>> 1;
            k <<= 1;
            build(k, l, mid);
            build(k + 1, mid + 1, r);
            f[k >>> 1] = f[k] + f[k + 1];
        }
    }

    void add(int k, int l, int r, int x, int y){
        f[k] += y;
        if(l == r) return;
        k <<= 1;
        int mid = (l + r) >>> 1;
        if(x > mid) add(k + 1, mid + 1, r, x, y);
        else add(k, l, mid, x, y);
    }

    int ask(int k, int l, int r, int x, int y){
        if(l == r) return f[k];
        if(l == x && r == y) return f[k];
        int mid = (l + r) >>> 1;
        k <<= 1;
        if(y <= mid) return ask(k, l, mid, x, y);
        if(x > mid) return ask(k + 1, mid + 1, r, x, y);
        else return ask(k, l, mid, x, mid) + ask(k + 1, mid + 1, r, mid + 1, y);
    }

    public NumArray(int[] nums) {
        a = nums;
        n = a.length;
        f = new int[n * 4 + 1];
        build(1, 1, n);
    }
    
    public void update(int index, int val) {
        add(1, 1, n, index + 1, val - a[index]);
        a[index] = val;
    }
    
    public int sumRange(int left, int right) {
        return ask(1, 1, n, left + 1, right + 1);
    }
}