Another weird segment tree application
Intuition\nWe have to maintain 2^2 combinations of left/right of the DP in a segment tree. Do points updates and update the information. Return idx 0.\n\n# Appr
# Intuition\nWe have to maintain 2^2 combinations of left/right of the DP in a segment tree. Do points updates and update the information. Return idx 0.\n\n# Approach\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nint mod = 1e9+7;\n\nclass Segment {\n    public:\n    int n;\n    vector<int> right_noleft;\n    vector<int> left_noright;\n    vector<int> both;\n    vector<int> none;\n\n    Segment(vector<int>& v) {\n        n = (int)v.size();\n        right_noleft.resize(4*n);\n        left_noright.resize(4*n);\n        both.resize(4*n);\n        none.resize(4*n);\n        init(0, 0, n-1, v);\n    }\n\n    void set(int idx, int left, int right) {\n        both[idx] = both[left] + right_noleft[right];\n        both[idx] = max(both[idx], both[right] + left_noright[left]);\n        \n        none[idx] = right_noleft[left] + none[right];\n        none[idx] = max(none[idx], none[left] + left_noright[right]);\n        left_noright[idx] = none[right] + both[left];\n        left_noright[idx] = max(left_noright[idx], left_noright[left] + left_noright[right]);\n\n        right_noleft[idx] = none[left] + both[right];\n        right_noleft[idx] = max(right_noleft[idx], right_noleft[left] + right_noleft[right]);\n\n        both[idx] = max(0, both[idx]);\n        left_noright[idx] = max(0, left_noright[idx]);\n        right_noleft[idx] = max(0, right_noleft[idx]);\n        none[idx] = max(0, none[idx]);\n        return;\n    }\n\n    void init(int idx, int l2, int r2, vector<int>& v) {\n        if (l2 == r2) {\n            int val = v[l2];\n            right_noleft[idx] = 0;\n            left_noright[idx] = 0;\n            none[idx] = 0;\n            both[idx] = max(val,0);\n            return;\n        }\n\n        int m = (l2 + r2)/2;\n        init(idx*2 + 1, l2, m, v);\n        init(idx*2 + 2, m+1, r2, v);\n\n        int left = idx*2 + 1;\n        int right = idx*2 + 2;\n        set(idx, left, right);\n    }\n\n    void update(int idx, int l1, int l2, int r2, int val) {\n        if (l2 == r2) {\n            assert(l1 == l2);\n            both[idx] = max(val,0);\n            return;\n        }\n\n        int m = (l2+r2)/2;\n        if (l1 <= m)\n            update(idx*2+1, l1, l2, m, val);\n        if (l1 >= m+1)\n            update(idx*2+2, l1, m+1, r2, val);\n        int left = idx*2 + 1;\n        int right = idx*2 + 2;\n        set(idx, left, right);\n    }\n\n};\n\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        Segment seg(nums);\n        int ans= 0;\n        int n = (int)nums.size();\n        \n        for (auto& each: queries) {\n            int idx = each[0];\n            int val = each[1];\n            seg.update(0, idx, 0, n-1, val);\n            ans += seg.both[0];\n            ans %= mod;\n        }\n\n        return ans;\n    }\n};\n```
['C++']