Description

Submission

class NumArray {
    struct SegTreeNode {
        int start;
        int end;
        int info;
        SegTreeNode* left;
        SegTreeNode* right;

        SegTreeNode(int start, int end, int info, SegTreeNode* left, SegTreeNode* right)
            :
            start(start),
            end(end),
            info(info),
            left(left),
            right(right)
            {}

    };

    SegTreeNode* Init(int a, int b)  // init for range [a,b]
    {                        
        if(a == b) {
            return new SegTreeNode(a, b, nums[a], nullptr, nullptr);
        }
        int mid = (a + b) / 2;
        SegTreeNode* left = Init(a, mid);
        SegTreeNode* right = Init(mid + 1, b);
        return new SegTreeNode(a, b, left->info+right->info, left, right);
    }

    void UpdateSingle(SegTreeNode* node, int idx, int val) {
        if(idx < node->start || idx > node->end) return;

        if(node->start == node->end) {
            node->info = val;
            return;
        }
        UpdateSingle(node->left, idx, val);
        UpdateSingle(node->right, idx, val);
        node->info = node->left->info + node->right->info;
    }

    int QueryRange(SegTreeNode* node, int a, int b) {
        if(node->end < a || node->start > b) return 0;
        if(a <= node->start && b >= node->end) return node->info;
        return QueryRange(node->left, a, b) + QueryRange(node->right, a, b);
    }
    
    int n;
    vector<int> nums;
    SegTreeNode* root;
public:
    NumArray(vector<int>& nums) {
        n = nums.size();
        this->nums = nums;
        root = Init(0, n-1);
    }
    
    void update(int index, int val) {
        UpdateSingle(root, index, val);
    }
    
    int sumRange(int left, int right) {
        return QueryRange(root, left, right);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */