Segment Tree | C++ | Easy to Understand
Intuition\n Describe your first thoughts on how to solve this problem. \nAs the question says updating the array and getting ans for each query, segment tree is
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAs the question says updating the array and getting ans for each query, segment tree is the best approach to think.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nAs we cannot take adjacent elements, we will build our tree in such a way that each node contains sum of non adjavent elements. If we start from the bottommost, we can say that the maximum sum will only to be carried forward. For the case of non adjacent, we pick maximum of all four cases and store it in the node. \nSuppose we have the range [l,r], we can have four cases as:\n1. l0_r0: taking non adjacent elements in the range [l+1,r-1]\n2. l1_r0: taking non-adjacent elements in the range [l,r-1] with l being taken.\n3. l0_r1: taking non-adjacent elements in the range [l+1,r] with r being taken.\n4. l1_r1: taking non-adjacent elements in the range [l,r] with l and r being taken.\nIf in any case, it is not possible to chose the corresponding set, we take the value as INt_MIN(-INFINITY).\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nEach query takes O(logn) for update.\nTC: O(mlogn), m is the number of queries and n is the size of input array.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(4*n) to store the tree\n\n# Code\n```\nint MOD = 1e9 + 7;\ntypedef long long ll;\nclass Node {\npublic:\n    ll l0_r0;\n    ll l1_r0;\n    ll l0_r1;\n    ll l1_r1;\n    Node(){}\n    Node(int a0, int a1, int a2, int a3)\n    {\n        l0_r0 = a0;\n        l1_r0 = a1;\n        l0_r1 = a2;\n        l1_r1 = a3;\n    }\n    ll get_max_left_right_exclude(const Node& left, const Node& right)\n    {\n        return max({left.l0_r0 + right.l0_r0, left.l0_r0 + right.l1_r0, left.l0_r1 + right.l0_r0});\n    }\n\n    ll get_max_left_include_right_exclude(const Node& left, const Node& right)\n    {\n        return max({left.l1_r0 + right.l0_r0, left.l1_r0 + right.l1_r0, left.l1_r1 + right.l0_r0});\n    }\n\n    ll get_max_left_exclude_right_include(const Node& left, const Node& right)\n    {\n        return max({left.l0_r0 + right.l0_r1, left.l0_r0 + right.l1_r1, left.l0_r1 + right.l0_r1});\n    }\n\n    ll get_max_left_right_include(const Node& left, const Node& right)\n    {\n        return max({left.l1_r0 + right.l0_r1, left.l1_r0 + right.l1_r1, left.l1_r1 + right.l0_r1});\n    }\n\n    ll get_max_value()\n    {\n        return max({l0_r0, l1_r0, l0_r1, l1_r1});\n    }\n\n    void merge(const Node& left, const Node& right)\n    {\n        this->l0_r0 = get_max_left_right_exclude(left,right);\n        this->l1_r0 = get_max_left_include_right_exclude(left,right);\n        this->l0_r1 = get_max_left_exclude_right_include(left,right);\n        this->l1_r1 = get_max_left_right_include(left,right);\n    }\n\n    // void print()\n    // {\n    //     cout<<l0_r0<<" "<<l1_r0<<" "<<l0_r1<<" "<<l1_r1<<endl;\n    // }\n};\n\nclass SegTree {\npublic:\n    int len;\n    vector<Node>tree;\n\n    SegTree(int n) {\n        len = n;\n        tree.resize(4*len);\n    }\n\n    void build(vector<int>& a, int v, int tl, int tr)\n    {\n        if(tl == tr)\n        {\n            tree[v] = Node(0,INT_MIN, INT_MIN, a[tl]);\n            return;\n        }\n        int tm = tl + (tr-tl)/2;\n        build(a,2*v, tl,tm);\n        build(a,2*v+1,tm+1,tr);\n        tree[v].merge(tree[2*v], tree[2*v+1]);\n    }\n\n    // void preorder(int v)\n    // {\n    //     if(v > 2*len)\n    //         return;\n    //     tree[v].print();\n    //     preorder(2*v);\n    //     preorder(2*v + 1);\n    // }\n\n    void update(int v, int val, int tl, int tr, int ind) {\n        if(tl > ind || tr < ind) return;\n        if(tl == ind  && tr == ind)\n        {\n            tree[v] = Node(0,INT_MIN,INT_MIN,val);\n            return;\n        }\n        int tm = tl + (tr - tl)/2;\n        update(2*v,val,tl,tm,ind);\n        update(2*v+1,val,tm+1,tr,ind);\n        tree[v].merge(tree[2*v],tree[2*v+1]);\n    }\n};\n\nclass Solution {\npublic:\n    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {\n        int n = nums.size();\n        SegTree* seg = new SegTree(n);\n        seg->build(nums,1,0,n-1);\n        int m = queries.size();\n        ll ans = 0;\n        for(int i=0; i<m; i++)\n        {\n            seg->update(1, queries[i][1], 0, n-1,queries[i][0]);\n            ans = (ans +  seg->tree[1].get_max_value())%MOD;\n        }\n        return (int)ans%MOD;\n    }\n};\n```
['C++']