LeetCode 303. 区域和检索 – 数组不可变

303. 区域和检索 – 数组不可变

【前缀和】朴素前缀和

class NumArray {

    int[] pre;

    public NumArray(int[] nums) {
        int n = nums.length;
        pre = new int[n + 1];
        for(var i = 0;i < n; i++){
            pre[i + 1] = pre[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return pre[right + 1] - pre[left];
    }
}

【树状数组】

class NumArray {

    int[] tree;
    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;
        tree = new int[n + 1];
        for(var i = 0; i < n; i++){
            add(i + 1, nums[i]);
        }
    }
    
    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;
        int mid = (l + r) >>> 1;
        k <<= 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(x > mid) return ask(k + 1, mid + 1, r, x, y);
        else if(y <= mid) return ask(k, l, mid, 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 = nums.length;
        f = new int[n * 4 + 1];
        build(1, 1, n);
    }
    
    public int sumRange(int left, int right) {
        return ask(1, 1, n, left + 1, right + 1);
    }
}