Count of Range Sum

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(n^2)$ 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.

var ans;

var wlower, wupper;

function merge(left, right) {

  ans += getAns(left, right);

  var tmp = [];

  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift());
    else
      tmp.push(right.shift());
  }

  return tmp.concat(left, right);
}


function mergeSort(a) {
  if (a.length === 1) 
    return a;

  var mid = ~~(a.length / 2)
    , left = a.slice(0, mid)
    , right = a.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}


/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countRangeSum = function(nums, lower, upper) {
  wlower = lower;
  wupper = upper;

  var arr = [];

  arr.push(0);

  nums.forEach(function(item) {
    var last = arr[arr.length - 1];
    arr.push(last + item);
  });

  ans = 0;

  mergeSort(arr);

  return ans;
};


// 返回 b[j] - a[i] 值在 [wlower, wupper] 范围内组数
function getAns(a, b) {

  var sum = 0;

  var lena = a.length; 
  var lenb = b.length;

  var start = 0;
  var end = 0;

  for (var i = 0; i < lenb; i++) {

    // to get start
    while (b[i] - a[start] >= wlower) {
      start++;
    }

    // to get end
    while (b[i] - a[end] > wupper) {
      end++;
    }

    sum += start - end;
  }

  return sum;
}

Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {

  // binary search
  function bSearch(target, a) {
    var start = 0
      , end = a.length - 1;

    while(start <= end) {
      var mid = ~~((start + end) >> 1);
      if (a[mid] >= target)
        end = mid - 1;
      else if (a[mid] < target)
        start = mid + 1;
    }

    return start;
  }

  var tmp = []  // store 
    , ans = [];

  for (var i = nums.length; i--; ) {
    var item = nums[i];

    var index = bSearch(item, tmp);

    ans.unshift(index);
    tmp.splice(index, 0, item);
  }

  return ans;
};

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var countSmaller = function(nums) {
  var arr = []
    , len = nums.length;

  // array to object
  // 增加 index 属性，以便离散化
  for (var i = 0; i < len; i++) {
    var tmp = {};
    tmp.index = i;
    tmp.value = nums[i];
    arr.push(tmp);
  }

  arr.sort(function(a, b) {
    return a.value - b.value;
  });

  // 离散化
  var maxn = 1;
  for (var i = 0; i < len; i++) {
    if (!i) {
      arr[i].nValue = maxn;
    } else {
      arr[i].nValue = arr[i].value === arr[i - 1].value ? maxn : ++maxn;
    }
  }

  arr.sort(function(a, b) {
    return a.index - b.index;
  });


  // 逆序树状数组
  var ans = []
    , sum = [];

  for (var i = 0; i <= maxn; i++)
    sum[i] = 0;

  function lowbit(x) { return x & (-x); }

  function update(index, val) {
    for (var i = index; i <= maxn; i += lowbit(i))
      sum[i] += val;
  } 

  function getSum(index) {
    var ans = 0;
    for (var i = index; i; i -= lowbit(i))
      ans += sum[i];
    return ans;
  }

  for (var i = len - 1; i >= 0; i--) {
    var nValue = arr[i].nValue;
    ans.unshift(getSum(nValue - 1));
    update(nValue, 1);
  }

  return ans;
};

Count Primes

Count the number of prime numbers less than a non-negative number, $n$.

/**
 * @param {number} n
 * @return {number}
 */

var countPrimes = function(n) {
  // if modified to 'var hash = []'
  // it will be Memory Limit Exceeded
  // I don't know why
  // I think both are the same
  var hash = new Array(n)
    , a = Math.sqrt(n);

  for (var i = 2; i <= a; i++) {
    if (!hash[i])
      for (var j = i * i; j < n; j += i)
        hash[j] = true;
  }

  var ans = 0;
  for (var i = 2; i < n; i++)
    if (!hash[i])
      ans ++;

  return ans;
};