C++ leetcode 327. Count of Range Sum CHATGPT Unlimited

AI: Hello human, Start Your Conversation, Ask me anything!
You: solve leetcode 327. Count of Range Sum class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {

}
};

AI: To solve LeetCode problem 327 "Count of Range Sum", you can implement a solution using a merge sort-based approach. Here is a possible implementation of the `countRangeSum` function within the `Solution` class:


cpp
#include <vector>
#include <iostream>

class Solution {
public:
    int countRangeSum(std::vector<int>& nums, int lower, int upper) {
        int count = 0;
        std::vector<long> prefixSum(nums.size() + 1, 0);

        for (int i = 0; i < nums.size(); i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        count = mergeSortCount(prefixSum, 0, prefixSum.size(), lower, upper);

        return count;
    }

    int mergeSortCount(std::vector<long>& prefixSum, int left, int right, int lower, int upper) {
        if (right - left <= 1) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int count = mergeSortCount(prefixSum, left, mid, lower, upper) + mergeSortCount(prefixSum, mid, right, lower, upper);

        int j = mid, k = mid, t = mid;
        std::vector<long> sorted(right - left, 0);

        for (int i = left, r = 0; i < mid; i++, r++) {
            while (j < right && prefixSum[j] - prefixSum[i] < lower) j++;
            while (k < right && prefixSum[k] - prefixSum[i] <= upper) k++;
            while (t < right && prefixSum[t] < prefixSum[i]) sorted[r++] = prefixSum[t++];
            sorted[r] = prefixSum[i];
            count += k - j;
        }

        std::copy(sorted.begin(), sorted.begin() + t - left, prefixSum.begin() + left);

        return count;
    }
};

int main() {
    Solution solution;
    std::vector<int> nums = {-2, 5, -1};
    int lower = -2;
    int upper = 2;

    int result = solution.countRangeSum(nums, lower, upper);

    std::cout << "Count of range sum within [" << lower << ", " << upper << "]: " << result << std::endl;

    return 0;
}



In this implementation, the `countRangeSum` function calculates the prefix sum of the input vector `nums` and then calls the `mergeSortCount` function to perform a merge sort-based counting of the range sums within the specified `lower` and `upper` bounds. The `mergeSortCount` function recursively divides the array and counts the valid range sums. Finally, the main function demonstrates how to use the `Solution` class to solve the problem for a sample input.