Count of Range Sum — Editorial

Opening the reading…

Intuitionthe subarray condition becomes an ordered prefix-sum pair

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.

The two pointers delimit an inclusive value interval in the right half.

Approach

Build prefix with n + 1 entries, including prefix[0] = 0, because a range beginning at index 0 needs a prefix on the left of it.

Recursively sort and process prefix[left] through prefix[right], stopping when the segment has one entry; a single prefix cannot form a pair with another entry inside that segment.

Count the valid pairs entirely inside the left half and entirely inside the right half before merging, because those pairs are not crossing pairs and must not be counted by the current merge.

For every left prefix value, advance one pointer until right values are at least prefix[i] + lower, and another until they are greater than prefix[i] + upper; the difference between the pointers is exactly the number of valid right values.

Keep both pointers moving forward across left values, because the left half is sorted and both target boundaries only increase; resetting them for every left value would lose the linear merge bound.

Merge the two sorted halves back into prefix, because the parent call relies on each child segment being sorted before it counts its own crossing pairs.

Return the accumulated count as an int; the stated guarantee makes the final answer fit, while long long is still required for prefix differences and intermediate sums.

Complexitythe merge work dominates the recursion

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.

Here n is nums.length. The prefix array has n + 1 entries.

Annotated solutionC++ · recursive merge sort with explicit linear merges

CPPBuild long long prefix sums, count crossing pairs with two advancing pointers, then merge the halves.

#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.

The Fenwick-tree alternativea different arrangement with the same asymptotic cost

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.

CPPCoordinate-compress prefix values and query the Fenwick tree for the valid earlier-value interval.

#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.