「学习笔记」线段树
线段树，
一个现代 \(OIer\) 最为熟知 的数据结构，
也代表着 \(OIer\) 从 普及 到 提高 的转变。
正题：
1.建树
线段树是一棵典型的二叉树，
它可以在 \(O(\log n)\) 级别的时间复杂度内实现 单点修改、区间修改、区间查询（求和，求最大值，求最小值） 等操作。
与 树状数组 不同，
树状数组的结构是基于 \(lowbit\) 操作 的；
而线段树的结构则是基于 二分操作。
并且，线段树中划分出的区间的作用与树状数组 完全一样：
储存此区间的贡献值。
于是，我们每次对当前节点的两个儿子进行递归，直到叶子结点为止；
而叶子节点的值就代表原数组上相应编号的值；
递归结束以后，当前节点的贡献就是由两个儿子的贡献合并而来（这叫做 \(pushup\) 操作）。
时间复杂度：\(O(\log n)\)。
因此，有建树代码：
#define ls rt<<1
#define rs rt<<1|1
//左儿子和右儿子的宏定义
inline void pushup(int rt) //合并左右儿子的贡献值
{
sum[rt]=sum[ls]+sum[rt*2+1];
// maximum[rt]=max(maximum[ls],maximum[rs]);
// minimum[rt]=min(minimum[ls],minimum[rs]);
}
void build(int l,int r,int rt)
{
if(l==r)
{
sum[rt]=a[l];
// maximum[rt]=a[l];
// minimum[rt]=a[l];
return;
}
int mid=l+((r-l)>>1); //二分
build(l,mid,ls);
build(mid+1,r,rs);
pushup(rt);
}
2. 查询
如果要查询的区间为 \((2,6)\)，
此时就不能直接获取区间的值，
但是 \((2,6)\) 可以拆成 \((2,4)\) 和 \((5,6)\)，
可以通过合并这两个区间的答案来求得这个区间的答案。
一般地，
如果要查询的区间是 \((l,r)\)，
则可以将其拆成最多为 \(O(\log n)\) 个 极大的区间，
合并这些区间即可求出 \((l,r)\) 的答案。
根据这个 “合并定理”，可以得出以下查询程序：
#define ls rt<<1
#define rs rt<<1|1
//左儿子和右儿子的宏定义
int query(int l,int r,int rt,int que_l,int que_r)
{
if(que_l<=l&&r<=que_r) //已经包含，直接返回
return sum[rt];
else if(rque_r)
return 0;
int mid=l+((r-l)>>1),res=0;
pushdown(l,r,rt); //此处暂且不用管，下文会提到
if(que_l<=mid)
res+=query(l,mid,ls,que_l,que_r);
if(mid 3. 修改 \(\operatorname{and}\) 懒惰标记优化
如果要求修改区间 \((l,r)\)，
把所有包含在区间中的节点都遍历一次、修改一次，
时间复杂度 显然无法承受。
我们这里要引入一个叫做 “懒惰标记” 的东西。
懒惰标记，
简单来说，就是通过延迟对节点信息的更改，
从而减少可能不必要的操作次数。
每次执行修改时，
我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改，
但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。
我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个 \(tag_i\)，表示该节点带的标记值。
举个栗子：
最开始时的情况是这样的：
现在我们准备给 \((3,5)\) 上的每个数都加上 \(5\)。
根据前面区间查询的经验，
我们很快找到了两个极大区间 \((3,3)\) 和 \((4,5)\)（分别对应线段树上的 \(3\) 号点和 \(5\) 号点）。
我们直接在这两个节点上进行修改，并给它们打上标记：
我们发现，\(3\) 号节点的信息虽然被修改了（因为该区间管辖两个数，所以 \(d_3\) 加上的数是 \(5\times 2=10\)），
但它的两个子节点却还没更新，仍然保留着修改之前的信息。
不过不用担心，虽然修改目前还没进行，
但当我们要查询这两个子节点的信息时，
我们会利用标记修改这两个子节点的信息，使查询的结果依旧准确。
接下来我们查询一下 \((4,4)\) 区间上各数字的和。
我们通过递归找到 \((4,5)\) 区间，发现该区间并非我们的目标区间，
且该区间上还 存在标记。
这时候就到 标记下传 的时间了。
我们将该区间的两个子区间的信息更新，并清除该区间上的标记。
现在 \(6\)、\(7\) 两个节点的值变成了最新的值，查询的结果也是准确的。
接下来给出在存在标记的情况下，区间修改和查询操作的参考实现。
#define ls rt<<1
#define rs rt<<1|1
//左右儿子的宏定义
void Add(int l,int r,int rt,int val) //打上懒标记
{
lazy[rt]+=val; //懒标记
sum[rt]+=val*(r-l+1);
}
void pushdown(int l,int r,int rt) //下传懒标记
{
if(!lazy[rt])
return;
int mid=l+((r-l)>>1);
Add(l,mid,ls,lazy[rt]);
Add(mid+1,r,rs,lazy[rt]);
lazy[rt]=0;
}
void update(int l,int r,int rt,int upd_l,int upd_r,int val)
{
if(upd_l<=l&&r<=upd_r)
{
Add(l,r,rt,val);
return;
}
int mid=l+((r-l)>>1);
pushdown(l,r,rt);
if(upd_l<=mid)
update(l,mid,ls,upd_l,upd_r,val);
if(upd_r>mid)
update(mid+1,r,rs,upd_l,upd_r,val);
pushup(rt);
// maximum[rt]=max(maximum[rt*2],maximum[rt*2+1]);
// minimum[rt]=min(minimum[rt*2],minimum[rt*2+1]);
}
int query(int l,int r,int rt,int que_l,int que_r)
{
if(que_l<=l&&r<=que_r) //已经包含，直接返回
return sum[rt];
else if(rque_r)
return 0;
int mid=l+((r-l)>>1),res=0;
pushdown(l,r,rt); //懒标记下传操作
if(que_l<=mid)
res+=query(l,mid,ls,que_l,que_r);
if(mid 4. 小优化
-
在叶子节点处 无需下放懒惰标记，所以懒惰标记 可以不下传到叶子节点。
-
标记 永久化：如果确定懒惰标记不会在中途被加到 数据溢出（超过了该类型能表示的最大范围），那么就可以将标记 永久化。标记永久化可以 避免下传懒惰标记，只需在进行询问时 把标记的影响加到答案中，从而 降低程序常数（本文所有程序都没有这个优化，
请放心）。
总结：
线段树是一个用途 极其广泛 的数据结构，用它来维护区间信息是一个明智之举；
当然，在遇到 仅需 单点修改与区间查询等 简单区间操作 的题目，
请选择树状数组。