Java 6ms Binary Indexed Tree Solution


  • 0
    N
    public class NumArray {
        int[] arr;
        int[] tree;
        int length;
        public NumArray(int[] nums) {
            length = nums.length;
            arr = new int[length];
            tree = new int[length+1];
            for (int i = 0; i < length; i++) {
                update(i, nums[i]);
            }
        }
    
        void update(int i, int val) {
            int delta = val - arr[i];
            arr[i] = val;
            i++;
            while(i <= length) {
                tree[i] += delta;
                i += i&(-i);
            }
        }
    
        public int sumRange(int i, int j) {
            int sumi = 0;
            int sumj = 0;
            j++;
            while (i > 0) {
                sumi += tree[i];
                i -= i &(-i);
                sumj += tree[j];
                j -= j &(-j);
            }
            while (j > 0) {
                sumj += tree[j];
                j -= j &(-j);
            }
            return sumj - sumi;
        }
    }

  • 0

Log in to reply
 

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