线段树

相关概念

线段树中的每个节点对应一个区间 $[l,\ r]$ ，

区间端点 $l$ 和 $r$ 的值其实维护在函数参数中，如：

void build(int l, int r, int rt);
void upd(int L, int R, int val, int l, int r, int rt);
int qry(int L, int R, int l, int r, int rt);

$l$ 和 $r$ 表示编号 $rt$ 的节点所对应的区间 $[l, r]$

因此 $l$ 和 $r$ 实际上可以为负数，只要其能代表一个区间。

子节点对应区间分别为 $[l, m]$ 和 $[m+1, r]$ ， $m$ 为 $l + r » 1$

子节点编号分别为 $rt « 1$ 和 $rt « 1 \vert 1$

节点信息通常用结构体数组存储：

struct { int sum, len, lazy; } t[N<<2]

空间需要开区间长度 $N$ 的 $4$ 倍，原因在于大于 $2$ 的幂次的部分会多用节点编号。

可构建一棵区间长度为 $9$ 的线段树体会。

节点信息一般分为：

如：区间和，区间最值，区间异或和，区间 $GCD$ 等，需满足区间可加性。

即：根据两个子区间的信息，可以推导出合并区间后的信息。

一般在函数结尾时合并。

t[rt].sum = op(t[ls].sum, t[rs].sum);

涉及区间更新时，需要用到延迟标记，以保证复杂度。

本质为，暂存下对于某个区间的多次更新的操作，

当需要查询该区间的子区间时，能够对子区间一次性完成所有更新。

前提：区间查询的结果满足区间可加性。
列出关于区间修改的表达式
1. 列出关于单点修改的表达式
  \[x_i = F(x_i)\]
2. 列出关于区间修改的表达式
  \[sum(l, r) = F(\ sum(l, r)\ )\]
3. 列出重复在同一区间上修改 $k$ 次的表达式
  \[sum(l, r) = F(\ sum(l, r),\ k\ )\]
4. 包含有 $k$ 的部分即为延迟标记需要维护的部分
  \[sum(l, r) = F(\ lazy(k),\ sum(l, r)\ )\]
$build(1, n, 1)$ 中初始化 “待查询信息” 与 “延迟标记信息”
区间更新 $upd(l, r, val, 1, n, 1)$
1. $Add(rt, val)$ 可看作一次 $pushdown$ ，将更新内容作用到对应节点，
  
  更新结点所维护的待查询信息和延迟标记。
区间查询 $qry(l, r, 1, n, 1)$

深入理解延迟标记： HDU 6562 Lovers