✅ Clean Solution w/ Explanation | Segment Tree | Beats 100%
The 303. Range Sum Query - Immutable could be solved using simple prefix sum approach because the array was fixed. Here the array can be dynamically updated and
The [303. Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/) could be solved using simple prefix sum approach because the array was fixed. Here the array can be dynamically updated and thus using that approach, we can either make `update` or `sumRange` as `O(1)` and the other remains `O(N)`. This will lead to TLE. \n\nFor efficient updates and sum queries, there are many approaches like square root decomposition, binary-index tree and segment trees. Here, I will explain the segment tree approach\n\n---\n\n\u2714\uFE0F ***Solution - I (Segment Trees using Array)***\n\nRange Sum Query is a very common application for Segment Tree (referred henceforth as **ST**). ST consists of three functions, namely *`build()`*, *`update()`* and *`query()`* It allows us `O(logn)` update and query time and `O(N)` time to build the tree.\n\n<p align=center><img src=https://leetcode.com/problems/range-sum-query-mutable/Figures/307/307_segment_tree.png width=800 /> </p>\n<p align=center><em>Borrowing Segment Tree image from LC for illustration</em></p>\n\nEach node in ST for RSQ holds the sum for a range `[i...j]`. Its left and right child nodes consists sum of sub-ranges `[i...mid]` and `[mid+1,...j]` respectively and thus sum of these two child nodes would be equal to value stored in parent node. This structure is followed recursively throughout the tree. Let\'s look at each of the functions offered by segment tree -\n\n* **`build`**:\n\t* Here, we will recursively build the ST for the given array.\n\t* *`segTree[2*i]`* and *`segTree[2*i+1]`* will denote the left child and right child respectively for the node rooted at `i`th index in *`segTree`*. By definition, *`segTree[i] = segTree[2*i] + segTree[2*i + 1]`* \n\t* The build function will be recursively called to split the given array into two halves (**Divide**). When we reach a segment consisting of single array element, it can\'t be split further and so we stop here and assign the value to corresponding `segTree` index. Finally, the parent nodes value will be constructed from from their child value (**Merge**).\n\n* **`update`**:\n\t* The update operation is simple. We traverse down to the node holding the segment `[i]` and update each node on our way up.\n\t* If the index `i` to be updated is less than **mid** of the current segment, then recurse the left child, otherwise recurse the right child.\n\t* When we reach the node holding segment `[i]`, update it\'s value to `new_val`.\n\t* Finally, on our way back up,  we update all the parent node\'s value as sum of left + right child\n\n* **`query`**:\n\t* We are given a range `[L, R]` and we need to find the sum of this range.\n\t* Consider current node\'s segment to be `[l, r]`. There exists three cases:\n\t\t1. `[L, R] == [l, r]`- We can directly return current node\'s value in this case\n\t\t2. `[L, R]` falls in the left or right child\'s range (`[l, mid]` or `[mid + 1, r]`)- We need to recurse for left or right child.\n\t\t3. `[L, R]` falls partially in both left and right child\'s range- Here, we need to make two separate recursive calls to both the left and right child nodes and return their sum.\n\t* Instead of writing two separate cases for 2 and 3, I have combined it into single return statement in the below function.\n\n\n```\nclass NumArray {\n    inline static int n;\n    int* segTree;\npublic:\n    NumArray(vector<int>& nums) {\n        n = size(nums);\n        segTree = (int*)malloc(4 * n * sizeof(int));\n        build(nums, 1, 0, n - 1);\n    }\n    \n    void build(vector<int>& nums, int segIdx, int l, int r) {\n        if(l == r) segTree[segIdx] = nums[l];      // can\'t split further - assign corresponding index of segTree as nums[l]\n        else {\n            int mid = (l + r) / 2;                 // divide array into two halves (left and right child of current node of segment tree)\n            build(nums, 2*segIdx, l, mid);         // calculate result for left child\n            build(nums, 2*segIdx + 1, mid + 1, r); // calculate result for right child\n            segTree[segIdx] = segTree[2*segIdx] + segTree[2*segIdx + 1];  // merge result into parent - parent val = sum of left & right child\n        }\n    }\n    \n    void update(int index, int val, int segIdx = 1, int l = 0, int r = n - 1) {\n        if(l == r) segTree[segIdx] = val;           // update segment tree index corresponding to the array index to be updated\n        else {\n            int mid = (l + r) / 2;\n            if (index <= mid) update(index, val, 2*segIdx, l, mid);       // if node holding [nums[index]] segment lies in left child, recurse for it\n            else update(index, val, 2*segIdx + 1, mid + 1, r);            // other wise recurse the right child\n            segTree[segIdx] = segTree[2*segIdx] + segTree[2*segIdx + 1];  // child nodes got updated - so parent need to be updated again as sum of left + right child nodes\n        }\n    }\n    \n    int sumRange(int left, int right, int segIdx = 1, int l = 0, int r = n - 1) {\n        if(left > right) return 0;   \n        if(l == left && r == right) return segTree[segIdx];  // case - 1\n        int mid = (l + r) / 2;\n\t\t// case - 2 and 3\n\t\t// Here, we are picking min(right, mid) & max(left, mid+1) to ensure that [left, right] is always subrange of [l, r] for recursive call \n\t\t// otherwise base condition would never be reached in some cases\n        return  sumRange(left, min(right, mid), 2*segIdx, l, mid) + \n                sumRange(max(left, mid + 1), right, 2*segIdx + 1, mid + 1, r);\n    }\n};\n```\n\n***Time Complexity :*** \n* Initial construction: **`O(N)`**, where `N` is the number of elements in *`nums`*.\n* `update()`: **`O(logN)`** for each call\n* `sumRange()`: **`O(logN)`** for each call\n\n***Space Complexity :*** **`O(N)`**, required to maintain the *`segTree`* array\n\n---\n\n\u2714\uFE0F ***Solution - II (Segment Trees w/ actual Tree construction)***\n\nHere, I am using custom *`SegmentTree`* class to actually construct a segment tree rather than simulating using the arrays. Most of the functions remains the same with only few changes in implementation of them.\n\n```\nclass SegmentTree {\n    SegmentTree *left, *right;\n    int L, R, val;\npublic:\n    SegmentTree(vector<int>& nums, int l, int r): L(l), R(r), left(NULL), right(NULL) {\n        build(nums);\n    }\n    void build(vector<int>& nums) {\n        if(L == R) val = nums[L];\n        else {\n            int mid = (L + R) / 2;\n            left = new SegmentTree(nums, L, mid);\n            right = new SegmentTree(nums, mid + 1, R);\n            val = left -> val + right -> val;\n        }\n    }\n    void update(int i, int new_val) {\n        if(L == R) val = new_val;\n        else {\n            int mid = (L + R) / 2;\n            if(i <= mid) left -> update(i, new_val);\n            else right -> update(i, new_val);\n            val = left -> val + right -> val;\n        }\n    }\n    int sum(int l, int r) {\n        if(l > r) return 0;\n        if(l == L && r == R) return val;\n        int mid = (L + R) / 2;\n        return left -> sum(l, min(mid, r)) + right -> sum(max(l, mid + 1), r);\n    }\n};\nclass NumArray {\n    SegmentTree *tree;\npublic:\n    NumArray(vector<int>& nums) {\n        tree = new SegmentTree(nums, 0, size(nums) - 1);\n    }\n    \n    void update(int index, int val) {\n        tree -> update(index, val);\n    }\n    \n    int sumRange(int left, int right) {\n        return tree -> sum(left, right);\n    }\n};\n```\n\n***Time and Space Complexity :*** same as above\n\n---\n\n*Best Runtime - (First Approach)*\n\n<table><tr><td><img src =https://assets.leetcode.com/users/images/a3a82ec2-6dc7-439c-ba1a-6d48ee4f9feb_1624025865.1465302.png  /></td></tr></table>\n\n\n\n---\n---\n\n\uD83D\uDCBB\uD83D\uDC31\u200D\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, please do comment below \uD83D\uDC47 \n\n---\n---
['C']