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

#define ll long long

struct Node {
    vector<ll> arr;
    Node() {
        arr = {};
    }
    Node(ll a) {
        arr = {a};
    }

    ll query(ll l, ll r) {
        auto lb = lower_bound(arr.begin(), arr.end(), l);
        auto ub = upper_bound(arr.begin(), arr.end(), r);
        return ub-lb;
    }

    static Node combine(Node &l, Node &r) {
        Node res;
        vector<ll> &al = l.arr, &ar = r.arr;
        res.arr = al;
        for(auto x: ar) res.arr.push_back(x);

        sort(res.arr.begin(), res.arr.end());

        return res;
    }
};

struct SegmentTree {
    vector<Node> tree;
    ll n;

    void build(vector<ll> &arr) {
        n = arr.size();
        tree.assign(4 * n + 1, Node());
        build(1, 0, n - 1, arr);
    }

    void build(ll v, ll tl, ll tr, vector<ll> &arr) {
        if(tl == tr) {
            tree[v] = Node(arr[tl]);
        }else {
            ll tm = (tl + tr) / 2;
            build(2 * v, tl, tm, arr);
            build(2 * v + 1, tm + 1, tr, arr);
            tree[v] = Node::combine(tree[2 * v], tree[2 * v + 1]);
        }
    }

    ll query(ll v, ll tl, ll tr, ll l, ll r, ll low, ll high) {
        if(tl > r || tr < l) {
            return 0;
        }
        if(tl >= l && tr <= r) {
            return tree[v].query(low, high);
        }
        ll tm = (tl + tr) / 2;
        ll ql = query(2 * v, tl, tm, l, r, low, high);
        ll qr = query(2 * v + 1, tm + 1, tr, l, r, low, high);
        return ql + qr;
    }

    ll query(ll l, ll r, ll low, ll high) {
        return query(1, 0, n - 1, l, r ,low, high);
    }
};

class Solution {
public:
    vector<ll> buildPrefix(vector<int> &nums) {
        ll n = nums.size();
        vector<ll> pref(n + 1, 0);
        for(ll i = 1; i <= n; i++) {
            pref[i] = pref[i - 1] + nums[i - 1];
        }
        return pref;
    }

    ll countRangeSum(vector<int>& nums, ll lower, ll upper) {
        auto pref = buildPrefix(nums);

        SegmentTree st;
        st.build(pref);

        ll n = nums.size();

        ll ans = 0;
        for(ll i = 1; i <= n; i++) {
            ll currPref = pref[i];
            
            ll lowTarget = currPref - lower;
            ll highTarget = currPref - upper;

            ll q = st.query(0, i - 1, highTarget, lowTarget);
            ans += q;
        }
        return ans;
    }
};
379105