2019-12-17 18:56:56
问题描述：
问题求解：
本题个人感觉还是很有难度的，主要的难点在于如何将题目转化为bit计数问题。
首先构建一个presum数组，这个没有问题。
需要对于任意一个j，我们需要知道的是presum[i]的个数使得 lower <= presum[j] - presum[i] <= upper。
上述等式等价于求符合 presum[j] - upper <= presum[i] <= presum[j] - lower 的presum[i]的个数。
看到这个是不是有点眼熟了呢，求满足某个条件的区间的个数，这个和逆序数问题是完全一致的，只是在那个问题里我们只有一个上界，这里多了一个下界罢了。
同逆序数的解法，这里我们可以使用树状数组来进行求解。
public int countRangeSum(int[] nums, int lower, int upper) {
if (nums.length == 0) return 0;
int res = 0;
int n = nums.length;
long[] presum = new long[n];
presum [0] = nums[0];
for (int i = 1; i < n; i++) presum[i] = presum[i - 1] + nums[i];
long[] copy = Arrays.copyOf(presum, n);
Arrays.sort(copy);
TreeMap<Long, Integer> map = new TreeMap<>();
int rank = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || copy[i] != copy[i - 1]) {
map.put(copy[i], ++rank);
}
}
int[] bit = new int[map.size() + 1];
for (int i = 0; i < n; i++) {
if (presum[i] >= lower && presum[i] <= upper) res += 1;
Long r = map.floorKey(presum[i] - lower);
Long l = map.ceilingKey(presum[i] - upper);
if (l != null && r != null) res += query(bit, map.get(r)) - query(bit, map.get(l) - 1);
update(bit, map.get(presum[i]));
}
return res;
}
private void update(int[] bit, int idx) {
for (int i = idx; i < bit.length; i += i & -i) {
bit[i] += 1;
}
}
private int query(int[] bit, int idx) {
int res = 0;
for (int i = idx; i > 0; i -= i & -i) {
res += bit[i];
}
return res;
}