C++, Segment Tree,update and sum are both O(logn)
struct SegmentTreeNode {\n        int start, end, sum;\n        SegmentTreeNode* left;\n        SegmentTreeNode* right;\n        SegmentTreeNode(int a, int b):s
    struct SegmentTreeNode {\n        int start, end, sum;\n        SegmentTreeNode* left;\n        SegmentTreeNode* right;\n        SegmentTreeNode(int a, int b):start(a),end(b),sum(0),left(nullptr),right(nullptr){}\n    };\n    class NumArray {\n        SegmentTreeNode* root;\n    public:\n        NumArray(vector<int> &nums) {\n            int n = nums.size();\n            root = buildTree(nums,0,n-1);\n        }\n       \n        void update(int i, int val) {\n            modifyTree(i,val,root);\n        }\n    \n        int sumRange(int i, int j) {\n            return queryTree(i, j, root);\n        }\n        SegmentTreeNode* buildTree(vector<int> &nums, int start, int end) {\n            if(start > end) return nullptr;\n            SegmentTreeNode* root = new SegmentTreeNode(start,end);\n            if(start == end) {\n                root->sum = nums[start];\n                return root;\n            }\n            int mid = start + (end - start) / 2;\n            root->left = buildTree(nums,start,mid);\n            root->right = buildTree(nums,mid+1,end);\n            root->sum = root->left->sum + root->right->sum;\n            return root;\n        }\n        int modifyTree(int i, int val, SegmentTreeNode* root) {\n            if(root == nullptr) return 0;\n            int diff;\n            if(root->start == i && root->end == i) {\n                diff = val - root->sum;\n                root->sum = val;\n                return diff;\n            }\n            int mid = (root->start + root->end) / 2;\n            if(i > mid) {\n                diff = modifyTree(i,val,root->right);\n            } else {\n                diff = modifyTree(i,val,root->left);\n            }\n            root->sum = root->sum + diff;\n            return diff;\n        }\n        int queryTree(int i, int j, SegmentTreeNode* root) {\n            if(root == nullptr) return 0;\n            if(root->start == i && root->end == j) return root->sum;\n            int mid = (root->start + root->end) / 2;\n            if(i > mid) return queryTree(i,j,root->right);\n            if(j <= mid) return queryTree(i,j,root->left);\n            return queryTree(i,mid,root->left) + queryTree(mid+1,j,root->right);\n        }\n    };\n    \n    \n    // Your NumArray object will be instantiated and called as such:\n    // NumArray numArray(nums);\n    // numArray.sumRange(0, 1);\n    // numArray.update(1, 10);\n    // numArray.sumRange(1, 2);
[]