3165. 不包含相邻元素的子序列的最大和

Problem: 3165. 不包含相邻元素的子序列的最大和

做题历程

起初，我直接想到的也是dp做法，但是这需要$O(n^2)$的时间复杂度，最后做出来也的确超时了。

我便想，这个dp数组能否在不同查询中共用？

可是维护这个dp数组也需要$O(n)$的时间复杂度，这样做是白白浪费空间。我们需要的是一个至少能够以$O(logn)$的时间维护和查询不包含相邻元素的子序列的最大和的数据结构。

而看到$O(logn)$这个数量级，不出意料的话应该需要不断将输入（这里就是数组）二分成不同区间了。

除了时间复杂度，我们需要这个数据结构有什么样的性质呢？

这个时间通过dp思想的启发，我们可以想到，如果这个数据结构能够维护数组的区间信息，利用dp思想来求得组合这些区间后，我们就能够求出不包含相邻元素的子序列的最大和。

而这就是线段树。

线段树

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在$O(logn)$的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。OI Wiki。

我们递归地把数组二分成更小的区间，每一个节点代表一个区间，而其子节点代表其更小的两个子区间。可见线段树也是一个完全二叉树。

我们可以使用数组像存储堆一样来存储线段树。如果存储下标从1开始，那么一个节点的左子节点为2*i，右子节点为2*i+1。

假设线段树有n个叶子节点，即数组有n个元素，那么树的高度为$\lceil logn \rceil$，总的节点数量为$2^{\lceil logn \rceil + 1} - 1$，可以证明这个值是小于4n的，在编程中可以直接用4n代替。

线段树我们先关注其构建、维护、查询三个操作。

构建

我们采用递归的方式构建。给定区间左右端点，我们递归地构建左右子树，如果左右端点相等则停止递归；然后计算所需的区间信息，在本题中就是不包含相邻元素的子序列的最大和。在计算时我们可以利用到子节点的信息，因为我们可以以$O(1)$的时间访问左右子节点。建树的时间复杂度取决于计算区间信息的时间复杂度，由主方法可知，如果可以以$O(1)$的时间完成该操作，即$O(f) = O(1)$ ，那么为$O(logn)$；否则为$O(f)$。

维护

在更改了一个单点信息后，我们需要维护线段树性质。由于这个点的修改只会影响到其祖先节点，我们以二分的思想递归查找到这个点，然后再维护区间信息即可。时间复杂度同上。

查询

本题只查询最大区间，因此$O(1)$时间即可。

推广到更大的范围，如果我们要查找任意一个区间，那么这个区间有可能不是完全和线段树节点的范围一样。我们只需递归地计算其左右区间的值，并相加起来。最后当区间范围完全被查询范围覆盖时，递归结束，直接返回该节点的信息即可。时间复杂度为$O(logn)$。

思路

知道了线段树的数据结构，我们就只差一步之遥，即维护什么样的区间信息。我们发现如果需要用子区间的信息计算出父区间的信息，我们需要左右两个区间分别左右两个端点是否取值时的区间值，运用dp的思想求解。详见代码。其中0表示这个端点不能取到，1表示这个端点可取可不取。可见11可以涵盖所有情况。

复杂度

• 时间复杂度: $O(n + qlogn)$。
• 空间复杂度: $O(n)$，n为数组长度。

Code

class Solution {
    //左右端点四种组合00, 01, 10, 11
    int [][]tree;
    int mod = 1000000007;
    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        int ret = 0;
        int n = nums.length;
        tree = new int[4 * n][4];
        //从1开始
        build(nums, 0, n - 1, 1);
        for (int i = 0; i < queries.length; i++) {
            maintain(0, n - 1, queries[i][0], 1, queries[i][1]);
            ret = (ret + tree[1][3]) % mod;
        }
        return ret;
    }
    public void build(int[] nums, int l, int r, int index){
        if (l == r) {
            tree[index][3] = Math.max(nums[l], 0);
            return;
        }
        // 注意中点位置
        int mid = (l + r) / 2;
        build(nums, l, mid, index * 2);
        build(nums, mid + 1, r, index * 2 + 1);
        calc(index);
    }
    
    //
    public void maintain(int l, int r, int pos, int index, int val) {
        if (l == pos && r == pos) {
            tree[index][3] = Math.max(val, 0);
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) maintain(l, mid, pos, index * 2, val);
        else maintain(mid + 1, r, pos, index * 2 + 1, val);
        calc(index);
    }

    public void calc(int i) {
        int l = 2 * i;
        int r = 2 * i + 1;
        tree[i][0] = Math.max(tree[l][0] + tree[r][2],tree[l][1] + tree[r][0]) % mod;
        tree[i][1] = Math.max(tree[l][1] + tree[r][1],tree[l][0] + tree[r][3]) % mod;
        tree[i][2] = Math.max(tree[l][3] + tree[r][0],tree[l][2] + tree[r][2]) % mod;
        tree[i][3] = Math.max(tree[l][3] + tree[r][1],tree[l][2] + tree[r][3]) % mod;
    }
}