Fenwick Tree + Divide et Impera : one branch memorized, another recomputed
IntuitionThe problem requires finding the maximum sum subsequence with no adjacent elements after multiple array modifications. This demands a dynamic approach
# Intuition\nThe problem requires finding the maximum sum subsequence with no adjacent elements after multiple array modifications. This demands a dynamic approach that can:\n1. Handle array updates efficiently\n2. Track subsequence sums without adjacent elements\n3. Quickly recompute only modified segments\n\n# Approach\nKey Strategy: Divide et Imera with Dynamic Programming\n- Split array recursively into halves\n- Maintain 4 DP states for each subarray representing different selection scenarios\n- Use memoization to cache and reuse computations\n- Leverage Fenwick tree to track version/modification of array segments\n\n## Core Invariants\n- `res00`: left right borders not included\n- `res01`: left not selected, right - selected\n- `res10`: left selected, right - not selected\n- `res11`: both selected\n\n## Version Tracking\n- Fenwick tree efficiently tracks array modification versions\n- Enables selective recomputation of only modified segments\nIMPORTANT: we look at not the max version in the segment, but at the sum of versions\n\n# Complexity\n- Time Complexity: $$O(M \\log N \\log N)$$\n  - M queries\n  - Recursive DP with log(N) depth\n  - Fenwick tree operations log(N)\n\n- Space Complexity: $$O(N \\log N)$$\n  - Memoization map\n  - Fenwick tree\n  - Recursive call stack\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int maximumSumSubsequence(const vector<int>& nums, const vector<vector<int>>& queries) {\n        this->nums = nums;\n        fenw_version_sum.resize(nums.size() + 1);\n\n        const long long kMod = 1e9 + 7;\n        long long res = 0;\n        for (const auto& q : queries) {\n            this->nums[q[0]] = q[1];\n            fenw_inc(q[0]); // Increment version for Fenwick tree tracking\n            res = (res + get_record(0, nums.size() - 1).accum()) % kMod;\n        }\n        return res;\n    }\n\nprivate:\n    struct PairHasher {\n        template <class T1, class T2>\n        std::size_t operator()(const std::pair<T1, T2>& p) const {\n            auto h1 = std::hash<T1>{}(p.first);\n            auto h2 = std::hash<T2>{}(p.second);\n            return h1 ^ (h2 << 1);\n        }\n    };\n\n    struct DpRecord { // Dynamic programming record to track non-adjacent subsequence sums\n        long long res00 = 0;\n        long long res01 = 0;\n        long long res10 = 0;\n        long long res11 = 0;\n        long long accum() const { return max({res00, res01, res10, res11}); }\n    };\n\n    vector<int> nums;\n    // Memoization map to cache computed records for specific range and version\n    unordered_map<pair<int, int>, pair<int, DpRecord>, PairHasher> memo_beg_end_2_record;\n    // Fenwick tree to track version of array modifications\n    vector<long long> fenw_version_sum;\n\n    // Divide et Impera with recomputing the half that has increased version\n    DpRecord get_record(int beg, int end) {\n        assert(beg <= end);\n        // Base case: single element\n        if (beg == end) return {0LL, 0LL, 0LL, max<long long>(0, nums[beg])};\n\n        int want_version = fenw_get_dist(beg, end);\n        auto it = memo_beg_end_2_record.find({beg, end});\n        if (it != memo_beg_end_2_record.end() && it->second.first >= want_version)\n            return it->second.second;\n\n        // Divide et Impera: split range into two halves\n        int mid = (beg + end) / 2;\n        auto l = get_record(beg, mid);\n        auto r = get_record(mid + 1, end);\n\n        DpRecord rec; // DP states considering non-adjacent constraint\n\n        rec.res00 = max(rec.res00, l.res00 + r.res00);\n        rec.res00 = max(rec.res00, l.res01 + r.res00);\n        rec.res00 = max(rec.res00, l.res00 + r.res10);\n\n        rec.res01 = max(rec.res01, l.res00 + r.res01);\n        rec.res01 = max(rec.res01, l.res01 + r.res01);\n        rec.res01 = max(rec.res01, l.res00 + r.res11);\n\n        rec.res10 = max(rec.res10, l.res10 + r.res00);\n        rec.res10 = max(rec.res10, l.res11 + r.res00);\n        rec.res10 = max(rec.res10, l.res10 + r.res10);\n\n        rec.res11 = max(rec.res11, l.res10 + r.res01);\n        rec.res11 = max(rec.res11, l.res11 + r.res01);\n        rec.res11 = max(rec.res11, l.res10 + r.res11);\n\n        // Memoize the result for current range and version\n        memo_beg_end_2_record[{beg, end}] = {want_version, rec};\n        return rec;\n    }\n\n    // Update version in Fenwick tree\n    void fenw_inc(int i) {\n        ++i;\n        for (; i < fenw_version_sum.size(); i += i & -i)\n            ++fenw_version_sum[i];\n    }\n\n    // Get versions sum till i\n    int fenw_get_below_or_eq(int i) {\n        ++i;\n        int res = 0;\n        for (; i > 0; i -= i & -i)\n            res += fenw_version_sum[i];\n        return res;\n    }\n\n    // Get versions sum for a range\n    int fenw_get_dist(int beg, int end) {\n        int res = fenw_get_below_or_eq(end);\n        if (beg > 0)\n            res -= fenw_get_below_or_eq(beg - 1);\n        return res;\n    }\n};\n\n```
['C++']