Binary Indexed Tree Solution


  • 0
    F

    // Binary Indexed Tree

        Long[] arr = null;
        int[] tree = null;
        public int countRangeSum(int[] nums, int lower, int upper) {
            int res = 0; 
            if (nums.length == 0) return res;
            Set<Long> set = new HashSet<>();
            long[] sum = new long[nums.length+1];
            set.add(sum[0]);
            for (int i = 0; i < nums.length; i++) {
                sum[i+1] = sum[i] + nums[i];
                set.add(sum[i+1]);
                set.add(sum[i+1]-lower);
                set.add(sum[i+1]-upper-1);
            }
            
            arr = set.toArray(new Long[0]);
            Arrays.sort(arr);
            tree = new int[arr.length];
            update(Arrays.binarySearch(arr, sum[0]));
            for (int i = 1; i < sum.length; i++) {
                res += get(Arrays.binarySearch(arr, sum[i]-lower));
                res -= get(Arrays.binarySearch(arr, sum[i]-upper-1));
                update(Arrays.binarySearch(arr, sum[i]));
            }
            return res;
        }
    
        private void update(int i) {
            i++;
            while (i <= tree.length) {
                tree[i-1]++;
                i += i&(-i);
            }
        }
        
        private int get(int i) {
            i++;
            int sum = 0;
            while (i > 0) {
                sum += tree[i-1];
                i -= i&(-i);
            }
            return sum;
        }

Log in to reply
 

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