006-数据结构-懒标记线段树

核心概述：支持区间赋值与区间加法两种懒标记，并提供区间最大值查询的线段树；构建与单次操作均摊 O(log N)。

原文引述：

Description: Segment tree with ability to add or set values of large intervals, and compute max of intervals. Time: O(\log N). Usage: Node* tr = new Node(v, 0, sz(v));

展开阐述：

• 定义与问题背景、适用场景
  • 在线维护数组的区间更新（加法或覆盖）与区间最大值查询，适用于区间打标、区间增量、区间赋值的综合场景。
  • 相比 003-数据结构-树状数组 仅支持加/前缀和，本结构以懒标记处理更复杂的区间操作与“取 max”的聚合。
• 接口与数据结构字段说明（据实现）
  • 节点定义：Node { Node* l, r; int lo, hi, mset = inf, madd = 0, val = -inf; }，常量 inf=1e9。
    • lo, hi：节点覆盖的半开区间 [lo, hi)；
    • val：该区间内元素的最大值；
    • mset：延迟赋值标记，默认 inf 表示无效；一旦有效表示整段应被设置为某值；
    • madd：延迟加法标记；
    • l, r：左右子指针（按需分配）。
  • 构造：
    • Node(lo, hi)：建立空区间，val 初始为 -inf；
    • Node(v, lo, hi)：自底向上构建，叶节点取 v[lo]，父节点 val=max(左.val,右.val)。
  • 操作：
    • query(L, R)：查询 [L,R) 的最大值；先 push() 确保懒标记应用到子树。
    • set(L, R, x)：将 [L,R) 赋值为 x；整段命中则 mset=val=x 并清空 madd，部分覆盖则下推后递归并回溯更新。
    • add(L, R, x)：将 [L,R) 加 x；整段命中时优先累加到 mset（若存在），否则累加到 madd，同时更新 val；部分覆盖同理。
• 核心算法流程/要点
  • push() 懒标记传播：
    • 若子节点不存在则按当前 [lo,hi) 对半创建；
    • 传播优先级：先处理 mset（覆盖）再处理 madd（叠加）。当 mset 有效时，子节点直接被覆盖并清空其 add；然后再将 madd 传播。
  • 维护不变式：val 始终是当前节点区间的最大值；任意时刻对子树的访问前先 push()，保证查询与递归正确。
• 复杂度与边界条件
  • set/add/query 均为 O(log N)；在指针式按需建树下，可处理大坐标（隐式树）。
  • 区间采用半开 [L,R)，务必与调用方语义一致，避免 off-by-one。
• 实现细节与坑
  • 覆盖 vs 加法的叠加顺序：覆盖应重置先前的加法影响；整段赋值后再加法才生效，需要在 push()/整段命中时维持该优先级。
  • 懒标记的清空与更新：命中整段时，mset=val=x 且 madd=0；整段加法时，若 mset 有效则 mset+=x，同时 val+=x，否则仅 madd+=x、val+=x。
  • 动态开点：仅在访问到子节点时分配，可节省内存。
• 变体/扩展
  • 将聚合函数由 max 改为 min/sum 需同步调整 val 的维护、单位元与懒标记组合方式。
  • 结合“线性分配器 BumpAllocator/SmallPtr”可进一步优化常数（文件注释有提示）。
• 正确性要点
  • 懒标记优先级保证覆盖语义正确；每次递归前 push() 保证子树状态与 val 一致，从而使区间查询和更新互相可交换地进行。

关联节点

• 012-数据结构-线段树
• 003-数据结构-树状数组
• 004-数据结构-二维树状数组