线段树（Segment Tree）
入门模板题 洛谷oj P3372
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入样例
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例
11
8
20
数据范围
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
才学会写线段树不久……随便扯一篇笔记orz
0x00 线段树概念
线段树是一种二叉搜索树。它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
插入（删除）操作的时间复杂度为O（logn）。
0x01 树形结构及建树
作为一棵树，线段树的结构体大概是这样的：
struct SegmentTree{ //树的结构体
long long l,r; //覆盖的区间的左右指针
long long value; //该节点上维护的值
long long tag; //lazy标记，下面会写到，这也是线段树的精髓
}node[MAX_N*+];
要想建一棵线段树，可以利用线段树是个二叉树的性质，进行递归建树：
void build(REG long long p,REG long long l,REG long long r){ //递归建树
node[p].l=l,node[p].r=r;
if (l==r){ //访问到了最底部，不可再分
node[p].value=read();
return ;
}
long long mid=(l+r)>>;
build(p<<,l,mid);
build((p<<)+,mid+,r);
node[p].value=node[p<<].value+node[(p<<)+].value;
}
这样我们就拥有了一棵树。
0x02 lazy标记（懒标记）
上面提到过，线段树的精髓是lazy标记。不管是要查询还是更改数列，都绕不开它。
如果要修改一段区间（比如同时都增加k），最容易想到的方法是暴力枚举，一个个修改。这样操作m次，最坏时间复杂度是O(mn)。显然是过不去的。
所以我们可以想：如果不修改那么多节点呢？很容易想到，我们只关心查询需要用到的节点——并不是每一个被修改的节点都会在查询中被访问到的。打个比方：假设只有一次修改，一次询问。修改修改[1,16]，而询问只关心[1,8]，那么我们对于[9,16]的修改都是没有意义的。
可以想到，如果点i的两个儿子都要同时增加k，考虑先不修改两个儿子，而给点i打一个标记，标记一下i的两个儿子都要被修改。
如果在下面的询问里要访问到i的两个儿子之一，我们再对i的两个儿子进行修改（或下传标记），再把标记归零。如果两个儿子都会被访问到，就直接取i的值（i点维护的value值是两个儿子节点的和）。
这差不多就是lazy标记的思想，时间复杂度就降到了O(mlogn)。
写一个下传标记的函数：
void push_down(REG const long long& p){
node[p<<].value+=(node[p].tag*(node[p<<].r-node[p<<].l+));
node[(p<<)+].value+=(node[p].tag*(node[(p<<)+].r-node[(p<<)+].l+));
node[p<<].tag+=node[p].tag;
node[(p<<)+].tag+=node[p].tag;
node[p].tag=;
}
按照这样的思想，我们就可以写出线段树了。其他的在最终代码里写了，不再赘述。
0x03 AC代码
#include <cstdio>
#define REG register
#define MAX_N 100000 using namespace std; long long n,m;
long long a[MAX_N+]; long long ch,x,y,z; inline long long read(){ //快速读入
REG long long ch=getchar(),x=,f=;
while (ch<''||ch>''){
if (ch=='-') f=-;
ch=getchar();
} while (ch<=''&&ch>=''){
x=x*+ch-'';
ch=getchar();
}return x*f;
} struct SegmentTree{ //树的结构体
long long l,r;
long long value;
long long tag;
}node[MAX_N*+]; void build(REG long long p,REG long long l,REG long long r){ //递归建树
node[p].l=l,node[p].r=r;
if (l==r){ //访问到了最底部，不可再分
node[p].value=read();
return ;
}
long long mid=(l+r)>>;
build(p<<,l,mid);
build((p<<)+,mid+,r);
node[p].value=node[p<<].value+node[(p<<)+].value;
} void push_down(REG const long long& p){
node[p<<].value+=(node[p].tag*(node[p<<].r-node[p<<].l+));
node[(p<<)+].value+=(node[p].tag*(node[(p<<)+].r-node[(p<<)+].l+));
node[p<<].tag+=node[p].tag;
node[(p<<)+].tag+=node[p].tag;
node[p].tag=; //标记归零
} void change(REG long long p,REG const long long& x,REG const long long& y,REG long long& z){
if (x<=node[p].l&&y>=node[p].r){ //是否完全在区间内
node[p].value+=(z*(node[p].r-node[p].l+));
node[p].tag+=z;
return ;
}
if (node[p].tag) push_down(p); //不完全在区间内，如果有lazy标记，下传
REG long long mid=(node[p].l+node[p].r)>>;
if (x<=mid) change(p<<,x,y,z);
if (y>mid) change((p<<)+,x,y,z);
node[p].value=node[p<<].value+node[(p<<)+].value;
} inline long long ask(REG long long p,REG const long long& x,REG const long long& y){
if (x<=node[p].l&&y>=node[p].r) return node[p].value;
push_down(p);
REG long long mid=(node[p].l+node[p].r)>>;
long long ans=;
if (x<=mid) ans+=ask(p<<,x,y);
if (y>mid) ans+=ask((p<<)+,x,y);
return ans;
} int main(){
// freopen("test1.txt","r",stdin);
n=read(),m=read();
build(,,n);
REG long long ch;
while (m--){
ch=read();
if (ch==){
x=read(),y=read(),z=read();
change(,x,y,z);
}
else{
x=read(),y=read();
printf("%lld\n",ask(,x,y));
}
}
return ;
}
如果写的有哪里不对，欢迎指出，轻喷orz
[参考百度百科及网友讲解]