C++ | Segment Tree | Explained
\n/\n\nHarshit Gupta | 19th May, 2021\n---------------------------------\n\nC++ program for \n\n    Given an integer array nums, handle multiple queries of the 
\n/*\n\nHarshit Gupta | 19th May, 2021\n---------------------------------\n\nC++ program for \n\n    Given an integer array nums, handle multiple queries of the following types:\n    - Update the value of an element in nums.\n    - Calculate the SUM of the elements of nums between indices left and right inclusive where left <= right.\n\n    Example 1:\n    Input\n    ["NumArray", "sumRange", "update", "sumRange"]\n    [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]\n    Output\n    [null, 9, null, 8]\n\nhttps://leetcode.com/problems/range-sum-query-mutable/\n\n------\n\nSolution: \n    1. One way to solve would simply be by a for loop and it will do the SUM in O(n) time and UPDATE in O(1) time.\n    2. Another way would be solve using Segment Trees which would do the SUM in O(logn) and UPDATE in O(logn) time. Howeever, weee will have to build a Segment Tree first which will require O(n) time.\n\n    https://leetcode.com/problems/range-sum-query-mutable/solution/\n\n\n    #SegmentTree #Segment #Trees #MergeSort\n\nTime Complexity: Sum: O(logn), Update: O(logn)\nSpace Complexity: O(n) for the segment tree\n---\n  NOTE: \n\n*/\n```\n\n// nums:[-1, 4, 2, 0]\n\n// Segment Tree for the Above Array:\n\n//      5                   [0,3]\n//    /   \\\n//    3    2          [0,1]      [2,3]\n//   / \\   /\\\n// -1  4  2  0    [0,0] [1,1] [2,2] [3,3]\n\n// Segment Tree Represented as: [5, 3, 2, -1, 4, 2, 0]\n// Each node at \'k\' can access their child at 2k+1, 2k+2\n// Each node can access its parent at (k-1)/2\n```\n```\nclass NumArray {\npublic:\n    // Check the constructor for the initialization of these variables.\n    vector<int> seg; // Segment Tree to be stored in a vector.\n    int n; // Length of the segment tree vector. \n    \n\n    // Function to build the Segment Tree\n    // This function will fill up the child values first\n    // (left == right) will satisfy for the leaf values and they will be updated in segment tree\n    // seg[pos]=seg[2*pos+1]+ seg[2*pos+2]; -> This will help populate all other intermediate nodes\n    // as well as the root node with the "sum" of their child nodes.\n    // Finally we have a segment tree which has all \'nodes\' with sum values of their child.\n    void buildTree(vector<int>& nums, int pos, int left, int right){\n        if (left == right){\n            seg[pos] = nums[left]; \n            return;\n        }\n        int mid = (left+right)/2;\n        buildTree(nums, 2*pos+1, left, mid);\n        buildTree(nums, 2*pos+2, mid+1, right);\n        seg[pos]=seg[2*pos+1]+ seg[2*pos+2];\n    }\n\n    // Function to update a node in the segment tree\n    // When a node is updated, then the change in the node value has to be propagated to the root\n    // left, right -> represents the range of the node of segment tree. (Ex: [0, n-1] -> root)\n    // pos       -> represents "position" in the segment tree data structure (Ex: 0 -> root)\n    // Using left, right and pos -> we have all the information on the segment tree\n    // Node at \'pos\' in segment tree will have children at 2pos+1(left) and 2pos+2(right)\n\n    // If index is less than left or more than right, then it is out of bound \n    //      for this node\'s range so we ignore it and return (This makes the algo O(logn))\n    // If left==right==index, then we found the index, \n    //      update the value of the segment tree node & return\n    // Otherwise, we need to find the index and we do this by checking child nodes (2pos+1, 2pos+2)\n    //      update the segment tree pos with the updated child values\' sum.\n    //      This would help propagate the updated value of the chid indexes to the parent (through recursion)\n    void updateUtil(int pos, int left, int right, int index, int val) {\n        // no overlap\n        if(index <left || index >right) return;\n        \n        // total overlap\n        if(left==right){\n            if(left==index)\n                seg[pos]=val;\n            return;\n        }\n\n        // partial overlap\n        int mid=(left+right)/2;\n        updateUtil(2*pos+1,left,mid,index,val); // left child\n        updateUtil(2*pos+2,mid+1,right,index,val); // right child\n        seg[pos]=seg[2*pos+1]+seg[2*pos+2];\n    }\n\n    // Function to get the sum from the range [qlow, qhigh]\n    // low, high -> represents the range of the node of segment tree. (Ex: [0, n-1] -> root)\n    // pos       -> represents "position" in the segment tree data structure (Ex: 0 -> root)\n    // Using low, high and pos -> we have all the information on the segment tree\n    // Node at \'pos\' in segment tree will have children at 2pos+1(left) and 2pos+2(right)\n    \n    // While searching for the range, there will be three cases: (Ex: arr: [-1, 4, 2, 0])\n    //  - Total Overlap:    Return the value. (Ex: qlow, qhigh: 0,3 and low, high: 1,2)\n    //  - No Overlap:       Return 0. (Ex: qlow, qhigh: 0,1 and low, high: 2,3)\n    //  - Partial Overlap:  Search for it in both the child nodes and their ranges.\n    //                      (Ex: Searching for 1,2 and node range is 0,1)\n    int rangeUtil(int qlow, int qhigh, int low, int high, int pos){\n        if (qlow <= low && qhigh>= high){ // total overlap\n            return seg[pos];\n        }\n        if (qlow > high || qhigh < low) { // no overlap\n            return 0;\n        }\n        // partial overlap\n        int mid = low+(high-low)/2;\n        return (rangeUtil(qlow, qhigh, low, mid, 2*pos+1) + rangeUtil(qlow, qhigh, mid+1, high, 2*pos+2));\n    }\n    \n    // Constructor for initializing the variables.\n    NumArray(vector<int>& nums) {\n        if(nums.size() > 0){\n            n = nums.size();\n            seg.resize(4*n,0);  // Maximum size of a segment tree for an array of size n is 4n\n            buildTree(nums, 0, 0, n-1); // Build the segment tree\n            // Print Segment Tree\n            // for(int i=0;i<4*n;i++)\n            //     cout<<seg[i]<<" ";\n            // cout<<endl;\n        }\n    }\n    \n    // Update the segment Tree recurively using updateUtil\n    void update(int index, int val) {\n        if(n==0)return;\n        updateUtil(0,0,n-1, index, val);\n    }\n    \n    // Get the sum for a specific range for the segment Tree\n    int sumRange(int left, int right) {\n        if(n==0)return 0;\n        return rangeUtil(left, right, 0, n-1, 0); \n        // query from left to right while segment tree is now at \'root\' (pos=0) and range(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 ```
['Tree', 'Recursion', 'C', 'C++']