Segment tree recursive , iterative , Binary index iterative explained
Approach 1 : using segment tree recurssive + good readable code for undersatnding\n\nclass NumArray {\npublic:\n    vector<int> tree;\n    vector<int> a;\n    v
**Approach 1 : using segment tree recurssive + good readable code for undersatnding**\n```\nclass NumArray {\npublic:\n    vector<int> tree;\n    vector<int> a;\n    void constructTree(int index , int left_range , int right_range)        // index is responsible for the range "range_left" , "range_right" \n    {\n        if(left_range > right_range)    return ;                                    // completely excluded region\n        if(left_range == right_range)   { tree[index] = a[left_range]; return; };   // leaf node\n        \n        int mid = (left_range + right_range)/2;                                     // divide and conquer \n        constructTree(index*2 ,  left_range , mid);\n        constructTree(index*2+1, mid+1 , right_range);\n        tree[index] = tree[index*2] + tree[index*2+1];                              // store answer in this node\n    }    \n    // index = node\'s index , update_left/right is the range ehich need sto be updated , node_left/right means this node is responsible for these range\n    void updater(int index, int update_left , int update_right, int node_left , int node_right, int val) \n    {\n        if(update_left > node_right || update_right < node_left)    return;     // completely excluded\n        if(node_left == node_right)                                             // reached leaf node \n        { \n            tree[index] = val; \n            a[node_left] = val;         // this line can be skipped, we dont give a fuck to vector a once tree has been made\n            return; \n        };\n        int mid = (node_left + node_right)/2;                                       \n        updater(index*2 , update_left , update_right , node_left , mid       , val);\n        updater(index*2+1,update_left , update_right , mid+1     , node_right, val);\n        tree[index] = tree[index*2] + tree[index*2+1];\n        return;\n    }\n    int get_sum(int index , int left_range, int right_range , int node_left , int node_right)       \n    {\n        if(left_range > node_right || right_range < node_left)  return 0;\n        if(left_range <= node_left and right_range >= node_right)   return tree[index];\n        \n        int mid = (node_left + node_right)/2;\n        int left_ans  = get_sum( index*2 , left_range , right_range , node_left , mid);\n        int right_ans = get_sum(index*2+1, left_range , right_range , mid+1 , node_right);\n        return left_ans + right_ans;        \n    }\n    \n    NumArray(vector<int>& arr) \n    {\n        int n = arr.size();                                                     \n        tree = vector<int> (4*n+1); \n        a = vector<int>(arr.begin() , arr.end());                               // note this step ,  we have created a global array , for our code, this step can be avoided , if we pass input array to this function, but to keep code simple we have made a global array\n        constructTree(1,0,n-1);     // index, node_left , node_right\n        \n        // for(int i=0 ; i<=7  ; i++)            printf("i = %d\\t\\tvAL = %d\\n", i, tree[i]);\n    }\n    void update(int i, int val) {\n        updater(1,i,i,0,a.size()-1 , val);                                      // node the update_left/right are same, as these are point updates, \n    }\n    int sumRange(int left_range, int right_range) {\n        return get_sum(1 , left_range , right_range , 0 , a.size()-1);\n    }\n};\n```\n**Approach 2 : segment tree using iterative**\n```\n// thanks to JLAGS https://www.youtube.com/watch?v=Oq2E2yGadnU\nvector<int> tree;\n    int n;\n    \n    NumArray(vector<int>& nums) {\n        n = nums.size();\n        tree = vector<int>(n<<1);                   // initilizing 2*N array for segment tree\n     \n        for(int i=0 ; i<n ; i++)                    // filling leaves \n            tree[i+n] = nums[i];\n        for(int i = n-1 ; i>=1 ; i--)               // filling parents\n            tree[i] = tree[i<<1] + tree[(i<<1) +1];\n    }\n    \n    void update(int i, int val) {\n        \n        i += n;                        // jumping to index of leaf\n        tree[i] = val;                //  updating value at leaf\n        while(i>1)\n        {\n            i/=2;\n            tree[i] = tree[i<<1] + tree[(i<<1)+1];\n        }\n    }\n    int sumRange(int i, int j) {\n        \n        i+=n , j+=n+1;\n        int sum = 0;\n        while(i<j)\n        {\n            if(i&1)                         // if left is odd then jumping to its parent is not a good idea as its range is bigger with partial overlap\n                sum+=tree[i++];   // as a result we must process this here only\n            if(j&1)\n                sum+=tree[--j];\n            i/=2 , j/=2;\n        }\n        return sum;\n    }\n```\n\n**Approach 3 : using Binary Index tree**\nI recently learned , Binary index Tree, m feeling excited\n```\nclass NumArray {\npublic:\n    vector<int> a,BIT;\n    int n;\n    \n    void init(int i, int val)\n    {\n        i++;\n        while(i<=n)\n            BIT[i] += val,\n            i += (i&-i);\n    }\n    int rangeSum(int i)\n    {\n        i++;\n        int sum = 0;\n        while(i)\n            sum += BIT[i],\n            i -= i&-i;\n        return sum;\n    }\n    NumArray(vector<int>& nums) {\n        \n        n = nums.size();\n        a = vector<int>(nums.begin(), nums.end());\n        BIT=vector<int>(n+1);\n        \n        for(int i=0 ; i<n ; i++)\n            init(i , a[i]);\n    }\n    \n    void update(int i, int val) {\n        int diff = val - a[i];\n        a[i] = val;\n        init(i,diff);\n    }\n    \n    int sumRange(int i, int j) {\n        \n        return rangeSum(j) - rangeSum(i-1);\n    }\n};\n```
[]