<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 <algorithm>
#include <vector>
using namespace std;

class Solution {
   private:
    struct node {
        int cnt_own;
        int cnt_left{0};
        long num;
    };
    constexpr int i_root(const int l, const int r) const { return (l + r) / 2; }

    int build_tree(vector<node>& tree, const int l, const int r) {
        if (r < l) return 0;
        if (l == r) return tree[l].cnt_own;
        auto pos{i_root(l, r)};
        tree[pos].cnt_left = build_tree(tree, l, pos - 1);
        return tree[pos].cnt_left + tree[pos].cnt_own +
               build_tree(tree, pos + 1, r);
    }
    int count_less(const vector<node>& tree, long target) {
        int total_cnt{0};
        int l{0};
        int r{static_cast<int>(tree.size()) - 1};
        while (l <= r) {
            auto pos{i_root(l, r)};
            if (target < tree[pos].num)
                r = pos - 1;
            else if (target == tree[pos].num) {
                total_cnt += tree[pos].cnt_left;
                break;
            } else {
                total_cnt += tree[pos].cnt_own + tree[pos].cnt_left;
                l = pos + 1;
            }
        }
        return total_cnt;
    }
    void delete_one_count(vector<node>& tree, long target) {
        int l{0};
        int r{static_cast<int>(tree.size()) - 1};
        while (true) {
            auto pos{i_root(l, r)};
            if (target < tree[pos].num) {
                tree[pos].cnt_left--;
                r = pos - 1;
            } else if (target == tree[pos].num) {
                tree[pos].cnt_own--;
                return;
            } else {
                l = pos + 1;
            }
        }
    }

   public:
    int countRangeSum(const vector<int>& nums, int lower, int upper) {
        vector<long> rng_sum_from_left;
        rng_sum_from_left.reserve(nums.size());

        rng_sum_from_left.push_back(nums[0]);
        for (auto it{nums.cbegin() + 1}; it != nums.cend(); ++it)
            rng_sum_from_left.push_back(rng_sum_from_left.back() + *it);

        auto to_sort{rng_sum_from_left};
        sort(to_sort.begin(), to_sort.end());

        vector<node> tree;
        for (auto it{to_sort.cbegin()}; it != to_sort.cend(); ++it) {
            int cnt{1};
            auto val{*it};
            while (it + 1 != to_sort.cend() && *(it + 1) == val) {
                ++cnt;
                ++it;
            }
            tree.push_back({cnt, 0, val});
        }
        to_sort.clear();
        to_sort.shrink_to_fit();

        build_tree(tree, 0, tree.size() - 1);

        int total_cnt{0};
        long correction{0};
        for (int i = 0; i < rng_sum_from_left.size() - 1; i++) {
            total_cnt += count_less(tree, upper + correction + 1) -
                         count_less(tree, lower + correction);
            delete_one_count(tree, rng_sum_from_left[i]);
            correction += nums[i];
        }
        total_cnt += count_less(tree, upper + correction + 1) -
                     count_less(tree, lower + correction);
        return total_cnt;
    }
};
92881