应用情况
线段树非常通用，是基于分治思想的二叉树。区间查询问题一般都可以试试（一般没有没有单点查询的），有单点修改和区间修改。有些问题甚至可以离散化转换成区间问题。（待验证。）
值域线段树的重要误区
值域线段树以值本身作为下标，值的出现次数存在线段树里。值域线段树和普通的线段树的区别只是用例的使用方式的区别，而根据这种不同的应用方式才把这类线段树分类叫做值域线段树而已。因此线段树的内部实现丝毫不受影响。因此在开发值域线段树时一定封装，不受用例的使用方式的干扰，而时刻注意线段树提供的接口。
接口设计
- 添加和删除往往可以合并，只是正负的问题
- 询问全局的答案也就是询问root节点的答案
内部实现的总设计思路
既然是分治思想的线段树，查什么，保存什么（通常），再存一下分治合并时需要的信息即可。区间被完全覆盖的优化是时间复杂度的保证，因此思考查询与修改时区间被完全覆盖、和非完全覆盖合并时的两种情况如果更新，当然也可以考虑子节点（优先考虑叶节点）如何更新父节点。一定记住叶节点一定被完全覆盖。实现时一定铭记向下递归一定是有选择性的操作 。
综上：
- 查什么，保存什么。思考叶节点储存的信息
- 思考父节点如何由子节点更新而来，考虑额外的维护信息
- 考虑修改查询操作的完全覆盖和非完全覆盖（深知叶节点一定被覆盖）
具体实现
- 建树。常常我们会对一个区间建树。
//这是扫描线的代码
void build(int u, int e, int o)
{
l[u]=e; r[u]=o; //左右端点赋值
if(e==o-1) return; //判叶节点
umid; //向下递归
build(ul, e, mid);
build(ur, mid, r);
}
- 区间操作：判断操作区间与当前节点区间的包含关系：完全覆盖，非完全覆盖（传标记，左右选择递归，合并更新）
//这是扫描线的代码
void modi(int u, int e, int o, int d)
{
//既然是分治的线段树结构 ，查什么，保存什么。
//区间被完全覆盖的优化是时间复杂度的保证。
//一定是有选择性的操作
if(e<=l[u]&&r[u]<=o) times[u]+=d; //被覆盖
else //没被覆盖，讨论下递归
{
umid;
if(e<=mid) modi(ul, e, mid, d);
if(o>mid) modi(ur, mid, r, d);
}
//合并更新
if(times[u]) width[u] = raw[r[u]] - raw[l[u]];
else width[u] = width[ul] + width[ur];
}
//这是区间求和的板子，
int query(int p, int e, int o)
{
if(e<=l[p]&&r[p]<=o) //先判断完全覆盖
return sum[p];
//非完全覆盖
spread(p); //有标记时先下传，选择性的合并
pmid;
int ans = 0;
if(e<=mid) ans+= query(pl, e, o);
if(o>mid) ans+= query(pr,e,o);
return ans;
}
- 单点修改：叶节点直接修改更新，其他节点选一边递归下去再合并更新。
各种不同维护信息的例题模板
- 区间乘加，区间求和
- 区间并
- 求区间最值
下面还有亟待解决的更难问题，也代表了即将学习平衡树和树套树。
曾老的OJ上有许多例题。
灵活多变的线段树
实际上线段树非常灵活：可以维护离散的序列，也可以维护真正的一维几何区间（例如扫描线）。
空间限制
可以动态开点和线段树合并，势能分析可得总体复杂度是线性对数的。
也可以离散化（貌似就不能在线了）。
正在更新
带着走还是储存边界？
如果没有初值，那就懒得建树，那我就直接带着走算了
