My java solution using segment tree


  • 0
    P

    I think the time complexity is O(klogk + n), or O(klogn + n)? please tell me,
    I'm sorry for the style, I don't know how to insert code in this new discuss...:disappointed_relieved: emoji available!

    class SegmentTreeNode {
    int start;
    int end;
    int val;
    SegmentTreeNode left;
    SegmentTreeNode right;
    SegmentTreeNode(int s, int e, int v) { start = s; end = e; val = v;}
    }
    public static int[] getModifiedArray(int len, int[][] updates) {
    int[] res = new int[len];
    SegmentTreeNode root = new SegmentTreeNode(0, len - 1, 0);
    for(int[] update : updates) {
    int s = update[0], e = update[1], v = update[2];
    root = insert(root, s, e, v);
    } //O(klogk) or O(klogn) ??
    fill(res, root); // O(n)
    return res;
    }
    public static void fill(int[] nums, SegmentTreeNode root) {
    if(root == null) return;
    for(int i = root.start; i <= root.end; i++) {
    nums[i] = root.val;
    }
    fill(nums, root.left);
    fill(nums, root.right);
    }
    public static SegmentTreeNode insert(SegmentTreeNode root, int s, int e, int v) {
    if(root.start >= s && root.end <= e) {
    root.val += v;
    return root;
    }
    if(root.end < s || root.start > e) return root;
    if(root.start < s) {
    if(root.right == null){
    root.right = new SegmentTreeNode(s, root.end, root.val);
    root.left = new SegmentTreeNode(root.start, s - 1, root.val);
    }
    }
    if(root.end >= e) {
    if(root.left == null){
    root.left = new SegmentTreeNode(root.start, e, root.val);
    root.right = new SegmentTreeNode(e + 1, root.end, root.val);
    }
    }
    root.left = insert(root.left, s, e, v);
    root.right = insert(root.right, s, e, v);
    return root;
    }


  • 0

    @jiaohy said in My java solution using segment tree:

    I'm sorry for the style, I don't know how to insert code in this new discuss...:disappointed_relieved: emoji available!

    Do you see "COMPOSE ?" in top right of the editor field? Clicking the question mark should give you help.


  • 1
    P

    @jiaohy
    I modify the style!

    class SegmentTreeNode {
    	int start;
    	int end;
    	int val;
    	SegmentTreeNode left;
    	SegmentTreeNode right;
    	SegmentTreeNode(int s, int e, int v) { start = s; end = e; val = v;}
    }
    public static int[] getModifiedArray(int len, int[][] updates) {
        	int[] res = new int[len];
        	SegmentTreeNode root = new SegmentTreeNode(0, len - 1, 0);
        	for(int[] update : updates) {
        		int s = update[0], e = update[1], v = update[2];
        		root = insert(root, s, e, v);
        	}   //O(klogk) or O(klogn) ??
        	fill(res, root);
        	return res;
        }
    	public static void fill(int[] nums, SegmentTreeNode root) {
    		if(root == null)  return;
    		for(int i = root.start; i <= root.end; i++) {
    			nums[i] = root.val;
    		}
    		fill(nums, root.left);
    		fill(nums, root.right);
    	}
        public static SegmentTreeNode insert(SegmentTreeNode root, int s, int e, int v) {
        	if(root.start >= s && root.end <= e) {
        		root.val += v;
        		return root;
        	}
        	if(root.end < s || root.start > e)	return root;
        	if(root.start < s) {
        		if(root.right == null){
        			root.right = new SegmentTreeNode(s, root.end, root.val);
        			root.left = new SegmentTreeNode(root.start, s - 1, root.val);
        		}
        	} 
        	if(root.end >= e) {
        		if(root.left == null){
        			root.left = new SegmentTreeNode(root.start, e, root.val);
        			root.right = new SegmentTreeNode(e + 1, root.end, root.val);
        		}
        	} 
        	root.left = insert(root.left, s, e, v);
    		root.right = insert(root.right, s, e, v);
        	return root;
        }
    

  • 0
    P

    @StefanPochmann Oh I see! Thank you !


Log in to reply
 

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