区间最值覆盖与历史最值查询

题目

区间最值覆盖与历史最值查询

信息

• 类型：问答
• 难度：⭐⭐⭐

考点

线段树延迟更新,双延迟标记设计,区间覆盖操作,历史最值维护

快速回答

本题要求设计一个支持区间覆盖、查询当前最大值和查询历史最大值的线段树。核心解决方案包括：

• 每个节点维护四个值：当前最大值、历史最大值、当前延迟标记、历史最大延迟标记
• 使用双延迟标记策略：一个记录当前覆盖值，另一个记录历史最大覆盖值
• 更新时同步更新当前值和历史值：历史最大值 = max(原历史最大值, 新值)
• 标记下传时，子节点的历史最大值需用父节点的历史最大标记更新

问题描述

设计数据结构支持以下操作：

1. update(l, r, v)：将区间 [l, r] 覆盖为值 v
2. current_max(l, r)：查询区间当前最大值
3. historical_max(l, r)：查询区间历史最大值（从初始化至今出现过的最大值）

核心难点

• 覆盖操作会改变区间值，影响历史最值
• 延迟更新时需维护历史状态
• 多操作叠加时需保证历史值正确性

数据结构设计

class SegmentTreeNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.current_max = -10**9  # 当前最大值
        self.hist_max = -10**9     # 历史最大值
        self.lazy_current = None   # 当前覆盖标记
        self.lazy_hist = -10**9    # 历史最大覆盖标记

关键操作实现

1. 更新操作（核心）

def update(node, l, r, v):
    if node.r < l or node.l > r: return

    if l <= node.l and node.r <= r:
        # 更新当前值和历史值
        node.current_max = v
        node.hist_max = max(node.hist_max, v)
        # 更新延迟标记
        node.lazy_current = v
        node.lazy_hist = max(node.lazy_hist, v)
        return

    push_down(node)  # 关键：下传标记

    mid = (node.l + node.r) // 2
    if l <= mid: update(node.left, l, r, v)
    if r > mid: update(node.right, l, r, v)

    push_up(node)  # 合并子节点信息

2. 标记下传（最复杂部分）

def push_down(node):
    if node.lazy_current is None: return

    # 更新左子节点
    node.left.hist_max = max(node.left.hist_max, node.lazy_hist)
    node.left.current_max = node.lazy_current
    node.left.lazy_hist = max(node.left.lazy_hist, node.lazy_hist)
    node.left.lazy_current = node.lazy_current

    # 更新右子节点（同上）
    ...

    # 重置父节点标记
    node.lazy_current = None

3. 查询操作

def query(node, l, r, is_historical=False):
    if node.r < l or node.l > r: 
        return -10**9
    if l <= node.l and node.r <= r:
        return node.hist_max if is_historical else node.current_max

    push_down(node)  # 确保数据最新

    mid = (node.l + node.r) // 2
    left_val = query(node.left, l, r, is_historical)
    right_val = query(node.right, l, r, is_historical)
    return max(left_val, right_val)

最佳实践

• 双标记设计：必须分开维护当前标记和历史标记
• 更新顺序：先更新历史值再更新当前值
• 下传策略：用父节点的历史标记更新子节点的历史值
• 边界处理：使用哨兵值（如 -10⁹）初始化

常见错误

• 错误1：仅用单标记，导致历史值丢失
• 错误2：下传时未用历史标记更新子节点历史值
• 错误3：未在查询前执行 push_down
• 错误4：未正确处理覆盖操作的传递性

复杂度分析

扩展知识

• 混合操作：支持同时存在区间加和区间覆盖的场景
• 多维历史值：维护历史最小值、历史总和等
• 动态开点：处理值域巨大的场景
• 应用场景：游戏成就系统（历史最高分）、网络质量监控（历史最大延迟）