# Time complexity of Segment Tree?

• For the code below, I think
Tree construction is O(N), because there are ~2*N nodes in the tree and each node needs constant time.
Update is O(logN), because we only need to follow a single path from the root to a leaf.
For sumRange(), is the complexity also O(logN)? I'm a bit uncertain about this, but from the test cases I have, I think we need to follow at most 2 paths from the root to the leaves in order to get the sum.

``````public class NumArray {
private TreeNode root;
private int[] nums;

//Complexity O(N)
public NumArray(int[] nums) {
if(nums==null||nums.length==0)  return;
this.nums=nums;
root=makeTree(nums, 0, nums.length-1);
}

private TreeNode makeTree(int[] nums, int lo, int hi){
if(lo==hi){
TreeNode current=new TreeNode(lo, hi);
current.val=nums[lo];
return current;
}
TreeNode current=new TreeNode(lo, hi);
int mid=lo+(hi-lo)/2;
current.left=makeTree(nums, lo, mid);
current.right=makeTree(nums, mid+1, hi);
current.val=current.left.val+current.right.val;
return current;
}

//Complexity O(logN)
void update(int i, int val) {
if(root==null)  return;
int diff=val-nums[i];
nums[i]=val;
update(root, diff, i);
}

private void update(TreeNode root, int diff, int index){
if(root.min==root.max){
root.val+=diff;
return;
}
int mid=root.min+(root.max-root.min)/2;
if(index<=mid)
update(root.left, diff, index);
else
update(root.right, diff, index);
root.val=root.left.val+root.right.val;
}

//Complexity O(logN)
public int sumRange(int i, int j) {
if(root==null)  return 0;
return sumRange(root, i, j);
}

private int sumRange(TreeNode root, int i, int j){
if(root.min==i&&root.max==j)
return root.val;
int mid=root.min+(root.max-root.min)/2;
if(j<=mid)
return sumRange(root.left, i, j);
else if(i>mid)
return sumRange(root.right, i, j);
else
return sumRange(root.left, i, mid)+sumRange(root.right, mid+1, j);
}

//Segment tree node
private class TreeNode {
private TreeNode left;
private TreeNode right;
private int min;
private int max;
private int val;
public TreeNode(int min, int max){
this.min=min;
this.max=max;
}
}
}``````

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