线段树详解
背景：在普及水到一等，提高水到二等的NOIp2018结束后，滑稽的小宫不满足于简单的暴搜（用暴搜骗了至少150分），决定学习更高级的算法
线段树（水）
这是一种神奇的数据结构，用蒟蒻语说，就是“树状区间和”，即将一个二分过程表现出来。通过改变大区间的值，来实现短时区间计算
如图：
1 - 8
/ \
1 - 4 5 - 8
/ \ / \
1-2 3 - 4 5-6 7-8
/ \ / \ / \ / \
1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 重点是，时间复杂度只有O(logn)！
（蒟蒻开始考虑自己已经多久没有见过logn的算法了）
不水了，进入正题
众所周知，拿数组存树是有“左右孩子定理”的。
因此通过某种高大上朴素的做法就可以轻易繁琐地求出左右孩子
先定义
#include<cstdio>
#define left_son(x) (x<<1)//某种神秘方法
#define right_son(x) (x<<1|1)//某种神秘方法2
#define ll long longps：为了更好理解我用了很长的函数和数组名，密恐慎入
在线段树中，我们用到三个主要函数：建树、操作、查询，还有一个辅助函数“下推”。
我在这里用的是结构体做法（实际是因为不会动态开点），定义了一个结构体“st”（segment tree的简称），里面存有它的左端点、右端点、当前值和lazy标记。注意，空间范围最好开到n的4倍（前辈的经验）。
首先是建树操作，可以看到，我们能利用递归建树，每次二分就行了，事实上，线段树就是还原了一个二分的过程
二分代码：
//毫无作用的二分
void div（int l,int r）{
if(l==r)return;
int mid=(l+r)/2;
div(l,mid);
div(mid+1,r);
}如果想要把它变成建树操作，还需要加上这个位置的节点，以便赋值，这时我们就用那个神秘的找孩子函数实现：
拿二分改成建树函数代码：
void build(ll x,ll li,ll ri){
st[x].left_point=li;//定义左孩子
st[x].right_point=ri;//定义右孩子
if(li==ri){//若相同，说明已经走到叶子结点
st[x].sum=a[li];//只有叶子结点被真实赋值
return;
}
//如果没到叶子结点，就继续二分
ll mid=(li+ri)/2;
build(left_son(x),li,mid);
build(right_son(x),mid+1,ri);
//二分完毕，在调用返回时把中间结点的值算出
st[x].sum=st[left_son(x)].sum+st[right_son(x)].sum;
}好了，先放出上面的那张图
//数字为区间端点下标
1 - 8
/ \
1 - 4 5 - 8
/ \ / \
1-2 3-4 5-6 7-8
/ \ / \ / \ / \
1-1 2-2 3-3 4-4 5-5 6-6 7-7 8-8 或者是
|1 - 16|
|1 - 8|9 - 16|
|1 - 4|5 - 8|9 - 12|13 - 16|
|1-2|3-4|5-6|7-8|9-10|11-12|13-14|15-16|
|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|那么如何修改元素呢？这里用加法举个例子。我继续使用二分，从根开始，往下分。题目中会给出要增加的区间，那么如果我们二分出了区间，就不用管了，因为这一部分不需要加上数。（比如我要在3-5区间加数，但是二分到了1-2区间，这时就要退出了，反正我也不加）但是如果是一部分有交集时怎么办（如加3-5，分到1-4）？这时就要有一些方法了。一言以蔽之：
继续分！
我们一直向下分，直到分到左右端点都在所需范围之中
void plus(ll x,ll li,ll ri,ll v){
if(st[x].left_point>ri||st[x].right_point<li)return;//出了范围，跳出
if(st[x].left_point>=li&&st[x].right_point<=ri){//都在范围中
st[x].lazy+=v;//暂时先忽略
st[x].sum+=(st[x].right_point-st[x].left_point+1)*v;//真实增值
return;
}
push_down(x);//暂时忽略
plus(left_son(x),li,ri,v);//二分
plus(right_son(x),li,ri,v);//二分
st[x].sum=st[left_son(x)].sum+st[right_son(x)].sum;//在递归调用返回时将父节点值改变
}这样，可以提供一次添加服务的函数已经写完。但是，已修改节点的祖先修改了，而子孙没有修改，这该怎么办呢？
有人说，可以从已修改节点向下递归，把下面节点都修改，但是这样时间会到达nlogn，得不偿失。
于是，lazy标记应运而生。lazy是用来标识当前区间每一个节点需要加上的值，当再进行操作时经过某一点，就可以把这一点的lazy值往下推，一直到叶子节点。时间复杂度仅为O(1)。
void push_down(ll x){
st[left_son(x)].sum+=(st[left_son(x)].right_point-st[left_son(x)].left_point+1)*st[x].lazy;
//将当前节点的左孩子的sum值加上当前节点的lazy乘上左孩子的区间长度
st[right_son(x)].sum+=(st[right_son(x)].right_point-st[right_son(x)].left_point+1)*st[x].lazy;
//将当前节点的右孩子的sum值加上当前节点的lazy乘上右孩子的区间长度
st[left_son(x)].lazy+=st[x].lazy;
//将lazy标记向左下推
st[right_son(x)].lazy+=st[x].lazy;
//将lazy标记向右下推
st[x].lazy=0;
//已经加完，归零
}如图：
这是lazy标记下推
这是sum值下推
所以我们利用lazy标记就解决了复杂度太高的问题，一句话总结，就是：在需要向下搜索时再把值向下推，不用就不推。
以此类推，当我们需要查找时，就用一样的道理
ll find(ll x,ll li,ll ri){
if(st[x].left_point>ri||st[x].right_point<li)return 0;
//如果搜索出范围了，就停止
if(st[x].left_point>=li&&st[x].right_point<=ri){
return st[x].sum;//边界，搜索区间完全在范围内，返回sum值
}
push_down(x);//别忘了在向下查找之前下推
return find(left_son(x),li,ri)+find(right_son(x),li,ri);//二分搜索
}至此，整个线段树我们就写完了（省略主函数）
线段树是我自学习OI以来遇到的第一个高级算法，心里还是很激动的，就写了这篇题解来记录它（也是我目前写过的最长的题解了）
完整代码（P3372）
#include<cstdio>
#define left_son(x) (x<<1)
#define right_son(x) (x<<1|1)
#define ll long long
struct segment_tree{
ll left_point,right_point,sum,lazy;
}st[400010];
ll n,m,a[100010];
void build(ll x,ll li,ll ri){
st[x].left_point=li;
st[x].right_point=ri;
if(li==ri){
st[x].sum=a[li];
return;
}
ll mid=(li+ri)/2;
build(left_son(x),li,mid);
build(right_son(x),mid+1,ri);
st[x].sum=st[left_son(x)].sum+st[right_son(x)].sum;
}
void push_down(ll x){
st[left_son(x)].sum+=(st[left_son(x)].right_point-st[left_son(x)].left_point+1)*st[x].lazy;
st[right_son(x)].sum+=(st[right_son(x)].right_point-st[right_son(x)].left_point+1)*st[x].lazy;
st[left_son(x)].lazy+=st[x].lazy;
st[right_son(x)].lazy+=st[x].lazy;
st[x].lazy=0;
}
void plus(ll x,ll li,ll ri,ll v){
if(st[x].left_point>ri||st[x].right_point<li)return;
if(st[x].left_point>=li&&st[x].right_point<=ri){
st[x].lazy+=v;
st[x].sum+=(st[x].right_point-st[x].left_point+1)*v;
return;
}
push_down(x);
plus(left_son(x),li,ri,v);
plus(right_son(x),li,ri,v);
st[x].sum=st[left_son(x)].sum+st[right_son(x)].sum;
}
ll find(ll x,ll li,ll ri){
if(st[x].left_point>ri||st[x].right_point<li)return 0;
if(st[x].left_point>=li&&st[x].right_point<=ri){
return st[x].sum;
}
push_down(x);
return find(left_son(x),li,ri)+find(right_son(x),li,ri);
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);
for(int i=1;i<=m;i++){
ll sign,x,y,k;
scanf("%lld",&sign);
if(sign==1){
scanf("%lld%lld%lld",&x,&y,&k);
plus(1,x,y,k);
}else{
scanf("%lld%lld",&x,&y);
printf("%lld\n",find(1,x,y));
}
}
return 0;
}