LeetCode 3165.不包含相邻元素的子序列的最大和：单点修改的线段树（动态规划）

标签：index right 单点 nums int tree 3165 LeetCode left

【LetMeFly】3165.不包含相邻元素的子序列的最大和：单点修改的线段树（动态规划）

力扣题目链接：https://leetcode.cn/problems/maximum-sum-of-subsequence-with-non-adjacent-elements/

给你一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [pos_i, x_i]。

对于每个查询 i，首先将 nums[pos_i] 设置为 x_i，然后计算查询 i 的答案，该答案为 nums 中 不包含相邻元素 的子序列的最大和。

返回所有查询的答案之和。

由于最终答案可能非常大，返回其对 10⁹ + 7 取余的结果。

子序列 是指从另一个数组中删除一些或不删除元素而不改变剩余元素顺序得到的数组。

示例 1：

输入：nums = [3,5,9], queries = [[1,-2],[0,-3]]

输出：21

解释：
执行第 1 个查询后，nums = [3,-2,9]，不包含相邻元素的子序列的最大和为 3 + 9 = 12。
执行第 2 个查询后，nums = [-3,-2,9]，不包含相邻元素的子序列的最大和为 9 。

示例 2：

输入：nums = [0,-1], queries = [[0,-5]]

输出：0

解释：
执行第 1 个查询后，nums = [-5,-1]，不包含相邻元素的子序列的最大和为 0（选择空子序列）。

提示：

1 <= nums.length <= 5 * 10⁴
-10⁵ <= nums[i] <= 10⁵
1 <= queries.length <= 5 * 10⁴
queries[i] == [pos_i, x_i]
0 <= pos_i <= nums.length - 1
-10⁵ <= x_i <= 10⁵

解题方法：线段树 + DP

对于单次操作，我们可以使用分治的方法来求解。对于一个子区间，我们比较关注的有：区间第一个元素是否被选取、区间最后一个元素是否被选取。也就是说，对于一个子区间，一共有以下4种情况：

开头一定不选，结尾一定不选，记为 f 00 f00 f00
开头一定不选，结尾可选(也可不选)，记为 f 01 f01 f01
开头可选(也可不选)，结尾一定不选，记为 f 10 f10 f10
开头可选(也可不选)，结尾可选(也可不选)，记为 f 11 f11 f11

那么对于区间 [ l e f t , r i g h t ] [left, right] [left,right]，如何进行分治操作呢？

如果 l e f t = = r i g h t left==right left==right，那么这个区间就只有一个元素，这个区间的 f 00 = f 01 = f 10 = 0 f00=f01=f10=0 f00=f01=f10=0， f 11 = max ⁡ ( 0 , n u m s [ l e f t ] ) f11=\max(0, nums[left]) f11=max(0,nums[left])。
否则，令 m i d = ⌊ l e f t + r i g h t 2 ⌋ mid = \lfloor\frac{left+right}{2}\rfloor mid=⌊2left+right⌋，递归计算 [ l e f t , m i d ] [left, mid] [left,mid]和 [ m i d + 1 , r i g h t ] [mid + 1, right] [mid+1,right]两个子区间的4个值并汇总得到这个区间的4个值。

假设左区间为 p p p，右区间为 q q q，则汇总方式为：
- f 00 = max ⁡ ( f p 00 + f q 10 , f p 01 + f q 00 ) f00 = \max(f_p00+f_q10, f_p01+f_q00) f00=max(fp00+fq10,fp01+fq00)
- f 01 = max ⁡ ( f p 00 + f q 11 , f p 01 + f q 01 ) f01 = \max(f_p00+f_q11, f_p01+f_q01) f01=max(fp00+fq11,fp01+fq01)
- f 10 = max ⁡ ( f p 10 + f q 10 , f p 11 + f q 00 ) f10 = \max(f_p10+f_q10, f_p11+f_q00) f10=max(fp10+fq10,fp11+fq00)
- f 11 = max ⁡ ( f p 10 + f q 11 , f p 11 + f q 01 ) f11 = \max(f_p10+f_q11, f_p11+f_q01) f11=max(fp10+fq11,fp11+fq01)

那么如何应对 l e n ( q u e r i e s ) len(queries) len(queries)次的修改呢？那就需要引入线段树了。

对于修改操作，使用线段树实现单点修改，线段树的每个节点维护对应区间的4个值
对于查询操作，线段树根节点（整个区间）的 f 11 f11 f11记为所求

时空复杂度分析

时间复杂度 O ( n + q log ⁡ n ) O(n+q\log n) O(n+qlogn)，其中 n = l e n ( n u m s ) n=len(nums) n=len(nums)， q = l e n ( q u e r i e s ) q=len(queries) q=len(queries)
空间复杂度 O ( n ) O(n) O(n)

AC代码

C++

const unsigned int mod = 1e9 + 7;

class Solution {
private:
    vector<array<unsigned int, 4>> tree;  // 00, 01, 10, 11

    void maintain(int index) {
        int leftIndex = 2 * index + 1;
        int rightIndex = 2 * index + 2;
        tree[index] = {
            max(tree[leftIndex][1] + tree[rightIndex][0], tree[leftIndex][0] + tree[rightIndex][2]),
            max(tree[leftIndex][0] + tree[rightIndex][3], tree[leftIndex][1] + tree[rightIndex][1]),
            max(tree[leftIndex][2] + tree[rightIndex][2], tree[leftIndex][3] + tree[rightIndex][0]),
            max(tree[leftIndex][2] + tree[rightIndex][3], tree[leftIndex][3] + tree[rightIndex][1])
        };
    }

    void buildTree(vector<int>& nums, int index, int left, int right) {
        if (left == right) {
            tree[index] = {0, 0, 0, (unsigned int)max(nums[left], 0)};
            return;
        }
        int mid = (left + right) / 2;
        buildTree(nums, 2 * index + 1, left, mid);
        buildTree(nums, 2 * index + 2, mid + 1, right);
        maintain(index);
    }

    void update(int index, int left, int right, int modifiedI, int val) {
        if (left == right) {
            tree[index][3] = max(0, val);
            return;
        }
        int mid = (left + right) / 2;
        if (modifiedI <= mid) {
            update(2 * index + 1, left, mid, modifiedI, val);
        } else {
            update(2 * index + 2, mid + 1, right, modifiedI, val);
        }
        maintain(index);
    }
public:
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        tree.resize(nums.size() * 4);
        buildTree(nums, 0, 0, nums.size() - 1);
        unsigned int ans = 0;
        for (vector<int>& query : queries) {
            update(0, 0, nums.size() - 1, query[0], query[1]);
            ans = (ans + tree[0][3]) % mod;
        }
        return ans;
    }
};

Python

from typing import List

MOD = 1_000_000_007
class Solution:
    def maintain(self, index: int) -> None:
        leftNode = self.tree[2 * index + 1]
        rightNode = self.tree[2 * index + 2]
        self.tree[index] = [
            max(leftNode[0] + rightNode[2], leftNode[1] + rightNode[0]),
            max(leftNode[0] + rightNode[3], leftNode[1] + rightNode[1]),
            max(leftNode[2] + rightNode[2], leftNode[3] + rightNode[0]),
            max(leftNode[2] + rightNode[3], leftNode[3] + rightNode[1])
        ]
    
    def build(self, index: int, left: int, right: int) -> None:
        if left == right:
            self.tree[index][3] = self.nums[left]
            return
        mid = (left + right) >> 1
        self.build(2 * index + 1, left, mid)
        self.build(2 * index + 2, mid + 1, right)
        self.maintain(index)

    def update(self, index: int, left: int, right: int, modifiedI: int, val: int) -> None:
        if left == right:
            self.tree[index][3] = max(0, val)
            return
        mid = (left + right) >> 1
        if modifiedI <= mid:
            self.update(2 * index + 1, left, mid, modifiedI, val)
        else:
            self.update(2 * index + 2, mid + 1, right, modifiedI, val)
        self.maintain(index)

    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        self.tree = [[0, 0, 0, 0] for _ in range(len(nums) * 4)]  # 00, 01, 10, 11
        self.nums = nums
        self.build(0, 0, len(nums) - 1)
        ans = 0
        for q, v in queries:
            self.update(0, 0, len(nums) - 1, q, v)
            ans = (ans + self.tree[0][3]) % MOD
        return ans

Java

class Solution {
    private long[][] tree;  // 诶，如果不是long的话会有两组数据无法通过
    private final int mod = 1000000007;

    private void maintain(int index) {
        long[] leftNode = tree[2 * index + 1];
        long[] rightNode = tree[2 * index + 2];
        tree[index][0] = Math.max(leftNode[0] + rightNode[2], leftNode[1] + rightNode[0]);
        tree[index][1] = Math.max(leftNode[0] + rightNode[3], leftNode[1] + rightNode[1]);
        tree[index][2] = Math.max(leftNode[2] + rightNode[2], leftNode[3] + rightNode[0]);
        tree[index][3] = Math.max(leftNode[2] + rightNode[3], leftNode[3] + rightNode[1]);
    }

    private void build(int[] nums, int index, int left, int right) {
        if (left == right) {
            tree[index][3] = Math.max(0, nums[left]);
            return;
        }
        int mid = (left + right) / 2;
        build(nums, 2 * index + 1, left, mid);
        build(nums, 2 * index + 2, mid + 1, right);
        maintain(index);
    }

    private void update(int index, int left, int right, int modifiedI, int val) {
        if (left == right) {
            tree[index][3] = Math.max(0, val);
            return;
        }
        int mid = (left + right) / 2;
        if (modifiedI <= mid) {
            update(2 * index + 1, left, mid, modifiedI, val);
        } else {
            update(2 * index + 2, mid + 1, right, modifiedI, val);
        }
        maintain(index);
    }

    public int maximumSumSubsequence(int[] nums, int[][] queries) {
        tree = new long[4 * nums.length][4];  // 00, 01, 10, 11
        build(nums, 0, 0, nums.length - 1);
        long ans = 0;
        for (int[] query : queries) {
            update(0, 0, nums.length - 1, query[0], query[1]);
            ans = (ans + tree[0][3]) % mod;
        }
        return (int)ans;
    }
}

Go

package main

type data struct {
    _00 int
    _01 int
    _10 int
    _11 int
}

type seg []data

func max(a int, b int) int {
    if a >= b {
        return a
    }
    return b
}

func maintain(tree seg, index int) {
    leftNode := tree[index * 2 + 1]
    rightNode := tree[index * 2 + 2]
    tree[index] = data{
        max(leftNode._00 + rightNode._10, leftNode._01 + rightNode._00),
        max(leftNode._00 + rightNode._11, leftNode._01 + rightNode._01),
        max(leftNode._10 + rightNode._10, leftNode._11 + rightNode._00),
        max(leftNode._10 + rightNode._11, leftNode._11 + rightNode._01),
    }
}

func build(tree seg, nums []int, index int, left int, right int) {
    if left == right {
        tree[index]._11 = max(0, nums[left])
        return
    }
    mid := (left + right) >> 1
    build(tree, nums, 2 * index + 1, left, mid)
    build(tree, nums, 2 * index + 2, mid + 1, right)
    maintain(tree, index)
}

func update(tree seg, index int, left int, right int, modified int, val int) {
    if left == right {
        tree[index]._11 = max(0, val)
        return
    }
    mid := (left + right) >> 1
    if modified <= mid {
        update(tree, 2 * index + 1, left, mid, modified, val)
    } else {
        update(tree, 2 * index + 2, mid + 1, right, modified, val)
    }
    maintain(tree, index)
}

func maximumSumSubsequence(nums []int, queries [][]int) int {
    tree := make(seg, len(nums) * 4)
    build(tree, nums, 0, 0, len(nums) - 1)
    ans := 0
    for _, query := range queries {
        update(tree, 0, 0, len(nums) - 1, query[0], query[1])
        ans = (ans + tree[0]._11) % 1_000_000_007
    }
    return ans
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143452715

标签：index,right,单点,nums,int,tree,3165,LeetCode,left
From： https://blog.csdn.net/Tisfy/article/details/143452715