c++ segment tree
1) c++ segment tree, following https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/\n\nO(log(n)) for query an
1) c++ segment tree, following https://leetcode.com/articles/a-recursive-approach-to-segment-trees-range-sum-queries-lazy-propagation/\n\nO(log(n)) for query and update, O(nlog(n)) for tree construction/pre-processing\n\nnote: we can\'t use the solution with O(n) pre-processing and O(1) query as in  [303. Range Sum Query - Immutable](https://leetcode.com/problems/range-sum-query-immutable/discuss/494820/c%2B%2B-very-simple) because we would have to recompute partial sums in O(n) on every update\n\n```\nclass NumArray {\nprivate:\n    int arr_size;\n    int tree_size;\n    vector<int> tree;\n    int merge(int l, int r){return (l+r);}\n    \n   void buildTree(vector<int>& arr,int treeIndex, int lo, int hi){\n       if(lo==hi) {\n           tree[treeIndex] = arr[lo]; //leaf node -> store value\n           return;\n       }\n       //recurse deeper for children\n       int mid = lo+(hi-lo)/2;\n       int leftIndex = 2*treeIndex+1;\n       int rightIndex = 2*treeIndex+2;\n       buildTree(arr,leftIndex, lo, mid);\n       buildTree(arr, rightIndex, mid+1, hi);\n       //merge, e.g. sum\n       tree[treeIndex] = merge(tree[leftIndex], tree[rightIndex]);\n   }\n    \n     void updateTree(int treeIndex, int lo, int hi,int arrIndex, int val){\n          if(lo==hi) {// leaf node. update element.\n              tree[treeIndex] = val; \n              return;\n          }\n         // recurse deeper for appropriate child\n         int mid = lo+(hi-lo)/2;\n         int leftIndex = 2*treeIndex+1;\n         int rightIndex = 2*treeIndex+2;\n         if (arrIndex > mid)  updateTree(rightIndex, mid+1, hi, arrIndex, val);\n         else updateTree(leftIndex, lo, mid, arrIndex, val);\n         //merge updates\n         tree[treeIndex] = merge(tree[leftIndex], tree[rightIndex]);\n         \n     }\n    \n     int queryTree(int treeIndex, int lo, int hi, int i, int j){\n        //segment completely outside range\n         if(lo > j || hi < i) return 0;\n         // segment completely inside range\n         if(i <= lo &&  j >=hi) return tree[treeIndex];\n         // partial overlap of current segment and queried range. Recurse deeper.\n         int mid = lo+(hi-lo)/2;\n         int leftIndex = 2*treeIndex+1;\n         int rightIndex = 2*treeIndex+2;\n         if (i > mid)  //if the range is completely to the right of mid\n             return queryTree(rightIndex, mid+1, hi, i, j);\n         else if (j <= mid)  //if the range is completely to the left of mid\n             return queryTree(leftIndex, lo, mid, i, j);\n         //if the range falls on left and right of mid\n         int leftQuery = queryTree(leftIndex, lo, mid, i, mid);\n         int rightQuery = queryTree(rightIndex, mid+1, hi, mid+1, j);\n          // merge query results\n         return merge(leftQuery, rightQuery);\n     }\n\npublic:\n    NumArray(vector<int>& nums) {\n        arr_size = nums.size();\n        if (arr_size==0) return;\n        int height = (int)(ceil(log2(arr_size)));   \n        tree_size = 2*(int)pow(2, height) - 1;  \n        tree.resize(tree_size,0);\n        \n        buildTree(nums, 0, 0, arr_size-1);\n    }\n    \n    void update(int i, int val) {\n         updateTree(0, 0, arr_size-1, i, val);\n    }\n    \n    int sumRange(int i, int j) {\n        int sum = queryTree(0, 0, arr_size-1, i, j);\n        return sum;\n    }\n};\n```\n\n2) simple solution: O(n) for query, O(1) for update, zero pre-processing cost (unlike the above)\n\n```\nclass NumArray {\n    vector<int>& _nums;\npublic:\n    NumArray(vector<int>& nums):_nums(nums) {}\n    void update(int i, int val) {\n        _nums[i]=val;\n    }\n    int sumRange(int i, int j) {\n        int sum = 0;\n        for (int x=i; x<=j; x++) sum+=_nums[x];\n        return sum;\n    }\n};\n
['Tree', 'C++']