一：定义
首先要明确线段树的定义，线段树是一颗树，而且是完全二叉树。同时线段树的每个节点表示一个区间，左子树和右子树分别表示这个区间的左半边和右半边。
即将区间[L,R]分解成[L,MID]和[MID+1,R]，假设根的高度为1,树高为(n>1)
下图展示了区间[1,13]的分解过程
二：原理
上图中每个节点存储自己对应区间的信息。
（1）单点修改
假设要修改1号节点，不难发现只要修改[1,13]、[1,7]、[1,4]、[1,2]、[1,1]这几个节点的信息，也就是更新1号节点到根节点的这条链上的所有信息
所以最大修改次数就是树的高度
（2）区间查询
我们可以将一个[1,n]的线段树分成若干个连续不相交区间，嗯大概是
详细证明可以参考https://www.cnblogs.com/AC-King/p/7789013.html
（3）区间修改
朴素算法：把区间内的每个点单点修改（好像有那么一点点...暴力）
那该怎么办呢，这时候一个神奇的东西出现了——懒惰标记（Lazy tag）
我们把对节点的修改情况储存在标记里，在访问一个节点的时候，“顺便”把它的标记传递给它的儿子节点，也就是懒惰标记的下放。
实现思路（重点）
<1>增加一个新的变量用来存储Lazy tag
<2>递归到这个节点时，只更新这个节点的状态，并把当前的更改值累积到标记里
<3>当需要递归这个节点的子节点的时候，标记下传给子节点
①当前节点的懒惰标记累积到子节点的懒惰标记中
②修改子节点状态（原状态+子节点区间大小*父节点传下来的懒惰标记）
③父节点懒惰标记清零
三：代码实现
const int MAXN=50010;
int a[MAXN],ans[MAXN<<2],lazy[MAXN<<2];
//a[]为原序列信息，ans[]模拟线段树维护区间和，lazy[]为懒惰标记
void PushUp(int rt)
{
ans[rt]=ans[rt<<1]+ans[rt<<1|1];
}
void Build(int l,int r,int rt)
{
if (l==r)
{
ans[rt]=a[l];
return;
}
int mid=(l+r)>>1;
Build(l,mid,rt<<1);
Build(mid+1,r,rt<<1|1);
PushUp(rt);
}
void PushDown(int rt,int ln,int rn)//ln表示左子树元素结点个数，rn表示右子树结点个数
{
if (lazy[rt])
{
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
ans[rt<<1]+=lazy[rt]*ln;
ans[rt<<1|1]+=lazy[rt]*rn;
lazy[rt]=0;
}
}
void Add(int L,int C,int l,int r,int rt)
{
if (l==r)
{
ans[rt]+=C;
return;
}
int mid=(l+r)>>1;
//PushDown(rt,mid-l+1,r-mid); 若既有点更新又有区间更新，需要这句话
if (L<=mid)
Add(L,C,l,mid,rt<<1);
else
Add(L,C,mid+1,r,rt<<1|1);
PushUp(rt);
}
void Update(int L,int R,int C,int l,int r,int rt)
{
if (L<=l&&r<=R)
{
ans[rt]+=C*(r-l+1);
lazy[rt]+=C;
return;
}
int mid=(l+r)>>1;
PushDown(rt,mid-l+1,r-mid);
if (L<=mid) Update(L,R,C,l,mid,rt<<1);
if (R>mid) Update(L,R,C,mid+1,r,rt<<1|1);
PushUp(rt);
}
LL Query(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
return ans[rt];
int mid=(l+r)>>1;
PushDown(rt,mid-l+1,r-mid);//若更新只有点更新，不需要这句
LL ANS=0;
if (L<=mid) ANS+=Query(L,R,l,mid,rt<<1);
if (R>mid) ANS+=Query(L,R,mid+1,r,rt<<1|1);
return ANS;
}
int main()
{
//建树
Build(1,n,1);
//点更新
Add(L,C,1,n,1);
//区间修改
Update(L,R,C,1,n,1);
//区间查询
int ANS=Query(L,R,1,n,1);
}