<p>Given an integer array <code>nums</code> and two integers <code>lower</code> and <code>upper</code>, return <em>the number of range sums that lie in</em> <code>[lower, upper]</code> <em>inclusive</em>.</p>

<p>Range sum <code>S(i, j)</code> is defined as the sum of the elements in <code>nums</code> between indices <code>i</code> and <code>j</code> inclusive, where <code>i &lt;= j</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [-2,5,-1], lower = -2, upper = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0], lower = 0, upper = 0
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>-10<sup>5</sup> &lt;= lower &lt;= upper &lt;= 10<sup>5</sup></code></li>
	<li>The answer is <strong>guaranteed</strong> to fit in a <strong>32-bit</strong> integer.</li>
</ul>

#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
    class SegmentTree {
    public:
        int n;
        std::vector<int> arr;

        SegmentTree(int size) : n(size), arr(2 * size) {
            arr[0] = 0;
            for (int i = 0; i < n; ++i) {
                arr[i + n] = 1;
            }
            for (int i = n - 1; i > 0; --i) {
                arr[i] = arr[2 * i] + arr[2 * i + 1];
            }
        }

        void addValue(int idx, int val) {
            idx += n;
            arr[idx] += val;
            while (idx > 1) {
                if (idx % 2) {
                    arr[idx / 2] = arr[idx - 1] + arr[idx];
                } else {
                    arr[idx / 2] = arr[idx] + arr[idx + 1];
                }
                idx >>= 1;
            }
        }

        int getSum(int left, int right) {
            int count = 0;
            left += n;
            right += n;
            while (left <= right) {
                if (left % 2) {
                    count += arr[left++];
                }
                if (right % 2 == 0) {
                    count += arr[right--];
                }
                left >>= 1;
                right >>= 1;
            }
            return count;
        }
    };

public:
    int countRangeSum(std::vector<int>& nums, int lower, int upper) {
        std::vector<long long> sum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); ++i) {
            sum[i + 1] = sum[i] + nums[i];
        }

        std::vector<long long> A(sum.begin(), sum.end());
        std::sort(A.begin(), A.end());

        SegmentTree tree(A.size());
        int count = 0;

        for (const auto& x : sum) {
            int idx = std::lower_bound(A.begin(), A.end(), x) - A.begin();
            int lowerIdx = std::lower_bound(A.begin(), A.end(), x + lower) - A.begin();
            int upperIdx = std::upper_bound(A.begin(), A.end(), x + upper) - A.begin() - 1;

            tree.addValue(idx, -1);
            count += tree.getSum(lowerIdx, upperIdx);
        }

        return count;
    }


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

    int result = solution.countRangeSum(nums, lower, upper);
    std::cout << "Count of range sums: " << result << std::endl;

    return 0;
}
};

78328