核心概述
常值区间以“整段同值”的抽象表示区间 [l,r) 上值恒定，可在区间赋值/查询中配合懒标记实现对整段的 O(1) 命中与 O(log n) 更新。
原文引述
Description: Represents a segment [l,r) with a constant value. Used for lazy propagation in segment trees, interval assignment, and range queries where the whole interval has the same value. ——来源：本节点英文注释 Time: O(1) creation; O(log n) with segment tree for range assignment/query ——来源：本节点英文注释 Status: tested ——来源：本节点英文注释
展开阐述
-
数据结构（据实现）
- struct ConstRange {
- ll l, r; // 区间 [l, r)
- ll value; // 区间上的恒定值
- bool valid; // 是否有效（未被覆盖） }
- 或作为线段树节点扩展：
- struct Node { ll val; bool is_const; }；区间覆盖时直接赋值并标记 is_const。
- struct ConstRange {
-
基本操作
- 构造：ConstRange(l, r, v)。
- 合并：若两相邻区间值相同，可合并为更大区间。
- 分裂：按位置将区间拆分成子区间。
- 覆盖：将区间标记为无效，被新覆盖的常值区间替代。
-
延迟标记应用（线段树）
- 区间赋值：若节点完全在目标区间内，直接 set(val) 并标记 is_const，不递归。
- 递归时先 pushdown：若当前节点有常值标记，下推到左右子节点并清除标记。
- 查询：若节点有常值标记，直接返回该值；否则递归合并子节点结果。
-
优势
- 区间赋值 O(log n)，无需逐点更新。
- 查询时若命中常值标记，O(1) 返回。
- 大幅减少递归深度与操作次数。
-
应用场景
- 区间赋值、区间覆盖问题。
- 差分约束、染色问题。
- 并查集的区间合并（加权并查集）。
- 字符串批量替换（区间字符统一）。
-
实现注意
- 标记下推（pushdown）时需更新子节点的值与标记。
- 合并操作需处理标记优先级（常值标记优先于加法标记等）。
- 边界条件：空区间、单点区间需特殊处理。
-
与其他结构关系
- 可作为 006-数据结构-懒标记线段树、012-数据结构-线段树 的优化。
- 与 015-数据结构-并查集 结合实现区间并查集。