SORTING › MERGE SORT
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →Let prefix[t] be the sum of nums[0] through nums[t - 1]. The sum from index i through j is prefix[j + 1] - prefix[i], so every non-empty range corresponds to two prefix positions a < b whose difference lies in [lower, upper]. The task is therefore to count ordered pairs (a, b) with a < b and prefix[b] - prefix[a] in the required interval.
For one earlier prefix value prefix[a], a later value prefix[b] is valid exactly when it lies between prefix[a] + lower and prefix[a] + upper. A divide-and-conquer split puts earlier prefix indices in the left half and later indices in the right half. Once both halves are sorted by value, two pointers can find that value interval for every left element in one scan. The recursive calls count pairs contained within one half; the merge step counts pairs crossing the split.
| MEASURE | BOUND | WHY |
|---|---|---|
| Time | O(n log n) | There are log n recursion levels, and each level scans and merges a total of n + 1 prefix values. Each pointer only advances through its half during a merge, so no right value is revisited within that merge. |
| Space | O(n) extra | The returned count is not output storage, and there is no returned array to include. The temporary merge array can hold O(n) values at the top level; the recursion stack adds O(log n), so the worst-case extra space remains O(n) for every input shape. |
#include <vector>
using namespace std;
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = static_cast<int>(nums.size());
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
long long answer = mergeSort(prefix, 0, n, lower, upper);
return static_cast<int>(answer);
}
private:
long long mergeSort(vector<long long>& prefix, int left, int right,
long long lower, long long upper) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
long long count = 0;
count += mergeSort(prefix, left, mid, lower, upper);
count += mergeSort(prefix, mid + 1, right, lower, upper);
int first = mid + 1;
int beyond = mid + 1;
for (int i = left; i <= mid; ++i) {
while (first <= right &&
prefix[first] - prefix[i] < lower) {
++first;
}
while (beyond <= right &&
prefix[beyond] - prefix[i] <= upper) {
++beyond;
}
count += beyond - first;
}
vector<long long> merged;
merged.reserve(right - left + 1);
int a = left;
int b = mid + 1;
while (a <= mid && b <= right) {
if (prefix[a] <= prefix[b]) {
merged.push_back(prefix[a++]);
} else {
merged.push_back(prefix[b++]);
}
}
while (a <= mid) merged.push_back(prefix[a++]);
while (b <= right) merged.push_back(prefix[b++]);
for (int i = 0; i < static_cast<int>(merged.size()); ++i) {
prefix[left + i] = merged[i];
}
return count;
}
};The split uses indices left through mid and mid + 1 through right. Therefore every pair counted in the current loop has its first prefix index in the left half and its second in the right half, which automatically enforces a < b. The two boundary tests deliberately use < lower and <= upper: the first stops on an included lower endpoint, while the second advances past an included upper endpoint.
You can process prefix sums from left to right and store earlier values in a Fenwick tree after coordinate compression. For the current prefix value cur, earlier values must lie in [cur - upper, cur - lower]. The tree answers how many stored values are below each boundary, so this version avoids recursive merging but still costs O(n log n) time and O(n) extra space. It is a reasonable choice when you already have a Fenwick-tree template; it is not an asymptotic optimisation.
#include <algorithm>
#include <vector>
using namespace std;
class Solution {
class Fenwick {
public:
explicit Fenwick(int size) : tree(size + 1, 0) {}
void add(int index, int value) {
for (int i = index; i < static_cast<int>(tree.size());
i += i & -i) {
tree[i] += value;
}
}
int sum(int count) const {
int result = 0;
for (int i = count; i > 0; i -= i & -i) {
result += tree[i];
}
return result;
}
private:
vector<int> tree;
};
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
int n = static_cast<int>(nums.size());
vector<long long> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
vector<long long> values = prefix;
sort(values.begin(), values.end());
values.erase(unique(values.begin(), values.end()), values.end());
Fenwick bit(static_cast<int>(values.size()));
long long answer = 0;
for (long long cur : prefix) {
long long lowValue = cur - upper;
long long highValue = cur - lower;
int first = static_cast<int>(lower_bound(
values.begin(), values.end(), lowValue) - values.begin());
int afterHigh = static_cast<int>(lower_bound(
values.begin(), values.end(), highValue + 1) - values.begin());
answer += bit.sum(afterHigh) - bit.sum(first);
int rank = static_cast<int>(lower_bound(
values.begin(), values.end(), cur) - values.begin()) + 1;
bit.add(rank, 1);
}
return static_cast<int>(answer);
}
};The insertion happens after the query, so the current prefix cannot pair with itself and every counted earlier prefix has a smaller index. lower_bound gives the first value not less than the lower boundary and the first value greater than the upper boundary after adding one, which produces the same inclusive interval as the merge-sort solution.