Simple Segment Tree + Point Update || Explained || Easy to understand || Beats 100% || C++
Intuition\nWe need to maintain a segment tree which will have the maximum sum of the subsequence in the segment where no two adjacent values are chosen. \nTo ma
# Intuition\n**We need to maintain a segment tree which will have the maximum sum of the subsequence in the segment where no two adjacent values are chosen. \nTo make sure that the condition holds, we need to store 4 values at each segment node. All the four values refer to:**\n1. Leftmost and Rightmost elements are taken\n2. Only leftmost is taken\n3. Only rightmost is taken\n4. None of the leftmost and rightmost taken\n\n**Now using all these 4 values, we can constitute the result for other nodes, and get the maximum sum in each segments.**\n# Complexity\n- Time complexity:$$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#define ll long long\nclass SGTree{\n    vector<vector<ll>> seg;\n    public:\n    // segment tree constructor for defining the size\n    SGTree(ll n){\n        seg.resize(4 * n + 1);\n    }\n    // operation function\n    vector<ll> comp(vector<ll>& a, vector<ll>& b){\n        vector<ll> ans(4);\n        // 0 - both left and right\n        // 1 - only left\n        // 2 - only right\n        // 3 - neither left nor right\n        ans[0] = max({a[1] + b[2], a[0] + b[2], a[1] + b[0]});\n        ans[1] = max({a[1] + b[1], a[1] + b[3], a[0] + b[3]});\n        ans[2] = max({a[2] + b[2], a[3] + b[2], a[3] + b[0]});\n        ans[3] = max({a[2] + b[3], a[3] + b[1], a[3] + b[3]});\n        return ans;\n    }\n    // for building the segment tree\n    void build(ll ind, ll left, ll right, vector<int>& arr){\n        // when on the leaf node, add the value to the segment\n        if(left == right){\n            vector<ll> ans(4, 0);\n            ans[0] = arr[left];\n            ans[1] = -1e15;\n            ans[2] = -1e15;\n            ans[3] = 0;\n            seg[ind] = ans;\n            return;\n        }\n        // now go on the build the left and right subtree\n        ll mid = left + (right - left) / 2;\n        // left subtree\n        build(2 * ind + 1, left, mid, arr);\n        // right subtree\n        build(2 * ind + 2, mid + 1, right, arr);\n        // operation which you need to perform on the subtree\n        seg[ind] = comp(seg[2 * ind + 1], seg[2 * ind + 2]);\n    }\n    // for the query of the data\n    vector<ll> query(ll ind, ll left, ll right, ll l, ll r){\n        // when the segment is not in the range (disjoll)\n        if(r < left || l > right) return vector<ll>(4, 0);\n        // when fully in the range \n        if(l <= left && right <= r){\n            return seg[ind];\n        }\n        // partial overlapping\n        ll mid = left + (right - left) / 2;\n        vector<ll> leftC = query(2 * ind + 1, left, mid, l, r);\n        vector<ll> rightC = query(2 * ind + 2, mid + 1, right, l, r);\n        // operation which you need to perform on the subtree\n        return comp(leftC , rightC);\n    }\n    // poll update for the tree\n    void update(ll ind, ll left, ll right, ll pos, ll val){\n        // when on the leaf node, update the value\n        if(left == right){\n            vector<ll> ans(4, 0);\n            ans[0] = val;\n            ans[1] = -1e15;\n            ans[2] = -1e15;\n            ans[3] = 0;\n            seg[ind] = ans;\n            return;\n        }\n        // now check on the left and right\n        ll mid = left + (right - left) / 2;\n        // when the position which need to be update is in left\n        if(left <= pos && pos <= mid){\n            update(2 * ind + 1, left, mid, pos, val);\n        }else update(2 * ind + 2, mid + 1, right, pos, val);\n        // operation which you need to perform on the tree\n        seg[ind] = comp(seg[2 * ind + 1], seg[2 * ind + 2]);\n    }\n \n};\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n = nums.size();\n        SGTree seg(n);\n        seg.build(0, 0, n-1, nums);\n        ll sum = 0, mod = 1e9 + 7;\n        for(auto &it: queries){\n            int pos = it[0], val = it[1];\n            seg.update(0, 0, n-1, pos, val);\n            vector<ll> ar = seg.query(0, 0, n-1, 0, n-1);\n            ll maxi = max({ar[0], ar[1], ar[2], ar[3]});\n            sum = (sum + maxi) % mod;\n        }\n        return sum;\n    }\n};\n```
['C++']