Range Sum Query  Immutable


@readonlyfile Well...
Submission Result: Compile Error
Line 3: error: cannot find symbol: class Pair





JavaScript implementations of the suggested accepted solutions are receiving time limit exceeded. Can anyone advise?
var NumArray = function(nums) { this.cache = {}; for (var i = 0; i < nums.length; i++) { var value = 0; for (var j = i; j < nums.length; j++) { value += nums[j]; this.cache[i+":"+j] = value; // create simple string key } } }; NumArray.prototype.sumRange = function(i, j) { return this.cache[i+":"+j]; };

It is true you can get overflow in the third solution, but this doesn't invalidate the method.
Let's try an example with an array of 300 entries of 100 million. The sum will obviously overflow, but when calculating sumRange(i, j), we can distinguish two possibilities: the sum doesn't overflow in the interval: sum[i] = actual sum up to i  x * 2^321 and sum[j+1] = actual sum up to and including j  x * 2^321; when calculating sum[j+1]  sum[i] the overflows will balance out.
 the sum does overflow in the inteval: sum[i] = actual sum up to i  x * 2^321 and sum[j+1] = actual sum up to and including j  (x+1) * 2^321; when calculating sum[j+1]  sum[i], this results in the actual result  2^321, which will underflow to the actual result.