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

    struct SegmentTree {
        SegmentTree* left;
        SegmentTree* right;
        int count;
        long min;
        long max;
        
        SegmentTree(vector<long>& nums, int l, int r):left(NULL),right(NULL) {
            if (l>r) {
                return;
            }
            min = nums[l];
            max = nums[r];
            count=0;
            
            if (l==r) {
                return;
            }
            
            int m = (l+r)/2;
            if (l<=m) {
                left = new SegmentTree(nums, l,m);
            } else {
                left=NULL;
            }
            if (m+1<=r) {
                right = new SegmentTree(nums, m+1, r);
            } else {
                right = NULL;
            }
        }
        
        void add(long value) {
            if (value<min || value>max) {
                return;
            }
            if (value==0) {
            }
            count++;
            if (left && value<=left->max) {
                left->add(value);
            } else if (right && value>=right->min) {
                right->add(value);
            }
        }
        
        int getCount(long minValue, long maxValue) {
            if (minValue<=min && max<=maxValue) {
                return count;
            }
            
            if (maxValue<min || minValue>max) {
                return 0;
            }
            
            int leftCount = left ? left->getCount(minValue, maxValue) : 0;
            int rightCount = right ? right->getCount(minValue, maxValue) : 0;
            
            return leftCount+rightCount;
        }
        
    };
        
        
    public:
        int countRangeSum(vector<int>& nums, int lower, int upper) {
            if (nums.size()==0) {
                return 0;
            }
            
            unordered_set<long> values;
            long sum = 0;
            for(int i=0;i<nums.size();++i) {
                sum+=nums[i];
                values.insert(sum);
            }
    
            vector<long> sums;
            for(auto& v : values) {
                sums.push_back(v);
            }
    
            sort(sums.begin(), sums.end());
            
            SegmentTree* tree = new SegmentTree(sums, 0, sums.size()-1);
    
            int count = 0;
            for(int i=nums.size()-1;i>=0;i--) {
                tree->add(sum);
                sum-=nums[i];
                count += tree->getCount(lower+sum, upper+sum);
            }
            
            return count;
            
        }
};
219014