solution with Fenwich Tree


  • 0
    M

    public class NumArray {
    // Fenwich Tree;
    // learn Fenwich Tree Features
    int[] Bit;
    int[] init;

    public NumArray(int[] nums) {
        if(nums == null || nums.length == 0) return;
        int len = nums.length;
        Bit = new int[len+1];
        init = new int[len];
        for(int i = 0; i < len; i++) {
            update(i, nums[i]);
        }
    }
    
    public void update(int i, int val) {
        int add = val - init[i];
        init[i] = val;
        // update tree value
        int idx = i+1;
        while(idx < Bit.length) {
            Bit[idx] += add;
            idx += idx&(-idx);
        }
    }
    
    public int sumRange(int i, int j) {
        return getSum(j+1) - getSum(i);
    }
    public int getSum(int idx) {
        int sum = 0;
        while(idx > 0) {
            sum += Bit[idx];
            idx -= idx&(-idx);
        }
        return sum;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.