3165. Maximum Sum of Subsequence With Non-adjacent Elements: FASTEST SOLUTION + SEGMENT TREE
Intuition\nThis is a straight forward segment tree problem were we have a custom merge function to merge our segment tree nodes.\n\n# Approach\n Describe your a
# Intuition\nThis is a straight forward segment tree problem were we have a custom merge function to merge our segment tree nodes.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe will maintain 4 pieces of information in our segment tree node.\n1. The best answer. The best answer either the best answer of the left node plus best answer of the right node excluding the leftmost element of the right node as we want to not take two elements that are next to each other. We can do the same thing but take everything on the right and take everything other than the rightmost on the left node.\n2. The answer excluding rightmost and leftmost position. This is equal to the maximum of the answer for the left node + the answer of the right node excluding the last value as we want to make sure no elements we take are on any of the edges Similarly we do this for max of right node and answer for first node excluding the first element.\n3. The answer excluding the leftmost position. This is equal to the max of the answer excluding the leftmost for both the left and right nodes and the no edges value for the left node plus the best answer for the right node.\n4. The answer excluding the rightmost position. This is similar to the leftmost position one, look at the code for more details.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nlogn)$$ \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ \n\n# Code\n```\n#define ll long long\n\nstruct node{\n    ll best, no_first, no_last, no_extreme;\n\n};\n\n\nconst node zero = {0, 0, 0,0};\nnode comb(node a, node b) {\n    node c;\n    c.best = max({a.no_last+b.best, a.best+b.no_first, b.best, a.best});\n    c.no_extreme = max(a.no_extreme+b.no_last, a.no_first+b.no_extreme);\n    c.no_first = max(a.no_first + b.no_first, a.no_extreme + b.best);\n    c.no_last = max(a.no_last+b.no_last, a.best+b.no_extreme);\n    return c;\n\n}\n\ntemplate <typename T>\nstruct Segtree\n{\n\n    int n;\n    int bstart, stsize;\n    vector<T> st;\n\n\n    T op(T a, T b) {\n        return comb(a, b);\n    }\n\n    Segtree(int _n) {\n        n = _n;\n        bstart = 1;\n        while (bstart < n) bstart *= 2;\n        stsize = bstart * 2 - 1;\n        bstart--;\n\n        st = vector<T>(stsize, zero);\n    }\n\n    void update(int ind, T v) {\n\n        ind += bstart;\n        st[ind] = v;\n\n        while (1) {\n            if (!ind) break;\n            ind = (ind - 1) / 2;\n            st[ind] = op(st[ind * 2 + 1], st[ind * 2 + 2]);\n        }\n\n    }\n\n    T query(int c, int cmin, int cmax, int minb, int maxb) {\n        if (cmin >= minb && cmax <= maxb){ return st[c];}\n        if (cmin > maxb || cmax < minb) return zero;\n        return op(query(c * 2 + 1, cmin, (cmin + cmax) / 2, minb, maxb),\n                  query(c * 2 + 2, 1 + (cmin + cmax) / 2, cmax, minb, maxb));\n    }\n\n    T query(int lo, int hi) {\n        if (lo > hi) return zero;\n        if (lo == hi) return st[lo + bstart];\n        return query(0, 0, bstart, lo, hi);\n    }\n\n};\n\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        Segtree<node> s(nums.size()+5);\n        ll ans = 0;\n        for(ll i = 0; i < nums.size(); i++){\n            node tmp =zero;  \n            tmp.best=nums[i];\n            s.update(i, tmp);\n        }\n        for(ll i = 0; i < queries.size(); i++){\n            node tmp =zero;  \n            tmp.best=queries[i][1];\n            s.update(queries[i][0], tmp);\n            ans += s.query(0,nums.size()+1).best;\n        }\n        int val = (ans%1000000007);\n        return val;\n    }\n};\n```
['C++']