# My java solution using segment tree

• 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;
}

• @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.

• @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;
}
``````

• @StefanPochmann Oh I see! Thank you !

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