Simple Solution using Binary Indexed Tree


  • 0
    M
    public class Solution {
        private class BIT {
            Map<Long, Integer> bit;
            long min, max;
            public BIT(long[] data) {
                int n = data.length;
                bit = new HashMap<>();
                min = Long.MAX_VALUE;
                max = Long.MIN_VALUE;
                for (long l : data) {
                    min = Math.min(min, l);
                    max = Math.max(max, l);
                }            
            }
            public void insert(long l) {
                long val = l - min + 1;
                while (val <= max - min + 1) {
                    bit.put(val, bit.getOrDefault(val, 0) + 1);
                    val += (val & -val);
                }
            }
            public long get(long l) {
                if (l > max) l = max;
                long val = l - min + 1;
                int sum = 0;
                while (val > 0) {
                    sum += bit.getOrDefault(val, 0);
                    val -= (val & -val);
                }
                return sum;
            }
        }
        public int countRangeSum(int[] nums, int lower, int upper) {
            if (nums == null || nums.length == 0) return 0;
            int n = nums.length;
            long[] sum = new long[n + 1];
            for (int i = 1; i <= n; ++i) {
                sum[i] = sum[i - 1] + nums[i - 1];
            }
            BIT bit = new BIT(sum);
            int cnt = 0;
            for (long l : sum) {
                cnt += bit.get(l - lower) - bit.get(l - upper - 1);
                bit.insert(l);
            }
            return cnt;
        }
    }
    

Log in to reply
 

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