提示：利用线段树解决不包含相邻元素的子序列最大和问题。
文章目录
一、题目描述
给定一个整数数组 nums 和一个二维数组 queries，其中 queries[i] = [posi, xi] 表示将 nums[posi] 的值更新为 xi。对于每次查询，要求重新计算 nums 中不包含相邻元素的子序列的最大和，并返回所有查询结果的累加和。由于累加和可能很大，最后结果需要对 109+7 取模。
示例
示例一：
输入: nums = [3,5,9], queries = [[1,-2],[0,-3]]
输出: 21
解释：
第 1 次查询后，nums = [3, -2, 9]，不包含相邻元素的最大和为 3 + 9 = 12。
第 2 次查询后，nums = [-3, -2, 9]，不包含相邻元素的最大和为 9。
查询的总和为 12 + 9 = 21。
示例二：
输入: nums = [0, -1], queries = [[0, -5]]
输出: 0
解释：
第 1 次查询后，nums = [-5, -1]，不包含相邻元素的最大和为 0（选择空子序列）。
二、解题思路
1.思路分析
题目要求计算 nums 中不包含相邻元素的子序列最大和，这类似于经典的打家劫舍问题，即在一组元素中挑选非相邻的元素，求其和的最大值。问题的难点在于，每次查询需要在更新数组的某个位置后，迅速重新计算整个数组的最大和。若采用暴力的方式重新计算每次的结果，时间复杂度将高达 O(n⋅q)，其中 n 是数组长度，q 是查询次数，这对于数据规模较大的情况来说难以接受。
为了优化时间复杂度，我们可以利用 线段树 的思路。线段树适合解决 区间查询和更新 的问题，可以在对数组某个元素进行修改后，以 O(logn) 的时间复杂度重新计算受影响的部分，从而避免全局计算。
2.线段树的状态设计
我们可以通过四种状态来存储每个区间的最大和：
**f00：**表示左子区间和右子区间都没有选中的最大和。
**f01：**表示左子区间没有选中，右子区间选中的最大和。
**f10：**表示左子区间选中，右子区间没有选中的最大和。
**f11：**表示左子区间和右子区间都选中的最大和。
通过这四种状态，我们可以在合并左右子树时，动态更新区间的最大和。
3.线段树的操作
建树（build）：
初始化线段树时，从叶子节点开始，将数组中的每个元素值填入对应的线段树节点中。
维护（maintain）：
在更新某个元素后，需要重新计算该元素所在区间及其父区间的最大和状态。
更新（update）：
当某个元素发生更新时，只需更新对应的线段树节点，并维护与其相关的父节点状态。
三、代码实现
class Solution(object):
def maximumSumSubsequence(self, nums, queries):
"""
:type nums: List[int]
:type queries: List[List[int]]
:rtype: int
通过线段树维护数组不包含相邻元素的最大和。每次查询只更新受影响的部分，避免全局计算。
"""
MOD = 10**9 + 7 # 用于结果取模
# 线段树节点保存四种状态：f00, f01, f10, f11
n = len(nums)
t = [[0] * 4 for _ in range(2 << n.bit_length())]
# 手写 max 函数提高效率
def max(a, b):
return b if b > a else a
# 合并左右子树的状态，更新当前节点的状态
def maintain(o):
a, b = t[o * 2], t[o * 2 + 1]
t[o][0] = max(a[0] + b[2], a[1] + b[0]) # 左右都没选，取最大值
t[o][1] = max(a[0] + b[3], a[1] + b[1]) # 左没选右选了
t[o][2] = max(a[2] + b[2], a[3] + b[0]) # 左选了右没选
t[o][3] = max(a[2] + b[3], a[3] + b[1]) # 左右都选了
# 初始化线段树
def build(o, l, r):
if l == r: # 叶子节点
t[o][3] = max(nums[l], 0) # 只需考虑当前元素是否大于 0
return
m = (l + r) // 2
build(o * 2, l, m)
build(o * 2 + 1, m + 1, r)
maintain(o) # 合并左右子树的状态
# 更新线段树，修改 nums[i] 为 val
def update(o, l, r, i, val):
if l == r: # 找到叶子节点
t[o][3] = max(val, 0) # 只更新 f11 的值，确保非负
return
m = (l + r) // 2
if i <= m:
update(o * 2, l, m, i, val) # 更新左子树
else:
update(o * 2 + 1, m + 1, r, i, val) # 更新右子树
maintain(o) # 更新父节点状态
# 构建初始线段树
build(1, 0, n - 1)
ans = 0
for i, x in queries: # 遍历每个查询
update(1, 0, n - 1, i, x) # 将 nums[i] 更新为 x
ans += t[1][3] # 每次查询后累加 f11
ans %= MOD # 对结果取模
return ans
代码详细解释
初始化与建树：
我们用 build 函数递归初始化线段树，每个节点存储四种状态，分别表示不同的子序列选择状态。
叶子节点初始化时，根据数组元素值设置状态，若元素为负数，则最大和为 0。
线段树的维护：
maintain 函数用于在修改某个节点后，合并左右子树的状态。我们考虑四种情况：
1.左右子树都不选；
2.左子树不选，右子树选；
3.左子树选，右子树不选；
4.左右子树都选。
处理查询：
每次查询时，通过 update 函数在对应位置更新 nums 数组的值，线段树在更新过程中仅修改受影响的节点及其相关区间。
计算当前查询的结果时，只需取根节点的 f11 值，这代表当前整个数组的最大和。
最终输出：
我们将每次查询的最大和累加，并对结果取模 109+7，保证返回的结果在题目要求范围内。
四、总结
时间复杂度分析
**线段树的初始化：**构建线段树的时间复杂度为 O(n)，其中 n 是数组长度。
**每次查询的复杂度：**由于线段树每次更新的复杂度为 O(logn)，处理每个查询的时间复杂度也是 O(logn)。
**总复杂度：**对于 q 个查询，整个算法的时间复杂度为 O(n+qlogn)，其中 q 是查询次数。
该算法可以有效处理 n 和 q 均为 5104*规模的情况，能够满足时间要求。
通过利用线段树，我们成功地将原问题的暴力解法优化到了 O(n+qlogn) 的时间复杂度，使得在面对大规模数据时依然可以高效地处理。本题展示了线段树在区间查询与更新问题中的强大应用，尤其在需要高效维护复杂状态的情况下，线段树是一种很好的解决方案。
