307. Range Sum Query - Mutable 线段树


线段树的基本操作啦,直接代码:
class MyNode{
public:
    int start, end, sum;
    MyNode *left, *right;
    MyNode(){
        start = end = sum = 0;
        left = right = NULL;
    }
    
    int Mid(){
        return (start + end) / 2;
    }
};

class NumArray {
public:
    NumArray(vector<int> nums) {
        if (nums.size() == 0){
            return;
        }
        t = nums;
        root = build(root, nums, 0, nums.size() - 1);
    }
    
    MyNode* build(MyNode *root, vector<int> &nums, int start, int end){
        if (start <= end){
            root = new MyNode();
            root->sum = nums[start];
            root->start = start;
            root->end = end;
        }
        
        if(start != end){
            root->left =  build(root, nums, start, root->Mid());
            root->right = build(root, nums, root->Mid() + 1, end);
            root->sum = root->left->sum + root->right->sum;
        }
        return root;
    }
    
    
    void update(int i, int val) {
        int c = val - t[i];
        t[i] = val;
        
        MyNode *node = root;
        while (1){
            if (node->start == i && node->end == i){
                node->sum = val;
                break;
            }
            node->sum = node->sum + c;
            if (i <= node->Mid()){
                node = node->left;
            }else{
                node = node->right;
            }
        }
        
    }

    int Query(MyNode *root, int start, int end){
        if (root->start == start && root->end == end){
            return root->sum;
        }
        
        if (end <= root->Mid()){
            return Query(root->left, start, end);
        }else if (start >= root->Mid() + 1){
            return Query(root->right, start, end);
        }else{
            return Query(root->left, start, root->Mid()) + Query(root->right, root->Mid() + 1, end);
        }
    }
    
    int sumRange(int i, int j) {
        if (i == j) return t[i];
        return Query(root, i, j);
    }

private:
    MyNode *root;
    vector<int> t;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

0 个评论

要回复文章请先登录注册

返回顶部