一：定义
首先要明确线段树的定义，线段树是一颗树，而且是完全二叉树。同时线段树的每个节点表示一个区间，左子树和右子树分别表示这个区间的左半边和右半边。
即将区间[L,R]分解成[L,MID]和[MID+1,R]，假设根的高度为1,树高为
下图展示了区间[1,13]的分解过程
二：原理
上图中每个节点存储自己对应区间的信息。
（1）单点修改
假设要修改1号节点，不难发现只要修改[1,13]、[1,7]、[1,4]、[1,2]、[1,1]这几个节点的信息，也就是更新1号节点到根节点的这条链上的所有信息
所以最大修改次数就是树的高度
（2）区间查询
我们可以将一个[1,n]的线段树分成若干个连续不相交区间，嗯大概是
详细证明可以参考
（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); }