求支持O(logn)复杂度的区间更新与最长非递减序列查询方案

问题描述 #

给定初始全为1、长度为n的数组，支持两种操作：

• Increase(x, y, m)：将区间[x,y]内的所有元素增加m（1≤x≤y≤n）；
• Give(x, y)：返回区间[x,y]内最长非递减子序列的长度。

示例：输入n=5，执行Increase 1 2 3后数组变为[4,4,1,1,1]，执行Give 2 4时返回最长长度2。

原思路尝试将数组转换为相邻元素差值数组（如[1,4,2,5]转为[0,3,-2,3]），通过维护差值为负的位置集合划分非递减区间，但Give操作最坏仍为O(n)复杂度，寻求优化方案使得两种操作均为O(logn)时间复杂度。

优化方案：线段树维护区间状态 #

要实现两种操作的O(logn)复杂度，核心是用线段树维护每个区间的关键状态信息，而非单纯记录负差值的位置。每个线段树节点需要存储以下核心字段：

• len：当前区间的最长非递减子序列（LNDS）长度
• prefix_len：从区间左端开始的最长非递减前缀长度
• suffix_len：以区间右端结束的最长非递减后缀长度
• left_val：区间左端元素的当前值
• right_val：区间右端元素的当前值
• add_tag：区间加法延迟标记（用于批量处理区间增减操作）

具体操作实现 #

1. Increase(x, y, m) 区间增减操作

这是标准的区间更新操作，通过线段树的延迟标记机制高效处理：

• 遍历线段树，定位到所有完全覆盖[x,y]的节点，更新节点的left_val和right_val（直接加上m），同时将节点的add_tag累加m。
• 延迟标记会在后续查询或更新操作时向下传递，确保子节点的数值和状态同步更新，整个过程的时间复杂度为O(logn)。

2. Give(x, y) 最长非递减子序列查询操作

查询区间[x,y]的LNDS时，需要将该区间拆分为线段树中的O(logn)个节点，然后合并这些节点的状态得到最终结果：

• 合并两个相邻子区间A和B时：
  • 如果A的right_val ≤ B的left_val，则合并后的区间LNDS长度为 max(A.len, B.len, A.suffix_len + B.prefix_len)
  • 否则，合并后的LNDS长度为 max(A.len, B.len)
  • 合并后的前缀长度：若A的前缀长度等于A的区间长度，且A的右端值≤B的左端值，则为A.prefix_len + B.prefix_len，否则直接取A.prefix_len
  • 合并后的后缀长度：若B的后缀长度等于B的区间长度，且A的右端值≤B的左端值，则为B.suffix_len + A.suffix_len，否则直接取B.suffix_len
• 依次合并所有拆分出的节点状态，最终得到目标区间的LNDS长度，整个查询过程时间复杂度为O(logn)。

优化原理 #

原思路仅记录负差值的位置，查询时需要遍历这些位置计算连续非递减段的长度，最坏情况下（比如数组整体递减）会退化为O(n)时间。而线段树通过预维护每个区间的LNDS相关状态，合并时直接复用子节点的预计算结果，完全避免了遍历操作，确保每次查询和更新都稳定在O(logn)复杂度。

内容的提问来源于stack exchange，提问作者Donald