Segment Tree [c++]
Intuition\n Describe your first thoughts on how to solve this problem. \nSegement tree.\n\nStore the following 4 values for each segment (l, r):\n1 l -> (r - 1)
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSegement tree.\n\nStore the following 4 values for each segment (l, r):\n1 l -> (r - 1)    ( maximum sum of a subsequence of nums where no two adjacent elements are selected in range (l, r - 1))\n2 (l + 1) -> r\n3 (l + 1) -> (r -1)\n4 l -> r\n\nUse following function to merge segment:\nvoid merge(node& ln, node& rn, node& c)\n{\n    c.c = max(ln.l + rn.c, ln.c + rn.r);\n    c.l = max(ln.c + rn.m, ln.l + rn.l);\n    c.r = max(ln.m + rn.c, ln.r + rn.r);\n    c.m = max(ln.m + rn.l, ln.r + rn.m);\n}\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\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```\ntypedef long long ll;\nstruct node {\n    // without right\n    ll l = 0;\n    // without left\n    ll r = 0;\n    ll m = 0;\n    // witheverything\n    ll c = 0;\n};\n\nstruct tree {\n    int n;\n    vector<node> arr;\n    void init(const vector<int>& nums) {\n        n = nums.size();\n        arr = vector<node>(n * 4 + 2);\n        build(0, n - 1, 1, nums);\n    }\n    void merge(node& ln, node& rn, node& c)\n    {\n        c.c = max(ln.l + rn.c, ln.c + rn.r);\n        c.l = max(ln.c + rn.m, ln.l + rn.l);\n        c.r = max(ln.m + rn.c, ln.r + rn.r);\n        c.m = max(ln.m + rn.l, ln.r + rn.m);\n    }\n    node& build(int l, int r, int cur, const vector<int>& nums)\n    {\n        if (l == r) {\n           arr[cur] = node(0, 0, 0, max(0, nums[l]));\n            return arr[cur];\n        }\n        int m = (l + r) / 2;\n        auto& ln = build(l, m,  cur * 2, nums);\n        auto& rn = build(m + 1, r, cur * 2 + 1, nums);\n        auto& c = arr[cur];\n        merge(ln, rn, c);\n        return c;\n    }\n\n    \n    // l, r, range of current node cur, \n    // p the target point\n    node& update(int l, int r, int cur, int p, int nv) {\n        if (p < l || p > r)  return arr[cur];\n        if (l == r) {\n            arr[cur].c = max(0, nv);\n            return arr[cur];\n        }\n        int m = (l + r) / 2;\n        auto& ln = update(l, m,  cur * 2, p, nv);\n        auto& rn = update(m + 1, r, cur * 2 + 1, p, nv);\n        merge(ln, rn, arr[cur]);\n        return arr[cur];\n    }\n\n    \n};\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& qs) {\n        const int mod = (int)(1e9 + 7);\n        ll sum = 0;\n        tree t;\n        t.init(nums);\n        int n = nums.size();\n        for (auto q : qs)\n        {\n            int x = q[0];\n            int y = q[1];\n            t.update(0, n - 1, 1, x, y);\n            // cout << x << "," << y << "," << t.arr[1].c << endl;\n            sum = (sum + t.arr[1].c) % mod;\n        }\n        return sum;\n    }\n};\n```
['C++']