线段树(Segment Tree),一种基于二叉搜索树的数据结构,通过将子问题进行简单的合并从而高效地解决问题(log2)

用结构体存储线段树
const int MAXN=100000;//节点数
int sav[MAXN+1];//存储初始值
int Mod,N,M;
struct node {
int val,plus,times;//plus存储加法lazytag,times存乘法
} a[4*MAXN+1];
建立一棵树(左右儿子递归)
void build(int k,int l,int r) {
a[k].times=1;
a[k].plus=0;
if(l==r) {
a[k].val=sav[l]%Mod;
return;
}
int mid=(l+r)>>1;//不要打错>>和l,r
build(k<<1,l,mid);
build((k<<1)+1,mid+1,r);
a[k].val=(a[k<<1].val+a[(k<<1)+1].val)%Mod;//建完树要更新当前节点的值=(左儿子+右儿子)
return;
}
※lazytag下传操作
void pushdown(int k,int l,int r) {
int mid=(l+r)>>1;
a[k<<1].val=(a[k<<1].val*a[k].times+a[k].plus*(mid-l+1))%Mod;
a[(k<<1)+1].val=(a[(k<<1)+1].val*a[k].times+a[k].plus*(r-mid))%Mod;
//更改左右儿子的值,注意(mid-l+1)与(r-mid)
a[k<<1].times=a[k].times*a[k<<1].times%Mod;
a[(k<<1)+1].times=a[k].times*a[(k<<1)+1].times%Mod;
a[k<<1].plus=(a[k<<1].plus*a[k].times+a[k].plus)%Mod;
a[(k<<1)+1].plus=(a[(k<<1)+1].plus*a[k].times+a[k].plus)%Mod;
//更改左右儿子的lazytag,注意先乘除再加减,乘法lazytag直接乘
//加法lazytag先将父亲的乘法lazytag应用后再加上父亲的加法lazytag
a[k].plus=0;
a[k].times=1;
return;
}
加法更新区间
void update_add(int k,int nl,int nr,int l,int r,int val) {
if(nl>r||nr<l)return;
if(nr<=r&&nl>=l) {
a[k].plus=(a[k].plus+val)%Mod;//直接加
a[k].val=(a[k].val+val*(nr-nl+1))%Mod;//不要忘记更新值,有多少个儿子就加多少次
return;
}
pushdown(k,nl,nr);//注意先下传
int mid=(nl+nr)>>1;
update_add(k<<1,nl,mid,l,r,val);
update_add((k<<1)+1,mid+1,nr,l,r,val);//mid+1
a[k].val=(a[k<<1].val+a[(k<<1)+1].val)%Mod;//不要忘记更新值
return;
}
乘法更新区间
void update_mul(int k,int nl,int nr,int l,int r,int val) {
if(nr<l||nl>r)return;
if(nr<=r&&nl>=l) {
a[k].val=a[k].val*val%Mod;//直接更新
a[k].times=a[k].times*val%Mod;
a[k].plus=a[k].plus*val%Mod;
return;
}
pushdown(k,nl,nr);//还是先下传
int mid=(nl+nr)>>1;
update_mul(k<<1,nl,mid,l,r,val);
update_mul((k<<1)+1,mid+1,nr,l,r,val);
a[k].val=(a[k<<1].val+a[(k<<1)+1].val)%Mod;//还是不要忘记更新值
return;
}
区间查询
int query(int k,int l,int r,int target_l,int target_r) {
if(target_l>r||target_r<l)return 0;//越界
if(target_l<=l&&target_r>=r) {
return a[k].val%Mod;//包含
}
pushdown(k,l,r);//先更新
int mid=(l+r)>>1;//再分治
return (query(k<<1,l,mid,target_l,target_r)+query((k<<1)+1,mid+1,r,target_l,target_r))%Mod;
}
用法
build(1,1,N);//建立一棵树
query(1,1,N,x,y);//查询x->y区间的数值和
update_add(1,1,N,x,y,val)//将x->y区间加上一个val
update_mul(1,1,N,x,y,val)//将x->y区间都乘val
2020.8.28 UPDATE 整合SegmentTree
struct SegTree {
#define ls(x) (x<<1)
#define rs(x) (x<<1)+1
#define ll long long
struct node {
ll sum,lazy,max,min;
int l,r;
};
const static int MAXN = 100010;
node a[4*MAXN+5];
inline void swap(int &a,int &b) {
int c=a;
a=b,b=c;
}
inline ll max(ll &a,ll &b) {
return a>b?a:b;
}
inline ll min(ll &a,ll &b) {
return a>b?b:a;
}
inline void pushup(int &k) {
a[k].sum=a[ls(k)].sum+a[rs(k)].sum;
a[k].max=max(a[ls(k)].max,a[rs(k)].max);
a[k].min=min(a[ls(k)].min,a[rs(k)].min);
}
inline void pushdown(int &k) {
if(a[k].lazy==0)return;
a[ls(k)].sum+=a[k].lazy*(a[ls(k)].r-a[ls(k)].l+1);
a[rs(k)].sum+=a[k].lazy*(a[rs(k)].r-a[rs(k)].l+1);
a[ls(k)].lazy+=a[k].lazy,a[rs(k)].lazy+=a[k].lazy;
a[ls(k)].max+=a[k].lazy,a[rs(k)].max+=a[k].lazy;
a[ls(k)].min+=a[k].lazy,a[rs(k)].min+=a[k].lazy;
a[k].lazy=0;
}
void build(int k,int l,int r,ll *sav) {
a[k].l=l,a[k].r=r;
if(l==r) {
a[k].sum=a[k].max=a[k].min=sav[l];
return;
}
int mid=l+r>>1;
build(ls(k),l,mid,sav);
build(rs(k),mid+1,r,sav);
pushup(k);
}
void query(int k,int l,int r,ll &dist,short op) {
/*
op = 0 query sum
1 query max
2 query min
*/
if(a[k].l>=l&&a[k].r<=r) {
if(op==0)
dist+=a[k].sum;
if(op==1)
dist=max(dist,a[k].max);
if(op==2)
dist=min(dist,a[k].min);
return;
}
pushdown(k);
int mid=(a[k].l+a[k].r)>>1;
if(l<=mid)query(ls(k),l,r,dist,op);
if(r>mid)query(rs(k),l,r,dist,op);
}
void add(int k,int l,int r,ll &x) {
if(a[k].l>=l&&a[k].r<=r) {
a[k].sum+=x*(a[k].r-a[k].l+1);
a[k].max+=x,a[k].min+=x;
a[k].lazy+=x;
return;
}
pushdown(k);
int mid=(a[k].r+a[k].l)>>1;
if(l<=mid)add(ls(k),l,r,x);
if(r>mid)add(rs(k),l,r,x);
pushup(k);
}
} T;

No responses yet