C++ ✅ || Segment Tree || Easy Solution
\nclass NumArray {\npublic:\n\t// Check the constructor for the initialization of these variables.\n\tvector<int> seg; // Segment Tree to be stored in a vector.
```\nclass NumArray {\npublic:\n\t// Check the constructor for the initialization of these variables.\n\tvector<int> seg; // Segment Tree to be stored in a vector.\n\tint n; // Length of the segment tree vector.\n\n\n\t// Function to build the Segment Tree\n\t// This function will fill up the child values first\n\t// (left == right) will satisfy for the leaf values and they will be updated in segment tree\n\t// seg[ind]=seg[2*ind+1]+ seg[2*ind+2]; -> This will help populate all other intermediate nodes\n\t// as well as the root node with the "sum" of their child nodes.\n\t// Finally we have a segment tree which has all \'nodes\' with sum values of their child.\n\tvoid buildTree(vector<int>& nums, int ind, int left, int right) {\n\t\tif (left == right) {\n\t\t\tseg[ind] = nums[left];\n\t\t\treturn;\n\t\t}\n\t\tint mid = (left + right) / 2;\n\t\tbuildTree(nums, 2 * ind + 1, left, mid);\n\t\tbuildTree(nums, 2 * ind + 2, mid + 1, right);\n\t\tseg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];\n\t}\n\n\t// Function to update a node in the segment tree\n\t// When a node is updated, then the change in the node value has to be propagated to the root\n\t// left, right -> represents the range of the node of segment tree. (Ex: [0, n-1] -> root)\n\t// ind       -> represents "position" in the segment tree data structure (Ex: 0 -> root)\n\t// Using left, right and ind -> we have all the information on the segment tree\n\t// Node at \'ind\' in segment tree will have children at 2ind+1(left) and 2ind+2(right)\n\n\t// If index is less than left or more than right, then it is out of bound\n\t//      for this node\'s range so we ignore it and return (This makes the algo O(logn))\n\t// If left==right==index, then we found the index,\n\t//      update the value of the segment tree node & return\n\t// Otherwise, we need to find the index and we do this by checking child nodes (2ind+1, 2ind+2)\n\t//      update the segment tree ind with the updated child values\' sum.\n\t//      This would help propagate the updated value of the chid indexes to the parent (through recursion)\n\tvoid updateUtil(int ind, int left, int right, int index, int val) {\n\t\t// no overlap\n\t\tif (index < left || index > right) return;\n\n\t\t// total overlap\n\t\tif (left == right) {\n\t\t\tif (left == index)\n\t\t\t\tseg[ind] = val;\n\t\t\treturn;\n\t\t}\n\n\t\t// partial overlap\n\t\tint mid = (left + right) / 2;\n\t\tupdateUtil(2 * ind + 1, left, mid, index, val); // left child\n\t\tupdateUtil(2 * ind + 2, mid + 1, right, index, val); // right child\n\t\tseg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];\n\t}\n\n\t// Function to get the sum from the range [qlow, qhigh]\n\t// low, high -> represents the range of the node of segment tree. (Ex: [0, n-1] -> root)\n\t// ind       -> represents "position" in the segment tree data structure (Ex: 0 -> root)\n\t// Using low, high and ind -> we have all the information on the segment tree\n\t// Node at \'ind\' in segment tree will have children at 2ind+1(left) and 2ind+2(right)\n\n\t// While searching for the range, there will be three cases: (Ex: arr: [-1, 4, 2, 0])\n\t//  - Total Overlap:    Return the value. (Ex: qlow, qhigh: 0,3 and low, high: 1,2)\n\t//  - No Overlap:       Return 0. (Ex: qlow, qhigh: 0,1 and low, high: 2,3)\n\t//  - Partial Overlap:  Search for it in both the child nodes and their ranges.\n\t//                      (Ex: Searching for 1,2 and node range is 0,1)\n\tint rangeUtil(int qlow, int qhigh, int low, int high, int ind) {\n\t\tif (qlow <= low && qhigh >= high) { // total overlap\n\t\t\treturn seg[ind];\n\t\t}\n\t\tif (qlow > high || qhigh < low) { // no overlap\n\t\t\treturn 0;\n\t\t}\n\t\t// partial overlap\n\t\tint mid = low + (high - low) / 2;\n\t\treturn (rangeUtil(qlow, qhigh, low, mid, 2 * ind + 1) + rangeUtil(qlow, qhigh, mid + 1, high, 2 * ind + 2));\n\t}\n\n\t// Constructor for initializing the variables.\n\tNumArray(vector<int>& nums) {\n\t\tif (nums.size() > 0) {\n\t\t\tn = nums.size();\n\t\t\tseg.resize(4 * n, 0); // Maximum size of a segment tree for an array of size n is 4n\n\t\t\tbuildTree(nums, 0, 0, n - 1); // Build the segment tree\n\t\t\t// Print Segment Tree\n\t\t\t// for(int i=0;i<4*n;i++)\n\t\t\t//     cout<<seg[i]<<" ";\n\t\t\t// cout<<endl;\n\t\t}\n\t}\n\n\t// Update the segment Tree recurively using updateUtil\n\tvoid update(int index, int val) {\n\t\tif (n == 0)return;\n\t\tupdateUtil(0, 0, n - 1, index, val);\n\t}\n\n\t// Get the sum for a specific range for the segment Tree\n\tint sumRange(int left, int right) {\n\t\tif (n == 0)return 0;\n\t\treturn rangeUtil(left, right, 0, n - 1, 0);\n\t\t// query from left to right while segment tree is now at \'root\' (ind=0) and range(0, n-1)\n\t}\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', 'C']