✅ Range Sum Query - Mutable | BIT + Segment Trees | Simple Solution
\u2714\uFE0F Solution: 1) Binary Indexed Tree:\n Time Complexity: \n1. Tree Construction: O(nLog(n))\n2. Update : O(Log(n))\n3. Query : O(Log(n))\n\n Space Comp
***\u2714\uFE0F Solution: 1) Binary Indexed Tree:***\n* **Time Complexity:** \n1. ***Tree Construction: O(nLog(n))***\n2. ***Update : O(Log(n))***\n3. ***Query : O(Log(n))***\n\n* **Space Complexity:** ***O(n)***\nwhere **n -** number of elements in array .\n```\nclass NumArray {\nprivate:\n    vector<int> bit;\n    int n;\n    int lsb(int idx)\n    {\n        return idx & (-idx);\n    }\n\n    void bitUpdate(int node_index, int val)\n    {\n        while(node_index<=n)\n        {\n            bit[node_index]+=val;\n            node_index += lsb(node_index);\n        }\n    }\n\n    void createBit(vector<int> &nums)\n    {\n        for(int i=0;i<n;i++)\n        {\n            bitUpdate(i+1,nums[i]);\n        }\n    }\n\n    int sumQuery(int idx)\n    {\n        int sum=0;\n        while(idx>=1)\n        {\n            sum+=bit[idx];\n            idx-=lsb(idx);\n        }\n        return sum;\n    }\n\npublic:\n    vector<int> nums;\n    NumArray(vector<int>& nums) \n    {\n        this->nums = nums;\n        bit.clear();\n        n=nums.size();\n        bit.resize(n+1);\n        createBit(nums);   \n    }\n    \n    void update(int index, int val) \n    {\n        int diff = val - nums[index];\n        nums[index] = val;\n        bitUpdate(index+1,diff);\n    }\n    \n    int sumRange(int left, int right) \n    {\n        return sumQuery(right+1)-sumQuery(left);\n    }\n};\n\n/**\n * Your NumArray object will be instantiated and called as such:\n * NumArray* obj = new NumArray(nums);\n * obj->update(index,val);\n * int param_2 = obj->sumRange(left,right);\n */\n```\n\n***\u2714\uFE0F Solution: 2) Segment Trees*:**\n* **Time Complexity:** \n1. ***Tree Construction: O(n)***\n2. ***Update : O(Log(n))***\n3. ***Query : O(Log(n))***\n\n* **Space Complexity:** ***O(n)***\nwhere **n -** number of elements in array .\n\n```\nclass NumArray {\nprivate:\n    vector<int> seg;\n    vector<int> nums;\n    int n;\nprotected:\n    void buildSegmentTree(int st,int en,int idx=0)\n    {\n        if(st==en)\n        {\n            seg[idx] = nums[st];\n            return;\n        }\n        int mid = st+(en-st)/2;\n        int lc = 2*idx+1;\n        int rc = 2*idx+2;\n        buildSegmentTree(st,mid,lc);\n        buildSegmentTree(mid+1,en,rc);\n        seg[idx] = seg[lc] + seg[rc];\n    }\n    \n    void updateSegmentTree(int st,int en,int pos,int val,int idx=0)\n    {\n        if(st>en or pos<st or pos>en)\n            return;\n        if(st==en)\n        {\n            seg[idx] = val;\n            return;\n        }\n        int mid = st+(en-st)/2;\n        int lc = 2*idx+1;\n        int rc = 2*idx+2;\n        if(pos<=mid)\n            updateSegmentTree(st,mid,pos,val,lc);\n        else\n            updateSegmentTree(mid+1,en,pos,val,rc);\n        seg[idx] = seg[lc] + seg[rc];\n    }\n    \n    int sumQuery(int qs,int qe,int st,int en,int idx=0)\n    {\n        if(qs>en or qe<st)\n            return 0;\n        if(st>=qs and en<=qe)\n            return seg[idx];\n        int mid = st+(en-st)/2;\n        int lc = 2*idx+1;\n        int rc = 2*idx+2;\n        return sumQuery(qs,qe,st,mid,lc) + sumQuery(qs,qe,mid+1,en,rc);\n    }\n    \npublic:\n    NumArray(vector<int>& nums) {\n        this->nums = nums;\n        n = (int)nums.size();\n        seg.resize(4*n);\n        buildSegmentTree(0,n-1);\n    }\n    \n    void update(int index, int val) \n    {\n        updateSegmentTree(0,n-1,index,val);\n    }\n    \n    int sumRange(int left, int right) \n    {\n        return sumQuery(left,right,0,n-1);\n    }\n};\n\n/**\n * Your NumArray object will be instantiated and called as such:\n * NumArray* obj = new NumArray(nums);\n * obj->update(index,val);\n * int param_2 = obj->sumRange(left,right);\n */\n```
['C']