Time complexity of Segment Tree?


  • 0
    S

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

Log in to reply
 

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