CPP || SEGMENT TREE || EASY ✅|| EXPLAINED 🤗
Approach\nThis question is a variation of Range Sum Query - Immutable. But the difference is that now besides queries for the sum of a range, there may also be 
# Approach\nThis question is a variation of [Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/). But the difference is that now besides queries for the sum of a range, there may also be queries to update the value at a certain index. A simple updation can be done in O(1) but we can\'t directly use a prefix sum array to compute the sum as now the values aren\'t constant but changing with time, hence during every updation we need to update the prefix sum array as well, **which will take O(n) time**. \n\nWe can improve this time complexity by using a data structure called **Segment Tree**. Segment tree reduces the time complexity of updation and querying a range to **O(logn) each** by representing the array in the form of a tree, where each node represents a certain range of the array and carries the answer of that range. The root node represents the full range of the array whereas the leaf nodes represent individual elements. For solving this question, any node that represents a range `l` to `r` will carry the sum of the range `l` to `r`.\n\nFor further information, [refer this article](https://cp-algorithms.com/data_structures/segment_tree.html).\n\n# Code\n```cpp\nclass NumArray {\n    int n;\n    vector<int> segTree;\n    \n    void buildTree(vector<int> &arr,int l,int r,int ind)\n    {\n\t\t// if we are at the leaf, we simply set the value at the given index\n        if(l==r)\n        {\n            segTree[ind] = arr[l];\n            return;\n        }\n        int mid = l + (r-l)/2;\n\t\t// we build the left subtree and the right subtree\n        buildTree(arr,l,mid,2*ind+1);\n        buildTree(arr,mid+1,r,2*ind+2);\n\t\t// value at this node will be equal to the sum of the value at its left and its right\n        segTree[ind] = segTree[2*ind+1] + segTree[2*ind+2];\n    }\n    \n    void update(int l,int r,int ind,int &i,int &x)\n    {\n\t\t// we have reached the leaf node so we update the value at the leaf\n        if(l==r)\n        {\n            segTree[ind] = x;\n            return;\n        }\n        int mid = l + (r-l)/2;\n\t\t// if the destination index is in the left subtree we update the left subtree else we update the right\n        if(i<=mid){\n            update(l,mid,2*ind+1,i,x);\n        }\n        else{\n           update(mid+1,r,2*ind+2,i,x); \n        }\n\t\t// update the current node after carrying out updations in its children\n        segTree[ind] = segTree[2*ind+1] + segTree[2*ind+2];\n    }\n    \n    int query(int l,int r,int ind,int &s,int &e)\n    {\n\t\t// if the current range is completely inside the queried range, we return the complete ans\n        if(l>=s && r<=e) return segTree[ind];\n\t\t// if the current range is completely outside, we return 0\n        if(l>e || r<s) return 0;\n        int mid = l + (r-l)/2;\n\t\t// if there is a partial overlap, we get the answers from left and right subtrees and return the sum\n        return query(l,mid,2*ind+1,s,e) + query(mid+1,r,2*ind+2,s,e);\n    }\n    \npublic:\n    NumArray(vector<int>& nums) {\n        n = nums.size();\n        segTree = vector<int>(4*n);\n        buildTree(nums,0,n-1,0);\n    }\n    \n    void update(int index, int val) {\n        update(0,n-1,0,index,val);\n    }\n    \n    int sumRange(int left, int right) {\n        return query(0,n-1,0,left,right);\n    }\n};\n```\n![](https://c.tenor.com/K98-kjOa1VYAAAAC/crazy-gudako.gif)
['Tree', 'C', 'C++']