# *Java* standard solution using segment tree

• 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) {
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
}
}
``````

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

• This post is deleted!

• This post is deleted!

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