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


  • 0
    W

    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;
    }```

Log in to reply
 

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