subject

Topic linking

Give you an array nums , Please complete two types of queries .

1. One type of query requirements to update Array nums The value of the subscript
2. Another type of query requires the return of an array nums Middle index left And index right Between （ contain ） Of nums Elemental and , among left <= right

Realization NumArray class ：

• NumArray(int[] nums) Use an array of integers nums Initialize object
• void update(int index, int val) take nums[index] Value to update by val
• int sumRange(int left, int right) Returns an array of nums Middle index left And index right Between （ contain ） Of nums Elemental and （ namely ,nums[left] + nums[left + 1], …, nums[right]）

Example 1：

 Input ：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
 Output ：
[null, 9, null, 8]

 explain ：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); //  return  1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); //  return  1 + 2 + 5 = 8

Problem solving

Method 1 ： Line segment tree

struct Node{
    
    Node* left;
    Node* right;
    int val;
    int add;
};

class NumArray {
    
public:
    Node* root=new Node();
    int N;
    NumArray(vector<int>& nums) {
    
        N=nums.size()-1;
        for(int i=0;i<=N;i++){
    
            update(root,0,N,i,i,nums[i]);
        }
    }
    
    void update(int index, int val) {
    
        update(root,0,N,index,index,val);
    }
    
    int sumRange(int left, int right) {
    
        return query(root,0,N,left,right);
    }


private:
    void update(Node* node,int start,int end,int l,int r,int val){
    
        if(l<=start&&end<=r){
    
            node->val=(end-start+1)*val;
            node->add=val;
            return;
        }
        int mid=(start+end)>>1;
        pushDown(node,mid-start+1,end-mid);
        if(l<=mid) update(node->left,start,mid,l,r,val);
        if(r>mid) update(node->right,mid+1,end,l,r,val);
        pushUp(node);
    }
    int query(Node* node,int start,int end,int l,int r){
    
        if(l<=start&&end<=r) return node->val;
        int mid=(start+end)>>1;
        int res=0;
        pushDown(node,mid-start+1,end-mid);
        if(l<=mid) res+=query(node->left,start,mid,l,r);
        if(r>mid) res+=query(node->right,mid+1,end,l,r);
        return res;
    }
  
    void pushUp(Node* node){
    
        node->val=node->left->val+node->right->val;
    }
    void pushDown(Node* node,int leftNum,int rightNum){
    
        if(node->left==nullptr) node->left=new Node();
        if(node->right==nullptr) node->right=new Node();
        if(node->add==0) return;
        node->left->val=node->add*leftNum;
        node->right->val=node->add*rightNum;
        node->left->add=node->add;
        node->right->add=node->add;
        node->add=0;
    }
};