My Binary Indexed Tree Solution in Java


  • 0
    S
    public class NumArray {
        // Binary Indexed Tree
        int[] tree;
        int[] sums;
        int[] nums;
        int length;
        public NumArray(int[] nums) {
            this.length = nums.length;
            this.tree = new int[length + 1];
            this.sums = new int[length + 1];
            this.nums = nums;
            for (int i = 1; i <= length; i++) {
                sums[i] = sums[i - 1] + nums[i - 1];
            }
            for (int i = 1; i <= length; i++) {
                int idx = i - (i & -i);
                // [idx, i]
                tree[i] = sums[i] - sums[idx];
            }
        }
    
        void update(int i, int val) {
            int idx = i + 1;
            int diff = val - nums[i];
            while (idx <= length) {
                tree[idx] += diff;
                idx += (idx & -idx);
            }
            nums[i] = val;
        }
    
        public int sumRange(int i, int j) {
            int sumj = 0, sumi = 0;
            j = j + 1;
            while (j > 0) {
                sumj += tree[j];
                j -= (j & -j);
            }
            while (i > 0) {
                sumi += tree[i];
                i -= (i & -i);
            }
            return sumj - sumi;
        }
    }
    

Log in to reply
 

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