# Simple Solution using Binary Indexed Tree

• ``````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;
}
}
``````

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