Segment Trees using Range Sum Query

Abhinay Gupta

·

Follow

Jul 3, 2021

--

Listen

Share

class NumArray {
    int nums[];
    int tree[];
    public NumArray(int[] nums) {
        this.nums=nums;
        this.tree = new int[nums.length*4];
        buildtree(1,0,nums.length-1);
    }
    
    public void update(int index, int val) {
        update(1,0,nums.length-1,index,val);
    }
    public void update(int node, int start, int end, int index, int val){
        if(start==end){
            nums[start]=val;
            tree[node]=val;
            return;
        }
        int mid= start + (end-start)/2;
        if(index<=mid){
            update(2*node,start,mid,index,val);
        }
        else{
            update(2*node+1,mid+1,end,index,val);
        }
        tree[node]=tree[2*node]+tree[2*node+1];
    }
    
    public int sumRange(int left, int right) {
        return sumRange(1,0,nums.length-1,left,right);
    }
    public int sumRange(int node, int start,int end,int left, int right){
        if(start> right|| end<left){
            return 0;
        }
        if(start>=left&& end<=right){
            return tree[node];
        }
        int mid= start+ (end-start)/2;
        int q1= sumRange(2*node,start,mid,left,right);
        int q2= sumRange(2*node+1,mid+1,end,left,right);
        return q1+q2;
        
    }
    public void buildtree(int node, int start, int end){
        if(start==end){
            tree[node]= nums[start];
            return;
        }
        int mid = start + (end-start)/2;
        buildtree(2*node,start,mid);
        buildtree(2*node+1,mid+1,end);
        tree[node]=tree[2*node]+tree[2*node+1];
        return;
    }   
}