Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe question implies a point update and range query. So we can use a segment tree. We
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe question implies a point update and range query. So we can use a segment tree. We want to figure out how to compute everything we need recursively.\n\nTo find the max (noadjsum in the range) recursively: we need the max out of two things:\n\n1. noadjsum of the left child + no adj sum of right child without its leftmost element\n2. noadjsum of the left child without its rightmost element + no adj sum of the right child\n\nNow we have to recursively calculate (noadjsum without leftmost element) and (noadjsum without rightmost element) recursively as well. If we maintain another variable which stores (noadjsum with both leftmost and rightmost elements missing), we can calculate these.\n\nNow we also have to recursively calculate the noadjsum with both ends missing, we can calculate this as the max of the following:\n\n1. left child\'s (noadjsum without leftmost element) + right child\'s (noadjsum with both leftmost and rightmost elements missing)\n2. right child\'s (noadjsum without rightmost element) + left child\'s (noadjsum with both leftmost and rightmost elements missing)\n\nNow the dependencies can all be solved recursively, so we can use this to combine segment tree nodes. The base case for a node covering a single element is everything is 0 except max noadjsum which is the max of the element and 0 (we can ignore negative elements as the examples show we can choose an empty subseqence).\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```\nclass Node{\n    public:\n    Node(int l, int r)\n    {\n        this->l = l;\n        this->r = r;\n        this->left = NULL;\n        this->right = NULL;\n        this->noadjsum = 0;\n        this->lefthole = 0;\n        this->righthole = 0;\n        this->bothholes = 0;\n    }\n\n    int l;\n    int r;\n    Node* left;\n    Node* right;\n    long long noadjsum;\n    long long lefthole;\n    long long righthole;\n    long long bothholes;\n};\n\nclass SegTree{\n    public:\n    Node* root;\n    vector<int> arr;\n    int n;\n    long long MOD = 10000\'00007;\n\n    SegTree(vector<int>& nums)\n    {\n        n = nums.size();\n        arr = nums;\n        root = new Node(0, n-1);\n\n        for(int i = 0; i<n; i++)\n        {\n            point_update(root, 0, n-1, i, nums[i]);\n        }\n    }\n\n    void point_update(Node* root, int l, int r, int pos, long long val)\n    {\n        if(pos < l || pos > r || l > r)\n        {\n            return;\n        }\n\n        if(l == r)\n        {\n            arr[pos] = val;\n            root->noadjsum = max(val, 0LL);\n            root->lefthole = 0;\n            root->righthole = 0;\n            root->bothholes = 0;\n            return;\n        }\n\n        int mid = l + (r-l)/2;\n\n        if(root->left == NULL)\n        {\n            root->left = new Node(l, mid);\n            root->right = new Node(mid+1, r);\n        }\n\n        point_update(root->left, l, mid, pos, val);\n        point_update(root->right, mid+1, r, pos, val);\n        \n        root->noadjsum = max(root->left->righthole + root->right->noadjsum, \n                            root->left->noadjsum + root->right->lefthole);\n\n        root->lefthole = max(root->left->lefthole + root->right->lefthole,\n                                root->left->bothholes + root->right->noadjsum);\n\n        root->righthole = max(root->left->righthole + root->right->righthole,\n                                root->left->noadjsum + root->right->bothholes);\n\n        root->bothholes = max(root->left->lefthole + root->right->bothholes,\n                                root->left->bothholes + root->right->righthole);\n        \n    }\n\n    int query()\n    {\n        return (int)((root->noadjsum)%MOD);\n    }\n};\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        SegTree st(nums);\n\n        int n = nums.size();\n\n        long long ans = 0;\n        long long MOD = 10000\'00007;\n\n        for(int i = 0; i<queries.size(); i++)\n        {\n            int pos = queries[i][0];\n            int val = queries[i][1];\n\n            st.point_update(st.root, 0, n-1, pos, val);\n            ans = (ans + st.query())%MOD;\n        }\n\n        return (int)ans;\n    }\n};\n```
['C++']