# Share my cpp solution based on merge-sort

• ``````class Solution {
vector<long long> x;
int lo, hi;
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
x = vector<long long>(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++) x[i + 1] = x[i] + nums[i];
lo = lower;
hi = upper;
int ans = merge_sort(1, nums.size());
return ans;
}

int merge_sort(int start, int end) {
if (start > end) return 0;
if (start == end) {
if (x[start] - x[start - 1] >= lo and x[start] - x[start - 1] <= hi) return 1;
else return 0;
}
int mid = start + (end - start) / 2;
int ans = merge_sort(start, mid) + merge_sort(mid + 1, end);
ans += merge(start, mid, mid + 1, end);
return ans;
}

int merge(int start1, int end1, int start2, int end2) {
vector<long long> tmp;
int p = start1, q = start2;
int ans = 0;
for (int i = start1; i <= end1; i++) {
int a = upper_bound(x.begin() + start2, x.begin() + 1 + end2, x[i - 1] + hi) - x.begin(),
b = lower_bound(x.begin() + start2, x.begin() + 1 + end2, x[i - 1] + lo) - x.begin();
ans += a - b;
}
while (p <= end1 && q <= end2) {
if (x[p] < x[q]) tmp.push_back(x[p++]);
else tmp.push_back(x[q++]);
}
while (p <= end1) tmp.push_back(x[p++]);
while (q <= end2) tmp.push_back(x[q++]);
for (int i = start1; i <= end2; i++) x[i] = tmp[i - start1];
return ans;
}
};``````

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