Javascript Solution using segment tree


  • 0
    W
    var Node = function(i, j, sum) {
        this.range = [i, j];
        this.sum = sum;
        this.left = null;
        this.right = null;
    };
    
    var buildTree = function(nums, s, e) {
        var root = new Node(s, e, 0);
        if (s == e) {
            root.sum = nums[s];
            return root;
        }
        var m = s + Math.floor((e-s)/2);
        root.left = buildTree(nums, s, m);
        root.right = buildTree(nums, m+1, e);
        root.sum = root.left.sum+ root.right.sum;
        return root;
    };
    
    var queryTree = function(root, s, e) {
        if (root.range[0] == s && root.range[1] == e) {
            return root.sum;
        }
        var mid = root.range[0] + Math.floor((root.range[1]-root.range[0])/2);
        if (e <= mid) {
            return queryTree(root.left, s, e);
        }
    
        if (mid < s) {
            return queryTree(root.right, s, e);
        }
    
        return queryTree(root.left, s, mid) + queryTree(root.right, mid+1, e);
    };
    
    var increaseTreeNode = function(root, i, val) {
        if (root.range[0] == i && root.range[1] == i) {
            var old = root.sum;
            root.sum = val;
            return val - old;
        }
    
        var mid = root.range[0] + Math.floor((root.range[1]-root.range[0])/2);
        if (i <= mid) {
            var diff = increaseTreeNode(root.left, i, val);;
            root.sum += diff;
            return diff;
        }
    
        var diff = increaseTreeNode(root.right, i, val);
        root.sum += diff;
        return diff;
    }
    
    /**
     * @param {number[]} nums 1:35
     */
    var NumArray = function(nums) {
        var n = nums.length;
        if ( n == 0) {
            this.segTree = null;
            return;
        }
        this.segTree = buildTree(nums, 0, n-1);
    };
    
    
    /**
     * @param {number} i
     * @param {number} val
     * @return {void}
     */
    NumArray.prototype.update = function(i, val) {
        if (!this.segTree) return;
    
        increaseTreeNode(this.segTree, i, val);
    };
    
    /**
     * @param {number} i
     * @param {number} j
     * @return {number}
     */
    NumArray.prototype.sumRange = function(i, j) {
        if (!this.segTree) return 0;
    
        return queryTree(this.segTree, i, j);
    };
    
    
    

Log in to reply
 

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