# [C++ 29ms 97%] Divide and Conquer Solution

• C++ solution based on @dietpepsi 's brilliant work.
I use a aux array caching merged list to avoid allocating memory every time. The benefits are obvious.

``````int countRangeSum(vector<int>& A, int lower, int upper) {
int n = A.size();
vector<long> prefix(n + 1), aux(n + 1);
for (int i = 0; i < n; ++i)
prefix[i + 1] = prefix[i] + A[i];
return countRangeSum(prefix, 0, n + 1, lower, upper, aux);
}

int countRangeSum(vector<long> &prefix, int beg, int end, int lower, int upper, vector<long> &aux) {
if (end - beg <= 1) return 0;
auto mid = beg + (end - beg) / 2;
auto count = countRangeSum(prefix, beg, mid, lower, upper, aux)
+ countRangeSum(prefix, mid, end, lower, upper, aux);
auto p = beg;
for (int i = beg, j = mid, k = mid, t = mid; i < mid; ++i) {
while (j < end && prefix[j] - prefix[i] <  lower) ++j;
while (k < end && prefix[k] - prefix[i] <= upper) ++k;
while (t < end && prefix[t] < prefix[i]) aux[p++] = prefix[t++];
aux[p++] = prefix[i];
count += k - j;
}
while (beg < p) prefix[beg] = aux[beg++];
return count;
}`````````

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