Range Sum Query - Mutable | Segmented Tree | C++ | Easy to  understand
Approach : Naive  (TLE)\n\nIterate over left to right in range and find sum  but it will result in TLE .\n\nclass NumArray {\nprivate:\n    vector<int> arr;\npu
**Approach : Naive**  (TLE)\n\nIterate over left to right in range and find sum  but it will result in TLE .\n```\nclass NumArray {\nprivate:\n    vector<int> arr;\npublic:\n    NumArray(vector<int>& nums) {\n        arr = nums;\n     }\n    \n    void update(int index, int val) {\n        arr[index] = val;\n    }\n    \n    int sumRange(int left, int right) {\n        int sum = 0;\n        for(int i = left;i<=right; i++)\n            sum += arr[i];\n        return sum;\n    }\n};\n```\n**Time complexity :**  O(n) - range sum query, O(1) - update query\n\n**Space complexity :** O(1)O(1).\n\n**Better Approach : Segment Tree**\nTo find  Range Sum in O(logn) we use segemnt tree \n```\nclass NumArray {\npublic:\n    \n    int n;\n    int stree[120004];\n    \n    // Build int segmented Tree stree[0] contains total sum \n    // stree[1] conatin sum of range 0 to mid and stree[1] conatian sum of range mid+1 to n\n    void build(int i,int s,int e,vector<int>&nums)\n    {\n        if(s == e)\n        {\n            stree[i] = nums[e];\n            return ;\n        }\n        \n        int mid = s+(e-s)/2;\n        build(2*i+1,s,mid,nums);\n        build(2*i+2,mid+1,e,nums);\n        \n        stree[i] = stree[2*i+1] + stree[2*i+2];\n    }\n    \n    // Updating value at particular index and updating stree accordingly\n    void treeupdate(int i ,int st, int end,int ind, int val)\n    {\n        if(st == end)\n        {\n            stree[i] = val;\n            return;\n        }\n        int mid = st+(end-st)/2;\n        if(ind<=mid)\n            treeupdate(2*i+1,st,mid,ind,val);\n        else\n            treeupdate(2*i+2,mid+1,end,ind,val);\n        \n        stree[i] = stree[i*2+1]+stree[i*2+2];\n    }\n    \n    // Return sum of range left to Right \n    int rangeSum(int i,int st,int end,int left,int right)\n    {\n        if(left <= st && right>=end)\n            return stree[i];\n        \n        if(left>end || right<st)\n            return 0;\n        \n        int mid  = st + (end-st)/2;\n        return rangeSum(2*i+1,st,mid,left,right) + rangeSum(2*i+2,mid+1,end,left,right);\n    }\n    \n    \n    NumArray(vector<int>& nums) {\n        n = nums.size();\n        build(0,0,n-1,nums);\n    }\n    \n    void update(int index, int val) {\n        treeupdate(0,0,n-1,index,val);\n    }\n    \n    int sumRange(int left, int right) {\n        int sum = rangeSum(0,0,n-1,left,right);\n        return sum;\n    }\n};\n```\n\nTime Complexity: \n\nTime Complexity for tree construction is O(n). There are total 2n-1 nodes, and value of every node is calculated only once in tree construction.\nTime complexity to query is O(Logn). To query a sum, we process at most four nodes at every level and number of levels is O(Logn). \nThe time complexity of update is also O(Logn). To update a leaf value, we process one node at every level and number of levels is O(Logn).\n\nPlease Upvaote if you find this helpful
['Tree', 'C']