# Accepted Java solution using BST and range search.

• Use sum[i] (sum from nums[0] to nums[i]) as node key to build the BST.

if we want ( lower <= sum[j] - sum[i] <= upper ), which is equal to ( sum[j] - upper <= sum[i] <= sum[j] - lower )
So the problem can be viewed as counting the nodes between sum[j] - upper and sum[j] - lower form previously-built BST.

Two recursive helper funtions:
searchRange: search for how many nodes in the previously-built BST, that fall into the provided range;
insert: used for building the BST, also handles duplicates.

Average runtime should be O(nlogn).

``````public class Solution {
class TreeNode {
long val;  // need to be long to avoid int overflow
int rep;  // count repeated sum[i]
TreeNode left,  right;
TreeNode (long val) {
this.val = val; this.rep = 1;
left = null; right = null;
}
}

public int countRangeSum(int[] nums, int lower, int upper) {
int res = 0;
long sum = 0;
TreeNode root = new TreeNode(0L); // dummy root
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
res += searchRange(root, sum - upper, sum - lower);
insert(root, sum);
}
return res;
}

private int searchRange(TreeNode root, long low, long high) {
if (root == null) return 0;
int res = 0;

if (root.val > low) res += searchRange(root.left, low, high);
if (root.val >= low && root.val <= high) res += root.rep;
if (root.val < high) res += searchRange(root.right, low, high);

return res;
}

private TreeNode insert(TreeNode root, long key) {
if (root == null) return new TreeNode(key);

if (root.val > key) root.left = insert(root.left, key);
else if (root.val < key) root.right = insert(root.right, key);
else root.rep++;

return root;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.