[高级数据结构]线段树SegmentTree
知道你没耐心看完，先一边听歌一边把模板抄一遍，你会懂的
刚学了线段树
下面对灵神的模板解释一下
结构讲解
线段树是一个完全二叉树，我们用数组模拟存储
node是什么
整棵树的根节点是1
- 当前根节点编号为
node - 左子树的根节点为
node<<1（node*2） - 右子树的根节点为
node<<1|1（node*2+1）
node如何对应原数组区间
node=1表示整棵树的根，它管理的区间是[0, n-1]node=2是左子树，它管理 根区间 的左半部分[0, mid]node=3是右子树，它管理 根区间 的右半部分[mid+1, n-1]
依次递归，每个node 代表一个子区间
- 当前根节点
node，管理区间[l,r]，中点int m=l+r>>1; - 左子树根节点
node<<1，管理区间[l,m] - 右子树根节点
node<<1|1，管理区间[m+1,r]
注意
每个node对应的区间[l,r]是固定的 但是我们在写函数的时候要用到很多递归，自己预处理一个node与区间的映射太麻烦了，所以就把l,r当做参数传递了
最朴素的模板
晕递归的同学，直接把递归调用看做他宏观整体上实现了这个功能，不要细究里面具体怎么实现的
#include<bits/stdc++.h>
using namespace std;template<typename T>//T会自动推导变量类型，T的作用域只在这个class内 其他地方还可以用T当做变量名
class SegmentTree{
private:int n;vector<T>tree;T merge_val(T a,T b) {//合并两个值return max(a,b);//根据题目修改,可能是区间和或者最小值}void maintain(int node){//根据左右子节点的值更新当前作为父结点的node的值tree[node]=merge_val(tree[node<<1],tree[node<<1|1]);}void build(vector<T>&a,int node,int l,int r){if(l==r){//找到叶子节点，可以直接赋值了tree[node]=a[l];return;}int m=l+r>>1;build(a,node<<1,l,m);build(a,node<<1|1,m+1,r);maintain(node);//递归建完左右子树后，要更新当前根节点的值}void update(int node,int l,int r,int i,T val){if(l==r){//找到叶子节点 直接更新//这里也根据题目修改 想直接替换就直接赋值为valtree[node]=merge_val(tree[node],val);return;}int m=l+r>>1;if(i<=m){update(node<<1,l,m,i,val);}else{update(node<<1|1,m+1,r,i,val);}maintain(node);//递归更新左右子树后，要更新当前根节点的值}T query(int node,int l,int r,int ql,int qr){if(ql<=l&&r<=qr){//当前子树完全被查询范围包含，[l,r]是[ql,qr]的子集，直接返回return tree[node];}int m=l+r>>1;if(qr<=m){//查询区间[ql,qr]在node的左子树return query(node<<1,l,m,ql,qr);}if(ql>m){//查询区间[ql,qr]在node的右子树return query(node<<1|1,m+1,r,ql,qr);}//如果到这里还没return，说明ql<=m<=qr//ql,qr在m的两边T l_res=query(node<<1,l,m,ql,qr);T r_res=query(node<<1|1,m+1,r,ql,qr);return merge_val(l_res,r_res);}public://写了两个构造函数SegmentTree(int n,T init_val): SegmentTree(vector<T>(n,init_val)){}SegmentTree(vector<T>&a): n(a.size()),tree(4*a.size()){//开四倍空间build(a,1,0,n-1);//数组，根节点，对应的区间(就是整个数组)}void update(int i,T val){update(1,0,n-1,i,val);//根节点，对应的区间(就是整个数组)，i为原数组的下标，需要更新的值}T query(int ql,int qr){return query(1,0,n-1,ql,qr);//根节点，对应的区间(就是整个数组)，查询区间}T get(int i){return query(1,0,n-1,i,i);//根节点，对应的区间(就是整个数组)，单点查询}
};
int n;
vector<int>a(n);
SegmentTree t(a);
常见应用
min,max,gcd,lcm,sum,xor- 维护区间内符合某种条件的 元素个数
懒标记LazyTag
- 懒标记就是用来延迟更新数组每个点具体的值
在访问子树之前要把懒标记分配下去 - 访问左右子树之前需要spread
- 子树的根上的 todo(懒标记) 代表整个子树里所有点需要增加的量，但这个增量还没有真正作用到子树的 val 上，只有当 spread 被调用时，才会把这个 todo 传播到左右子树，并更新它们的 val 和 todo
- 当子树变化(update&query)之后 必须马上maintain更新根节点
- spread后不需要maintain ：
-
- spread是从根节点向子节点传播懒标记 只是把原本应该由父节点计算的影响，转移到子节点，并不影响父节点在当前状态下的正确性
- 记住update&query后面要maintain
- apply最后merge_todo
- spread最后重置todo
模板
#include<bits/stdc++.h>
using namespace std;template<typename T, typename F>
class LazySegmentTree{//求区间和
private:const F TODO_INIT=0;//懒标记初始值 根据题目修改struct Node{T val;F todo;};int n;vector<Node>tree;T merge_val(T a,T b){return a+b;//求区间和 两个值直接相加}F merge_todo(F a,F b){return a+b;//合并懒标记 因为求区间和 懒标记直接加在点上 所以懒标记可以直接相加合并}//把懒标记作用在node子树 更新val ”在当前子树做任务“void apply(int node,int l,int r,F todo){Node& cur=tree[node];//先把这个子树的总体val更新了 因为很容易得到cur.val+=todo*(r-l+1);//区间长度*每个点增量//具体数组每个点的值用懒标记叠加上 下一行就是在合并懒标记cur.todo=merge_todo(todo,cur.todo);}//把当前节点的懒标记传递给左右子树 “给下属分派任务”void spread(int node,int l,int r){ Node& cur=tree[node];F todo=cur.todo;if(todo==TODO_INIT){//没有懒标记 就returnreturn;}//根节点的懒标记 就是下面的子节点需要更新的增量int m=l+r>>1;apply(node<<1,l,m,todo);//分治递归更新apply(node<<1|1,m+1,r,todo);cur.todo=TODO_INIT;//下传完毕 重置根节点的懒标记}void maintain(int node){//维护根节点的值tree[node].val=merge_val(tree[node<<1].val,tree[node<<1|1].val);}void build(vector<T>&a,int node,int l,int r){Node& cur=tree[node];cur.todo=TODO_INIT;//记得初始化懒标记if(l==r){cur.val=a[l];return;}int m=l+r>>1;build(a,node<<1,l,m);build(a,node<<1|1,m+1,r);maintain(node);}void update(int node,int l,int r,int ql,int qr,F f){if(ql<=l&&r<=qr){apply(node,l,r,f);return;}//先把任务分派下去 才能更新下面的值spread(node,l,r);int m=l+r>>1;//这里是跟朴素版本不一样的if(ql<=m){//目标区间有一部分在m左边 递归更新左子树update(node<<1,l,m,ql,qr,f);}if(qr>m){//目标区间有一部分在m右边 递归更新右子树update(node<<1|1,m+1,r,ql,qr,f);}maintain(node);}T query(int node,int l,int r,int ql,int qr){if(ql<=l&&r<=qr){return tree[node].val;}//访问子树之前要spreadspread(node,l,r);int m=l+r>>1;if(qr<=m){//目标区间在左子树return query(node<<1,l,m,ql,qr);}if(ql>m){//目标区间在右子树return query(node<<1|1,m+1,r,ql,qr);}//目标区间跨m的左右两边T l_res=query(node<<1,l,m,ql,qr);T r_res=query(node<<1|1,m+1,r,ql,qr);return merge_val(l_res,r_res);}public:LazySegmentTree(int n,T init_val=0) :LazySegmentTree(vector<T>(n,init_val)){}LazySegmentTree(vector<T>&a) : n(a.size()),tree(4*a.size()){build(a,1,0,n-1);}//用f更新[ql,qr]中的每个a[i]void update(int ql,int qr,F f){update(1,0,n-1,ql,qr,f);}T query(int ql,int qr){return query(1,0,n-1,ql,qr);}};
int n;
vector<int>a(n);
LazySegmentTree<int,int> t(a);//要自己写明类型