示例1
输入:
nums = [-2,5,-1], lower = -2, upper = 2,
输出:
3
解释:
3个区间分别是: [0,0], [2,2], [0,2],它们表示的和分别为: -2, -1, 2。
typedef long long ll;
class BIT {
private:
static const int MAXN = 100010;
int bit[MAXN];
public:
BIT() {
memset(bit, 0, sizeof bit);
}
int lowbit(int x) {
return x&(-x);
}
void add(int i, int x) {
while (i < MAXN) {
bit[i] += x;
i += lowbit(i);
}
}
void sub(int i, int x) {
while (i < MAXN) {
bit[i] -= x;
i += lowbit(i);
}
}
int sum(int i) {
int s = 0;
while (i > 0) {
s += bit[i];
i -= lowbit(i);
}
return s;
}
};
class ID {
private:
unordered_map<ll, int> mp;
set<ll> st;
int idx;
public:
ID() {
mp.clear();
st.clear();
idx = 1;
}
void addNum(ll x) {
st.insert(x);
}
void proj() {
for (ll x: st) {
mp[x] = idx++;
}
}
int getID(ll x) {
return mp[x];
}
};
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = nums.size();
ll sum = 0, res = 0;
ID id = ID();
BIT bit = BIT();
id.addNum(0);
for (int i = 0; i < n; ++i) {
sum += nums[i];
id.addNum(sum);
id.addNum(sum-lower);
id.addNum(sum-upper);
}
id.proj();
bit.add(id.getID(0), 1);
sum = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i];
int lb = id.getID(sum-upper), rb = id.getID(sum-lower);
res += bit.sum(rb) - bit.sum(lb-1);
bit.add(id.getID(sum), 1);
}
return res;
}
};
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~