<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:
    int count_adjucent_rng_sums(const vector<long>& rng_sum_l,
                                const vector<long>& rng_sum_r, int lower,
                                int upper) {
        int cnt{0};
        auto lo_bound{static_cast<int>(rng_sum_l.size()) - 1};
        auto up_bound{static_cast<int>(rng_sum_l.size()) - 1};
        for (const auto& n : rng_sum_r) {
            int l{0};
            int r{lo_bound};
            while (l <= r) {
                int mid{(l + r) / 2};
                if (lower <= n + rng_sum_l[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            // if (l == static_cast<int>(rng_sum_l.size())) continue;
            lo_bound = max(0, r);

            int ll{0};
            r = up_bound;
            while (ll <= r) {
                int mid{(ll + r) / 2};
                if (upper < n + rng_sum_l[mid])
                    r = mid - 1;
                else
                    ll = mid + 1;
            }
            if (r == -1) break;
            up_bound = r;

            cnt += ll - l;
        }
        return cnt;
    }

   public:
    int countRangeSum(const vector<int>& nums, int lower, int upper) {
        int total_cnt{0};

        for (const auto& n : nums) {
            if (lower <= n && n <= upper) ++total_cnt;
        }

        for (int step{1}; step < nums.size(); step <<= 1) {
            for (int i{0}; i + step < nums.size();) {
                auto mid{i + step};
                auto i_r{
                    min(mid + step - 1, static_cast<int>(nums.size()) - 1)};
                std::vector<long> rng_sum_mid_to_l;
                std::vector<long> rng_sum_mid_to_r;
                rng_sum_mid_to_l.push_back(nums[mid - 1]);
                for (auto j{mid - 2}; j >= i; --j)
                    rng_sum_mid_to_l.push_back(rng_sum_mid_to_l.back() +
                                               nums[j]);
                sort(rng_sum_mid_to_l.begin(), rng_sum_mid_to_l.end());
                rng_sum_mid_to_r.push_back(nums[mid]);
                for (auto j{mid + 1}; j <= i_r; ++j)
                    rng_sum_mid_to_r.push_back(rng_sum_mid_to_r.back() +
                                               nums[j]);
                sort(rng_sum_mid_to_r.begin(), rng_sum_mid_to_r.end());

                total_cnt += count_adjucent_rng_sums(
                    rng_sum_mid_to_l, rng_sum_mid_to_r, lower, upper);

                i = i_r + 1;
            }
        }
        return total_cnt;
    }
};
282080