Segment Tree, Binary Indexed Tree and the simple way using buffer to accelerate in C++, all quite efficient
Segment Tree\n\n    struct SegmentTreeNode \n    {\n        int start, end, sum;\n        SegmentTreeNode left;\n        SegmentTreeNode right;\n        Segment
**Segment Tree**\n\n    struct SegmentTreeNode \n    {\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    \n    class NumArray \n    {\n    private:\n        SegmentTreeNode* root;\n        SegmentTreeNode* buildTree(vector<int> &nums, int start, int end) \n        {\n            if(start > end) return nullptr;\n            SegmentTreeNode* root = new SegmentTreeNode(start,end);\n            if(start == end) \n            {\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    \n        int modifyTree(int i, int val, SegmentTreeNode* root) \n        {\n            if(root == nullptr) return 0;\n            int diff;\n            if(root->start == i && root->end == i) \n            {\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) diff = modifyTree(i,val,root->right);\n            else diff = modifyTree(i,val,root->left);\n            root->sum += diff;\n            return diff;\n        }\n    \n        int queryTree(int i, int j, SegmentTreeNode* root) \n        {\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    public:\n        NumArray(vector<int> &nums) \n        {\n            root = buildTree(nums,0,nums.size()-1);\n        }\n    \n        void update(int i, int val) \n        {\n            modifyTree(i,val,root);\n        }\n    \n        //AC - 56ms - Segment Tree;\n        int sumRange(int i, int j) \n        {\n            return queryTree(i, j, root);\n        }\n    };\n    \n----------\n\n**Fenwick Tree or Binary Indexed Tree**\n    \n    class NumArray {\n    private:\n        int* BIT;\n        int size;\n        int sum(int x)\n        {\n            int ret = 0;\n            while(x)\n            {\n                ret += BIT[x];\n                x-= (x&-x);\n            }\n            return ret;\n        }\n    public:\n        NumArray(vector<int> &nums) \n        {\n            size = nums.size();\n            BIT = (int*)malloc(sizeof(int)*(size+1));\n            memset(BIT,0,sizeof(int)*(size+1));\n            for(int i = 0; i < size; i++)\n            update(i,nums[i]);\n        }\n    \n        void update(int i, int val) \n        {\n            i++;\n            val -= sum(i) - sum(i-1);\n            while(i <= size)\n            {\n                BIT[i] += val;\n                i+= (i&-i);\n            }\n        }\n        \n        //AC - 52ms - Fenwick Tree or Binary Indexed Tree;\n        int sumRange(int i, int j) \n        {\n            return sum(j+1) - sum(i);\n        }\n    };\n    \n    \n----------\n\n**R\xe9guler method using buffer to accelerate**\n    \n    class NumArray {\n    private:    \n        vector<long> sums;\n        vector<int> nums;\n        vector<pair<int,int>> buffer;\n    public:\n        NumArray(vector<int> &nums) : sums(nums.size()+1, 0), nums(nums)\n        {\n            partial_sum(nums.begin(), nums.end(), sums.begin() + 1);\n        }\n        void update(int i, int val) \n        {\n            buffer.emplace_back(i,  val - nums[i]); //buffer.push_back(make_pair(i, val-nums[i]));\n            nums[i] = val;        \n            if(buffer.size() > 300) \n            {\n                partial_sum(nums.begin(), nums.end(), sums.begin() + 1);\n                buffer.clear();\n            }\n        }\n    \n        //AC - 80ms - just using a buffer, dramatically reduce the time cost;\n        int sumRange(int i, int j)\n        {\n            long result =  sums[j+1] - sums[i];\n            for(const auto& p : buffer)\n                if(p.first <=j && p.first >= i) result += p.second;\n            return result;\n        }\n    };
['Binary Tree', 'C++']