LeetCode [307] Range Sum Query - Mutable

 307. Range Sum Query - Mutable

Medium

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

 

Constraints:

• The array is only modifiable by the update function.
• You may assume the number of calls to update and sumRange function is distributed evenly.
• 0 <= i <= j <= nums.length - 1

//C++
//C++: 1720ms
class STNode{
public:
    int sum;
    int ss;
    int se;
    STNode *left;
    STNode *right;
    STNode(vector<int> &nums, int s, int e){
        sum = 0;
        ss = s;
        se = e;
        left = NULL;
        right = NULL;
        if(s==e){
            sum = nums[s];
        }else if(s<e){
            int m = (s+e)/2;
            left = new STNode(nums, s, m);
            right = new STNode(nums, m+1, e);
            sum = left->sum + right->sum;
        }
    }
};

class NumArray {
    STNode * root;
    void updateST(STNode* root, int i, int val){
        if(!root || i<root->ss || i>root->se){
            return;
        }if(i==root->ss && i==root->se){
            root->sum = val;
        }else{
            updateST(root->left, i, val);
            updateST(root->right, i, val);
            root->sum = (root->left?root->left->sum:0) + (root->right?root->right->sum:0);
        }
    }
    int sumRange(STNode* root, int i, int j){
        if(!root) return 0;
        else if(i>root->se || j<root->ss) return 0;
        else if(i<=root->ss && j>=root->se) return root->sum;
        else return sumRange(root->left, i, j)+sumRange(root->right, i, j);
    }
public:
    NumArray(vector<int> &nums) {
        int n = nums.size();
        root = new STNode(nums, 0, n-1);
    }

    void update(int i, int val) {
        updateST(root, i, val);
    }

    int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }
};

//Java
class SGTree{
    int sum;
    int start;
    int end;
    SGTree left;
    SGTree right;
    SGTree(int[] nums, int l, int r){
        start = l;
        end = r;
        if(start==end){
            sum = nums[l];
        }else{
            int m = (l+r)/2;
            left = new SGTree(nums, l, m);
            right = new SGTree(nums, m+1, r);
            sum = left.sum + right.sum;
        }
    }
};

public class NumArray { 
    SGTree sgTree;
    public NumArray(int[] nums) {
        if(nums.length>0)
            sgTree = new SGTree(nums, 0, nums.length-1);
    }

    void updateST(SGTree node, int i, int v){
        if(node==null || i<node.start || i>node.end) return;
        if(i==node.start && i==node.end) node.sum = v;
        else{
            updateST(node.left, i, v);
            updateST(node.right, i, v);
            node.sum = node.left.sum + node.right.sum;
        }
    }

    int sumST(SGTree node, int i, int j){
        if(node==null || j<node.start || i>node.end) return 0;
        if(i<=node.start && node.end<=j) return node.sum;
        return sumST(node.left, i, j)+sumST(node.right, i, j);
    }
    
    public void update(int i, int val) {
        updateST(sgTree, i, val);
    }
    
    public int sumRange(int i, int j) {
        return sumST(sgTree, i, j);
    }
}

/**
 * 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);
 */

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

class NumArray { int n; int[] bit; int[] arr; int getNext(int i){ return i+(i&(-i)); } int getParent(int i){ return i-(i&(-i)); } public NumArray(int[] nums) { n = nums.length; bit = new int[n+1]; arr = new int[n]; for(int i=0; i<n; ++i){ update(i, nums[i]); } } public void update(int index, int val) { int diff = val-arr[index]; arr[index] = val; int p = index+1; while(p<=n){ bit[p] += diff; p = getNext(p); } } int getPreSum(int index){ int sum = 0; int p = index+1; while(p>0){ sum += bit[p]; p = getParent(p); } return sum; } public int sumRange(int left, int right) { return getPreSum(right)-getPreSum(left-1); } } /** * 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); */