*Java* standard solution using segment tree


  • 0
    E

    For brief explanations, or if you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java/blob/master/SegmentTree/RangeSumMutable.java

    public class NumArray {
    int N; // length of array
    int[] nums; // array copy
    TreeNode root; // range sum tree nodes
    
    private class TreeNode {
    	public int val;
    	public TreeNode left=null, right=null;
    	public TreeNode(int val) { this.val = val; }
    }
    
    public NumArray(int[] nums) {
    	N = nums.length;
    	if(N>0) {
        	this.nums = nums;
    		int[] sums = new int[N+1];
    		for(int i=0; i<N; i++)
    			sums[i+1] = sums[i]+nums[i];
    		root = new TreeNode(sums[N]);
    		constructSegmentTree(sums, 0, N-1, root);
    	}
    }
    private void constructSegmentTree(int[] sums, int lo, int hi, TreeNode root) {
    	if(lo==hi) return;
    	int mid = lo + ((hi-lo)>>1);
    	root.left = new TreeNode(sums[mid+1] - sums[lo]);
    	root.right = new TreeNode(sums[hi+1] - sums[mid+1]);
    	constructSegmentTree(sums, lo, mid, root.left);
    	constructSegmentTree(sums, mid+1, hi, root.right);
    }
    
    void update(int i, int val) {
    	updateSegmentTree(i, 0, N-1, val-nums[i], root);
    	nums[i] = val; // update array copy
    }
    private void updateSegmentTree(int i, int lo, int hi, int diff, TreeNode root) {
    	root.val += diff; 
    	if(lo==i && hi==i) return;
    	int mid = lo + ((hi-lo)>>1);
    	if(i>mid)   updateSegmentTree(i, mid+1, hi, diff, root.right);
    	else        updateSegmentTree(i, lo, mid, diff, root.left);
    }
    
    public int sumRange(int i, int j) {
    	if(j>j || i<0 || j>=N) return 0;
    	return range(i, j, 0, N-1, root);
    }
    private int range(int i, int j, int lo, int hi, TreeNode root) {
    	if(i==lo && j==hi) return root.val; // full cover
    	int mid = lo + ((hi-lo)>>1);
    	if(j<=mid)		return range(i, j, lo, mid, root.left); // cover left half
    	else if(i>mid) 	return range(i, j, mid+1, hi, root.right); // cover right half
    	else			return range(i, mid, lo, mid, root.left) + range(mid+1, j, mid+1, hi, root.right); // mixed cover
    }
    }
    

  • 0
    M

    thanks for sharing. fyi, there is no need to really build an actual tree structure.
    array-based tree (just like the heap) is sufficient.


  • 0
    L
    This post is deleted!

  • 0
    L
    This post is deleted!

Log in to reply
 

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