LeetCode Q327: Count of Range Sum (hard)

Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Solution 1:

My solution is to pre-processing the array and compute range sum, than build BST for searching. In C++, to allow duplicated nodes in a BST, you should use multimap.

Revised version of solution 1

Solution 2:
Analysis of the solution is given in this post.