算法详解——线段树

1. 线段树介绍

线段树是一个高度平衡二叉树，它主要用来高效动态地管理一个序列。线段树叶子结点存储序列元素值，分支结点存储一个连续地子区间的某种聚合信息，例如最值、均值等信息。

如图所示：

用这样一个树状结构来管理序列有什么好处？

1. 快速地查询某个区间范围，时间复杂度为O(logn)
2. 快速修改某个元素的值并更新分支结点，时间复杂度为O(logn)
3. 打上延迟标记之后，可以快速修改某个范围的元素值

线段树的主要操作包括：

1. 构建线段树
   构建线段树的时间复杂度为 O(n)O(n)O(n)，通常是递归构建：

• 如果区间只有一个元素，那么该节点是叶子节点，直接存储该元素的值。
• 如果区间有多个元素，则将区间一分为二，递归构建左右子树，节点值为左右子树值的组合。

2. 区间查询
   查询操作的时间复杂度为 O(log⁡n)O(\log n)O(logn)：

• 如果查询的区间完全覆盖当前节点区间，则直接返回该节点的值。
• 如果查询的区间与当前节点区间部分重叠，则递归查询左右子树，并将左右子树的结果组合。

3. 区间更新
   更新操作的时间复杂度同样为 O(log⁡n)O(\log n)O(logn)：

• 如果更新区间完全覆盖当前节点区间，则更新当前节点的值。
• 如果更新区间与当前节点区间部分重叠，则递归更新左右子树，并将左右子树的结果组合更新当前节点的值。

2. 算法实战

题目如下：

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

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

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

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

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

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

分析：如果题目只是单纯的求不包含相邻元素的子序列的最大和，那么该题解法就类似于198.打家劫舍，使用动态规划即可解决。但是题目中给了多次查询，每次查询都会改变序列中一个元素的值，这意味着每次查询都需要从头开始进行计算，显然会超时。

我们可以注意到，如果序列中xi的值被改变，那么其两边子区间的解是不变的，也就是说，我们可以存储许多个子区间的解，当某个元素被修改时只需要更新相应的子区间即可，大大减少计算量。

这样一分析，可以选择使用线段树来保存和维护这些子区间。

使用线段树涉及到如何根据两个子结点的值计算父结点的值，也就是如何合并两个区间的解。如果xi被选择，则xi-1和xi+1都不能被选择，因此合并两个区间时我们需要知道两个区间左右两边的结点是否被选择了。

2.1 定义线段树结点的结构体

首先定义线段树结点的结构体:

struct SegNode
{
    long long best()
    {
        return v11;
	}
    
    void set(long long value)
    {
        v00 = v01 = v10 = 0;
        // v11代表的可选可不选，因此如果value为负数就不选
        v11 = max(value, 0LL);
    }
    
    long long v00, v01, v10, v11;
};

其中v00代表两边结点都不被选择的情况下啊区间的解，而v01则代表左结点不被选择、右结点可选择也可不选择的情况下啊的区间解，v10和v11的含义以此类推。

2.2 定义线段树的主要操作

// 合并两个子区间
void pushup(vector<SegNode> &tree, int x)
{
	const SegNode &left = tree[2 * x];
	const SegNode &right = tree[2 * x + 1];
    tree[x].v00 = max(left.v01 + right.v00, left.v00 + right.v10);
    tree[x].v10 = max(left.v11 + right.v00, left.v10 + right.v10);
    tree[x].v01 = max(left.v01 + right.v01, left.v00 + right.v11);
    tree[x].v11 = max(left.v11 + right.v01, left.v10 + right.v11);
}

// 初始化线段树
void segtree_init(vector<SegNode> &tree, vector<int> &nums, int x, int l, int r)
{
    if (l == r)
    {
        tree[x].set(nums[l - 1]);
        return;
    }
    int mid = (l + r) / 2;
    segtree_init(tree, nums, 2 * x, l, mid);
    segtree_init(tree, nums, 2 * x + 1, mid + 1, r);
    
    pushup(tree, x);
}

// 更新某个元素
void update(vector<SegNode> &tree, int x, int l, int r, int pos, int value)
{
   if (l == r)
   {
       tree[x].set(value);
       return;
   }
   else
   {
       int mid = (l + r) / 2;
       if (pos <= mid)
           update(tree, 2 * x, l, mid, pos, value);
       else
           update(tree, 2 * x + 1, mid + 1, r, pos, value);     
       
        pushup(tree, x);
   }
}

线段树的主要操作还包括查询某个子区间，但是本题只需要全局的解。

2.3 利用线段树解题

class Solution {
public:
    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
      	// 由于元素个数不一定组成一个满二叉树，所以线段树的结点总数可能超过2 * n
        vector<SegNode> tree(4 * n + 1);
        segtree_init(tree, nums, 1, 1, n);
        constexpr int mod = 1e9 + 7;
        int ans = 0;
        for (auto &q : queries)
        {
			update(tree, 1, 1, n, q[0] + 1, q[1]);
            ans = (tree[1].best() + ans) % mod;
        }
        return ans;
        
    }
};