Segment Tree
Intuition\nLet n = \textrm{nums.length}, q=\textrm{queries.length}.\n\nWe can use dynamic programming to solve a query for any instance of nums in O(n) time, yi
# Intuition\nLet $$n = \\textrm{nums.length}, q=\\textrm{queries.length}$$.\n\nWe can use dynamic programming to solve a query for any instance of `nums` in $$O(n)$$ time, yielding a total runtime of $$O(nq)$$. This is too slow. The problem is that for every query, we use $$O(n)$$ time to recalculate the entire answer despite just one element being modified. It would be nice if there was a way to update the answer faster.\n\nWe can update the answer in $$O(\\lg n)$$ time per query using a data structure known as a segment tree, which uses a divide and conquer strategy to quickly update an array and answer queries.\n\nI will give a brief explanation of how a segment tree works for this problem, but I recommend first solving the [Point Update Range Sum](https://usaco.guide/gold/PURS) problem:\n1. Keep an array `nums`, doing $$O(n)$$ preprocessing.\n2. Update an element in $$O(\\lg n)$$ time.\n3. Query the sum `nums[l] + nums[l + 1] + ... + nums[r]` in $$O(\\lg n)$$ time.\n\nSee the link above for a resource.\n\n## Segment Tree\nA segment tree answers queries on an array/segment/range by dividing the array into two roughly equally sized subarrays, solving/conquering the answer for each of the two subarrays, then "merging" the two subarrays\' answers to get the answer for the whole array.\n![Screenshot 2024-05-25 at 10.48.09\u202FPM.png](https://assets.leetcode.com/users/images/b0a16243-068c-4c9c-801b-3da3ae4c7e3d_1716695297.5889199.png)\n\nMoreover, there is something special about the way we divide this array. If we want to update an individual element, the answers to only $$O(\\lg n)$$ of the ranges will be changed!\n![Screenshot 2024-05-25 at 10.45.27\u202FPM.png](https://assets.leetcode.com/users/images/a7b1d614-3765-47e5-aac9-2fc7685a9191_1716695305.7036445.png)\n\nSo, we can query the answer to the whole array in $$O(1)$$ time by looking at the answer associated with topmost segment in the image, and we can update an element in the array by updating the answers to the $$O(\\lg n)$$ corresponding nodes. Note that if combining the answers from each of the two subarray children takes $$O(1)$$ time, then updating is $$O(\\lg n)$$ time.\n\n# Approach\nKeep a segment tree, where each node represents a range in `nums`, storing the bounds of the range `unsigned int lo, hi` as well as some values `long long selected[2][2]`, where `selected[i][j]` indicates the answer where the leftmost element in the range is selected iff `i = 1` and similarly for the rightmost element iff `j = 1`.\n\nIf we know `selected` for the left and right halves of the current segment, we can calculated `selected` for the current segment. For example, here is how to calculate `selected[1][0]`.\n\n![Screenshot 2024-05-25 at 10.42.23\u202FPM.png](https://assets.leetcode.com/users/images/a97c84bd-c317-4cf7-a88f-43b23bfc1557_1716695907.0409842.png)\n\nThe outer endpoints of the two subarrays are fixed to be `1` and `0` since we are calculating `selected[1][0]`. The inner endpoints can be any values as long as they are not both `1`, as that would break the condition that no two adjacent elements are selected.\n\nThus, we can combine two segments by doing\n```cpp\nselected[1][0] = max(\n    l->selected[1][0] + r->selected[0][0], max(\n    l->selected[1][1] + r->selected[0][0], \n    l->selected[1][0] + r->selected[1][0]\n));\n```\nand similarly for the other `selected` elements.\n\nSo, the solution is to initialize the segment tree, combining segments as shown above, then update each of the $$O(\\lg n)$$ segments associated with each query, again updating by combining segments as shown above. For each query, return the answer in the topmost node.\n\n# Complexity\n- Time complexity: $$O(n + q\\lg n)$$\n\n- Space complexity: $$O(n + q)$$\n\n# Code\n```cpp\nconst long long inf = 1e18;\nconst long long mod = 1e9 + 7;\n\n// Modified from https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LazySegmentTree.h\nstruct Node {\n    Node *l = nullptr, *r = nullptr;\n    unsigned int lo, hi;\n    long long selected[2][2];\n\n    Node(const vector<int> &nums, unsigned int lo, unsigned int hi) : lo(lo), hi(hi) {\n        if (lo < hi) {\n            unsigned int mid = (lo + hi) / 2;\n            l = new Node(nums, lo, mid);\n            r = new Node(nums, mid + 1, hi);\n\n            combine();\n        } else {\n            selected[0][0] = 0;\n            selected[0][1] = -inf;\n            selected[1][0] = -inf;\n            selected[1][1] = nums[lo];\n        }\n    }\n\n    void combine() {\n        selected[0][0] = max(l->selected[0][0] + r->selected[0][0], max(l->selected[0][1] + r->selected[0][0], l->selected[0][0] + r->selected[1][0]));\n        selected[0][1] = max(l->selected[0][0] + r->selected[0][1], max(l->selected[0][1] + r->selected[0][1], l->selected[0][0] + r->selected[1][1]));\n        selected[1][0] = max(l->selected[1][0] + r->selected[0][0], max(l->selected[1][1] + r->selected[0][0], l->selected[1][0] + r->selected[1][0]));\n        selected[1][1] = max(l->selected[1][0] + r->selected[0][1], max(l->selected[1][1] + r->selected[0][1], l->selected[1][0] + r->selected[1][1]));\n    }\n\n    void update(int i, long long x) {\n        if (i < lo || hi < i) {\n            return;\n        }\n\n        if (lo == hi) {\n            selected[0][0] = 0;\n            selected[1][1] = x;\n            return;\n        }\n\n        l->update(i, x);\n        r->update(i, x);\n\n        combine();\n    }\n};\n\nclass Solution {\n  public:\n    int maximumSumSubsequence(vector<int> &nums, vector<vector<int>> &queries) {\n        Node segmentTree(nums, 0, nums.size() - 1);\n\n        long long res = 0;\n        for (auto &query : queries) {\n            segmentTree.update(query[0], query[1]);\n            res += max(segmentTree.selected[0][0], max(segmentTree.selected[0][1], max(segmentTree.selected[1][0], segmentTree.selected[1][1])));\n            res %= mod;\n        }\n        return static_cast<int>(res);\n    }\n};\n```
['Segment Tree', 'C++']