线段树，坑害萌新，码粮金人
线段树不是算法，应该是一种工具。她能把一些对于区间（或者线段）的修改、维护，从O(N)的时间复杂度变成O（logN）。
线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
线段树的查询方法：
-
如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
-
如果这个区间的左儿子和目标区间有交集，那么搜索左儿子
-
如果这个区间的右儿子和目标区间有交集，那么搜索右儿子
区间求和就是运用的这个逻辑：
ll query(ll q_x,ll q_y,ll l,ll r,ll p){//区间求和，[q_x,q_y]为目标区间，[l,r]为当前区间 ,小心函数内部变量重复
ll sum = 0;
if(q_x <= l && r <= q_y){
return ans[p];
}
ll mid = (l + r) >> 1;
push_down(p,l,r);
if(q_x <= mid){
sum += query(q_x,q_y,l,mid,lc(p));
}
if(q_y > mid){
sum += query(q_x,q_y,mid + 1,r,rc(p));
}
return sum;
}
向下传递：
inline void push_down(ll p,ll l,ll r){//每次更新两个子节点，然后继续传递
ll mid = (l + r) >> 1;
f(lc(p),l,mid,t[p]);
f(rc(p),mid + 1,r,t[p]);
t[p] = 0;
}
向上维护：
inline void push_up(ll p){// 向上不断维护区间操作
ans[p] = ans[lc(p)] + ans[rc(p)];
}
左右儿子：
inline ll lc(ll x){//left chrildren 左儿子
return x << 1;
}
inline ll rc(ll x){//right chrildren 右儿子
return x << 1 | 1;//二进制位左移一位代表着数值*2，而如果左移完之后再或上1，由于左移完之后最后一位二进制位上一定会是0，所以|1等价于+1。
}
区间修改(单点修改就是长度是一的区间修改)：
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k){ //l,r为要修改的区间,nl,nr,p为当前节点所存储的区间以及节点的编号
if(nl <= l && r <= nr){
ans[p] += (r - l + 1) * k;
t[p] += k;//懒标记
return;
}
push_down(p,l,r);
ll mid = (l + r) >> 1;
if(nl <= mid){
update(nl,nr,l,mid,lc(p),k);
}
if(nr > mid){
update(nl,nr,mid + 1,r,rc(p),k);
}
push_up(p);
}
以上学会之后就可以去P3372了，因为以上代码选自P3372。
哦，还有建树：
void build(int i,int l,int r){
if(l==r){
tree[i]=a[i];
return ;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(i);
}
现在，我们已经讲完了单点修改，区间修改，区间查询，单点查询，左右儿子，向上回溯，建树。好像都讲完了吧(bushi)。
时间复杂度如下：
数据上传 O ( 1 ) O(1) O(1)
建树 O ( n ) O(n) O(n)
标记下传 O ( 1 ) O(1) O(1)
单点/区间修改 O ( log n ) O(log n) O(logn)
单点/区间查询 O ( log n ) O(log n) O(logn)
懒标记：
一般是区间修改才会用到的。懒标记顾名思义，就是一个特别懒的东西，只有在你需要它的时候，它才会出现；当我们对区间修改时，如果一个个的修改，那么复杂度爆炸，显然不可以；这时懒标记的作用就体现了，对每个区间加一个懒标记，标志着这个区间是否进行了修改，如果进行了，那么它的子区间也要进行修改，并且把懒标记转给子结点（因为子结点的子区间也要修改）
讲了这么多，能用在哪里？
只要信息维护满足结合律，就可以使用线段树。
一些好东西：
浅谈线段树
线段树入门
关于线段树上的一些进阶操作
浅谈权值线段树到主席树
线段树合并：从入门到放弃
区间最值操作与区间历史最值详解
