[C++] Clean Segment Tree and Binary Indexed Tree solutions [Detailed Explanation]
Binary Indexed Tree Solution\n\n/*\n    https://leetcode.com/problems/range-sum-query-mutable/\n    \n    Binary Indexed Tree Solution\n    \n    Binary Indexed
**Binary Indexed Tree Solution**\n```\n/*\n    https://leetcode.com/problems/range-sum-query-mutable/\n    \n    Binary Indexed Tree Solution\n    \n    Binary Indexed Tree is an n-ary tree that stores has a size equal to the size of input array\n    unlike a segment tree where size is often 4n.\n    \n    1. Each node represents an index.\n    2. Here the relationship between each node is based on the binary representation.\n    A node x is child of node y, if on setting the rightmost set bit (LSB) makes it equal to y.\n    Eg. x = 10110, y = 10100\n    If we set the rightmost bit of x => 10100\n    It becomes y.\n    \n    Similarly for x, 10111 can be a child.\n    \n    3. Each node index will account for values decided by its LSB. Eg 1010, LSB number is 10, so it will account for\n    last 2 numbers in the array including itself. So bit[1010 (10)] = Accounts for nums[9:8], Bit has 1 based indexing\n    hence 1010 accounts for 9-8 (0 based indexing).\n    \n    idx      Coverage\n    (4) 0100     |   LSB = 100. This covers 4 nums: last 3 numbers and itself\n    (3) 0011 |   |   LSB = 1. This covers 1 num: 1 number (itself)\n    (2) 0010   | |   LSB = 10. This covers 2 nums: last 1 number and itself\n    (1) 0001 | | |   LSB = 1. This covers 1 num: itself\n    (0) 0000         Doesn\'t cover anything\n    \n    4. For updates, it goes to that index and adds the delta change compared to current value. Then the nodes (not descendents),\n    which accounts for a cummulative value involving this index are also updated.\n    To go to the next node index: \n        index = index + (index & -index), (index & -index) = Extracts the set LSB number\n        Adds the LSB number to current index to go to the next number\n        \n        Keep going to the next index till we don\'t cross the max fenwick tree size.\n        \n    5. For queries, eg [4,7] (1 based), we need prefixSum(7) - prefixSum(3)\n    For finding prefixSum(x), go to the index, add its value. Now that index will account for last LSB numbers, so\n    go up to its parent to get next set of accounted numbers, repeat the process till we reach dummy root 0.\n    \n    eg: prefixSum(3) => 0011, add its value, LSB number is 1 So it accounts for 1 number\n    So next number is: 0011 - 1 => 0010 (2)\n    At 2 (0010), add its value, LSB number is 10, so it accounts for 2 numbers\n    Next number: 0010 - 10 => 0000 (0), No set bit, so stop \n    \n    The sum is returned\n    \n    TC:\n        n = no. of elements\n        NumArray = O(nlogn), Since we use update for each of the n elements\n\n        for both update and query we traverse either upwards or downwards based on last set bit. \n        Worst case we traverse for the all the bits in the number. Max index number is \'n\', so log2(n) no. of\n        bits will be present for traversal.\n\n        Update: O(log2n), Traverses downwards in tree\n        Query: O(log2n), Traverses upwards in tree\n    \n    SC:O(n)\n    \n    \n*/\nclass NumArray {\n    // Stores Binary Indexed Tree and original array \n    vector<int> bit, nums;\n    int n = 0;\npublic:\n    NumArray(vector<int>& nums) {\n        n = nums.size();\n        this->nums = nums;\n        // The parent node in BIT is dummy, so +1 the size\n        bit.resize(n + 1, 0);\n        // Build BIT by doing update operation for each index with the value\n        for(int idx = 0; idx < nums.size(); idx++)\n            updateBIT(idx + 1, nums[idx]);\n    }\n    \n    // Makes the updates to applicable nodes. Delta is the net change\n    // needed for each node.\n    void updateBIT(int index, int delta) {\n        // Propagate the delta downwards till within the array\n        while(index < bit.size()) {\n            // notice how only delta is added at each node and not replaced\n            bit[index] += delta;\n            // Go to next node by adding the last set bit number\n            // (index & -index): Number created by right most set bit\n            index = index + (index & -index);\n        }    \n    }\n    \n    void update(int index, int val) {\n        // BIT works on 1 based indexing, convert to 1 based index\n        ++index;\n        // Find the delta change for the index value, this is done by comapring\n        // the value at the original nums array\n        updateBIT(index, val - nums[index-1]);\n        // Set the value in original array, this will be \n        // useful next time when a delta is calculated\n        nums[index-1] = val;\n    }\n    \n    // Finds the prefix sum in nums[0:idx-1]\n    int prefixSum(int idx) {\n        int sum = 0;\n        // Go upwards towards the root\n        while(idx > 0) {\n            sum += bit[idx];\n            idx = idx - (idx & -idx);\n        }    \n        return sum;\n    }\n    \n    int sumRange(int left, int right) {\n        // convert to 1 based index\n        ++left, ++right;\n        // nums[right-1:left-1] = nums[right-1:0] - nums[left-1:0]\n        return prefixSum(right) - prefixSum(left-1);\n    }\n};\n\n```\n\n**Segment Tree Solution**\n```\n/*\n  Range Sum query.\n  https://leetcode.com/problems/range-sum-query-mutable/\n\n    Segment tree is a complete binary tree with the leaf nodes storing the actual value of array for \n    which it is built. Each inner node just stores the overall value for that subtree.\n    Root represents [0, n] range and each subtree approx divides the range by half.\n    So left subtree: [0, n/2]\n    Right subtree: [n/2 + 1, n]\n\n    These nodes will also save the value for that range.\n    Eg: root will contain the answer to query [0, n], left subtree will store for [0, n/2]\n    and right subtree for [n/2 + 1, n].\n\n    Since we want to store a complete binary tree for an n sized array, based on analysis 4*n is \n    sufficient size for the segment tree to store all the nodes.\n\n    Build: \n    Tree is built recursively and takes O(n) time.\n    n leaf nodes and n-1 inner nodes are created\n\n    Update:\n    Each time only one of the nodes is selected and hence it traverses in a single path towards the \n    left nodes. So max takes O(heigh of tree) = O(log2N)\n\n    Query:\n    This also at max goes till the leaf node and hence takes O(log2N)\n\n    Space Complexity:\n    O(4*n) ~ O(n)\n  Ref:\n  https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/#\n*/\nclass NumArray {\n    vector<int> tree;\n    int n = 0;\npublic:\n    NumArray(vector<int>& nums) {\n        n = nums.size();\n        tree.resize(4 * n, 0);\n        \n        buildSegmentTree(0, 0, n-1, nums);\n    }\n    \n    // Builds the Segment tree from an array\n    void buildSegmentTree(int tree_idx, int low, int high, vector<int>& nums) {\n        // Leaf node reached\n        if(low == high) {\n            tree[tree_idx] = nums[low];\n            return;\n        }\n        int mid = low + (high - low) / 2;\n        // Build left and right subtrees\n        buildSegmentTree(2*tree_idx + 1, low, mid, nums);\n        buildSegmentTree(2*tree_idx + 2, mid + 1, high, nums);\n        \n        // Update the value of current node based on subtrees\n        tree[tree_idx] = merge(tree[2*tree_idx + 1], tree[2*tree_idx + 2]);\n    }\n    \n    // Kind of operation expected in a query\n    int merge(int val1, int val2) {\n        return val1 + val2;\n    }\n    \n    void update(int index, int val) {\n        return updateSegmentTree(0, 0, n-1, index, val);\n    }\n    \n    void updateSegmentTree(int tree_idx, int low, int high, int idx, int val) {\n        if(low == high) {\n            tree[tree_idx] = val;\n            return;\n        }\n        \n        int mid = low + (high - low) / 2;\n        // if the index lies in the right subtree\n        if(idx > mid)\n            updateSegmentTree(2*tree_idx + 2, mid + 1, high, idx, val);\n        // index lies on the left side\n        else\n            updateSegmentTree(2*tree_idx + 1, low, mid, idx, val);\n        \n        // Now update the value of root parent node\n        tree[tree_idx] = merge(tree[2*tree_idx + 1], tree[2*tree_idx + 2]);\n    }\n    \n    int sumRange(int left, int right) {\n        return query(0, 0, n-1, left, right);\n    }\n    \n    int query(int tree_idx, int low, int high, int left, int right) {\n        // Out of bound range\n        if(right < low || left > high)\n            return 0;\n        \n        // If the current segment falls entirely in the range, return the value\n        if(left <= low && high <= right)\n            return tree[tree_idx];\n        \n        int mid = low + (high - low) / 2;\n        // If the range entirely lies on the right side\n        if(left > mid)\n            return query(2*tree_idx + 2, mid + 1, high, left, right);\n        // Range lies entirely on left\n        else if(right <= mid)\n            return query(2*tree_idx + 1, low, mid, left, right);\n        \n        // Range is spread across left and right, so recursively split the operation\n        // |Low......left......|mid|....right....High|\n        int left_query = query(2*tree_idx + 1, low, mid, left, right);\n        int right_query = query(2*tree_idx + 2, mid+1, high, left, right);\n        \n        return merge(left_query, right_query);\n    }\n\n    /*\n        NOTE: Simplified Query function, above is faster since it takes one more\n        pruning step. In this one an invalid function will still execute but will return by\n        the out of bound check. \n\n        int rangeQuery(int l, int r, int node, int start, int end, vector<int>& tree) {\n       // when query range is out of given range\n        if(r < start || l > end)\n            return 0;\n        // when current range lie inside query range\n        else if(l <= start && end <= r)\n            return tree[node];\n        else {\n            int mid = start + (end - start)/2;\n            int left = rangeQuery(l, r, 2*node+1, start, mid, tree);\n            int right = rangeQuery(l, r, 2*node+2, mid+1, end, tree);\n            \n            return left + right;\n        }\n            \n    }\n    */\n};\n```
['C', 'Binary Tree', 'C++']