JavaScript solution with Segment Tree


  • 0
    L
    function NumArray(nums) {
    	var tree = [];
    	build(0, nums.length - 1, 0);
    	return {sumRange, update};
    
    	function sumRange(left, right) {
    		return sumUtil(0, nums.length - 1, 0);
    
    		function sumUtil(currLeft, currRight, treeIdx) {
    			if (left > currRight || right < currLeft) return 0;
    			if (left <= currLeft && right >= currRight) return tree[treeIdx];
    
    			var mid = currLeft + ((currRight - currLeft) >> 1);
    			return sumUtil(currLeft, mid, treeIdx * 2 + 1) +
    				sumUtil(mid + 1, currRight, treeIdx * 2 + 2);
    		}
    	}
    
    	function update(idx, val) {
    		var diff = val - nums[idx];
    		nums[idx] = val;
    		updateUtil(0, nums.length - 1, 0);
    
    		function updateUtil(left, right, treeIdx) {
    			if (idx >= left && idx <= right) {
    				tree[treeIdx] += diff;
    				if (left === right) return;
    				var mid = left + ((right - left) >> 1);
    				updateUtil(left, mid, treeIdx * 2 + 1);
    				updateUtil(mid + 1, right, treeIdx * 2 + 2);
    			}
    		}
    	}
    
    	function build(left, right, idx) {
    		if (left > right) return;
    		var mid = left + ((right - left) >> 1);
    		var sum = left === right ? nums[left] :
    			build(left, mid, idx * 2 + 1) + build(mid + 1, right, idx * 2 + 2);
    
    		tree[idx] = sum;
    		return sum;
    	}
    }

Log in to reply
 

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