题目大意
给定一个数列，有如下操作：
- 将区间 $[l,r]$ 上的数乘上 $x$
- 将区间 $[l,r]$ 上的数加上 $x$
- 询问区间 $[l,r]$ 上的数之和
分析
很经典的线段树教学题，写完后对线段树的理解确实更深了。
从一次函数的角度考虑问题感觉更清晰。我们实际上在对每个序列上的值做一次函数
$$ f_i(x) = k_i x + m_i $$
先来看本题线段树的结构
template <class T>
struct SegmentTree {
vector<Seg> tr;
void pushup(int p);
void pushdown(int p);
void build(int l, int r, int p = 1);
void modify(int l, int r, T k, T m, int p = 1);
T query(int l, int r, int p = 1);
};
懒标记：在知道一段当前值的情况下，可以立刻知道该段被操作后的值，不必重新计算所有的数。因此可以把当前的操作存起来，询问的时候再对子节点做真实操作。
真实操作也称永久化，操作后懒标记就被下放子节点。懒标记意味着当前节点已经完成了永久化，子节点没有完成，故询问子节点值前需要更新。
- pushup：当 $p$ 的子节点被改变时，需要用此方法对节点 $p$ 的值进行更新。
- pushdown：当询问 $p$ 的子节点的值时，如果 $p$ 节点有懒标记，则下放到 $p$ 的子节点。
- modify：对所有在 $[l,r]$ 区间内的节点做永久化，并打上懒标记。
- query：询问在 $[l,r]$ 区间内的节点。
当子节点懒标记上已经有值时，下放标记需要合并，即是函数复合。
$$ f_i(f_j(x)) = a_i(a_j x + b_j) + b_i = a_ia_j x + a_i b_j + b_i $$