10ms Java Segment Tree solution


  • 0
    M
    public class NumArray {
        int[] seg;
        
        public NumArray(int[] nums) {
            seg = new int[nums.length*2];
            for(int i = seg.length/2; i < seg.length; i++) {
                seg[i] = nums[i - seg.length/2];
            }
            
            for(int i = seg.length/2-1; i > 0; i--) {
                seg[i] = seg[2*i] + seg[2*i+1];
            }
        }
    
        void update(int i, int val) {
            seg[i + seg.length/2] = val;
            int par = (i + seg.length/2)/2;
            while(par > 0) {
                seg[par] = seg[2*par] + seg[2*par+1];
                par /= 2;
            }
        }
    
        public int sumRange(int i, int j) {
            int sum = 0;
            int left = i + seg.length/2, right = j + seg.length/2 + 1;
            while(left < right) {
                if(left % 2 == 1) {
                    sum += seg[left];
                    left++;
                }
                if(right % 2 == 1) {
                    right--;
                    sum += seg[right];
                }
                left /= 2;
                right /= 2;
             }
            return sum;
        }
    }
    

Log in to reply
 

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