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

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {

        // this question was very difficult because of the difficulty in
        // concept and implementation. while the concept is difficult but
        // digestible in the end, the implementation is quite complex
        // considering my lack of knowledge in fenwick trees.

        vector<long> prefix;
        prefix.push_back(0);

        for (int i = 0; i < nums.size(); i++) prefix.push_back((long) nums[i] + prefix[i]);

        // idea:
        // store all start and end points to abuse this inferred logic where
        // prefix[i - 1] + lower < prefix[j] < prefix[i - 1] + upper

        vector<vector<long>> vals;

        for (int i = 0; i < prefix.size(); i++) {
            // cpp sort can sort in lexicographical order!
            // we can use 0, -1 and 1 to determine if an element is
            // a left or right boundary AND make sure duplicates
            // won't cause misorderings between boundaries and actual
            // elements after sorting.

            vals.push_back(vector<long>{prefix[i], 0, i});
            vals.push_back(vector<long>{prefix[i] + lower, -1, i});
            vals.push_back(vector<long>{prefix[i] + upper, 1, i});
        }

        sort(vals.begin(), vals.end());

        // you can view the whole fenwick tree as encompassing
        // BOTH the vals and tree vectors.
        // vals store the actual values which the tree is ordered
        // by, while tree stores "count" of each nodes.
        // it is important to decouple this logic!
        // note that there is "vals" because otherwise we will eat
        // up a lot of memory. However, if question requires a
        // variable size of the tree, we can probably resort to
        // hashmaps instead.

        vector<int> tree(vals.size() + 1);
        tree[0] = 0;

        // store the prefix to tree mappings for o(1) access
        // to the tree when we iterate through the prefix vector.

        unordered_map<int, int> idx;
        unordered_map<int, int> left;
        unordered_map<int, int> right;

        for (int i = 0; i < vals.size(); i++) {
            if (vals[i][1] == 0) {
                idx[vals[i][2]] = i;
                add(tree, i, 1);
            } else if (vals[i][1] == -1) {
                left[vals[i][2]] = i;
            } else {
                right[vals[i][2]] = i;
            }
        }

        int result = 0;

        for (int i = 0; i < prefix.size(); i++) {

            add(tree, idx[i], -1);

            // for each prefix at idx i, find all j > i s.t:
            // prefix[i - 1] + lower < prefix[j] < prefix[i - 1] + upper

            result += query(tree, right[i]) - query(tree, left[i] - 1);
        }

        return result;
    }

    int rsb(int x) {
        return x & (-x);
    }

    void add(vector<int> &tree, int x, int add) {
        x++;
        while (x < tree.size()) {
            tree[x] += add;
            x += rsb(x);
        }
    }

    int query(vector<int> &tree, int x) {
        int result = 0;
        x++;
        while (x > 0) {
            result += tree[x];
            x -= rsb(x);
        }

        return result;
    }
};
349998