首页 > 代码库 > 线段树可维护的基本信息
线段树可维护的基本信息
一、区间最值
1.单点替换：
1 const int M=100001; 2 LL a[M]; 3 LL MAX[M<<2]; 4 #define lson l,m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 void update(int rt){ 7 MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]); 8 } 9 void build(int l,int r,int rt){ 10 if (l==r) { 11 MAX[rt]=a[l]; 12 return; 13 } 14 int m=(l+r)>>1; 15 build(lson); 16 build(rson); 17 update(rt); 18 } 19 void modify(int l,int r,int rt,int p,int v){ 20 if (l==r) { 21 MAX[rt]=v; 22 return; 23 } 24 int m=(l+r)>>1; 25 if (p<=m) modify(lson,p,v); 26 else modify(rson,p,v); 27 update(rt); 28 } 29 30 int query(int l,int r,int rt,int nowl,int nowr) { 31 if (nowl<=l && r<=nowr) return MAX[rt]; 32 int ans=INT_MIN; 33 int m=(l+r)>>1; 34 if (nowl<=m) ans=max(ans,query(lson,nowl,nowr)); 35 if (m<nowr) ans=max(ans,query(rson,nowl,nowr)); 36 return ans; 37 }
2.区间增减：当一段区间整体增加（减少）某一个定值时，这段区间的最值也同时增大（减小）这个值，可参照区间和中区间增减的代码。
二、区间和
区间和是线段树可维护的最基本的信息，其他所有线段树可维护的序列信息，都是以区间和为模板建立的。
1.单点增减、单点替换：
1 #define lson l,m,rt<<1 2 #define rson m+1,r,rt<<1|1 3 void update(int rt){ 4 sum[rt]=sum[rt<<1]+sum[rt<<1|1];//sum[rt]表示rt节点所包含的区间信息，此处为区间和 5 } 6 void build(int l,int r,int rt){ //构造线段树 7 if (l==r) { 8 sum[rt]=a[l]; 9 return; 10 } 11 int m=(l+r)>>1; 12 build(lson); 13 build(rson); 14 update(rt); 15 } 16 void modify(int l,int r,int rt,int p,LL v){ //将p位置修改为v 17 if (l==r) { 18 sum[rt]=v;//如果是将p位置的数+v,则此句应为sum[rt]+=v; 19 return; 20 } 21 int m=(l+r)>>1; 22 if (p<=m) modify(lson,p,v); 23 else modify(rson,p,v); 24 update(rt); 25 } 26 27 LL query(int l,int r,int rt,int nowl,int nowr) { //询问[nowl,nowr]的信息 28 if (nowl<=l && r<=nowr) return sum[rt]; 29 LL ans=0; 30 int m=(l+r)>>1; 31 if (nowl<=m) ans+=query(lson,nowl,nowr); 32 if (m<nowr) ans+=query(rson,nowl,nowr); 33 return ans; 34 }
2.区间增减、区间替换：（测试：洛谷P3372）
1 const int M=100001; 2 LL a[M]; 3 LL sum[M<<2],lazy[M<<2]; 4 #define lson l,m,rt<<1 5 #define rson m+1,r,rt<<1|1 6 void update(int rt){ 7 sum[rt]=sum[rt<<1]+sum[rt<<1|1]; 8 } 9 void build(int l,int r,int rt){ 10 lazy[rt]=0;//懒标记 11 if (l==r) { 12 sum[rt]=a[l]; 13 return; 14 } 15 int m=(l+r)>>1; 16 build(lson); 17 build(rson); 18 update(rt); 19 } 20 void clean(int rt,int len){//懒标记下移 21 if(lazy[rt]){ 22 lazy[rt<<1]+=lazy[rt];//若为区间替换则为“=” 23 lazy[rt<<1|1]+=lazy[rt];//同上 24 sum[rt<<1]+=lazy[rt]*(len-(len>>1));//同上 25 sum[rt<<1|1]+=lazy[rt]*(len>>1);//同上 26 lazy[rt]=0; 27 } 28 } 29 void modify(int l,int r,int rt,int nowl,int nowr,LL v){ 30 int len=r-l+1; 31 if (nowl<=l&&r<=nowr) { 32 lazy[rt]+=v;//若为区间替换则为“=” 33 sum[rt]+=v*len;//同上 34 return; 35 } 36 clean(rt,len);//每次分治前需要下移懒标记，不分治就不下移 37 int m=(l+r)>>1; 38 if(nowl<=m)modify(lson,nowl,nowr,v); 39 if(m<nowr)modify(rson,nowl,nowr,v); 40 update(rt); 41 } 42 LL query(int l,int r,int rt,int nowl,int nowr) { 43 if (nowl<=l && r<=nowr) return sum[rt]; 44 clean(rt,r-l+1);//同上 45 LL ans=0; 46 int m=(l+r)>>1; 47 if (nowl<=m) ans+=query(lson,nowl,nowr); 48 if (m<nowr) ans+=query(rson,nowl,nowr); 49 return ans; 50 }
3.区间加减乘混合（测试：洛谷P3373）
1 typedef long long LL; 2 const int M=100001; 3 LL a[M]; 4 LL sum[M<<2],add[M<<2],c[M<<2]; 5 LL p;//模数 6 #define lson l,m,rt<<1 7 #define rson m+1,r,rt<<1|1 8 void update(int rt){ 9 sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%p; 10 } 11 void build(int l,int r,int rt){ 12 add[rt]=0;c[rt]=1;//加法懒标记和乘法懒标记 13 if (l==r) { 14 sum[rt]=a[l]; 15 return; 16 } 17 int m=(l+r)>>1; 18 build(lson); 19 build(rson); 20 update(rt); 21 } 22 void clean(int rt,int len){ 23 if(c[rt]!=1){//先下移乘法标记，再下移加法标记 24 c[rt<<1]=c[rt<<1]*c[rt]%p; 25 c[rt<<1|1]=c[rt<<1|1]*c[rt]%p; 26 add[rt<<1]=add[rt<<1]*c[rt]%p;//加法标记也要乘上乘数 27 add[rt<<1|1]=add[rt<<1|1]*c[rt]%p; 28 sum[rt<<1]=sum[rt<<1]*c[rt]%p; 29 sum[rt<<1|1]=sum[rt<<1|1]*c[rt]%p; 30 c[rt]=1; 31 } 32 if(add[rt]){ 33 add[rt<<1]=(add[rt<<1]+add[rt])%p; 34 add[rt<<1|1]=(add[rt<<1|1]+add[rt])%p; 35 sum[rt<<1]+=add[rt]*(len-(len>>1));sum[rt<<1]%=p; 36 sum[rt<<1|1]+=add[rt]*(len>>1);sum[rt<<1|1]%=p; 37 add[rt]=0; 38 } 39 } 40 void modify(int l,int r,int rt,int nowl,int nowr,LL v){//区间加法 41 int len=r-l+1; 42 if (nowl<=l&&r<=nowr) { 43 add[rt]=(add[rt]+v)%p; 44 sum[rt]=(sum[rt]+v*len%p)%p; 45 return; 46 } 47 clean(rt,len); 48 int m=(l+r)>>1; 49 if(nowl<=m)modify(lson,nowl,nowr,v); 50 if(m<nowr)modify(rson,nowl,nowr,v); 51 update(rt); 52 } 53 void modify_(int l,int r,int rt,int nowl,int nowr,LL v){//区间乘法 54 int len=r-l+1; 55 if(nowl<=l&&r<=nowr){ 56 c[rt]=c[rt]*v%p; 57 add[rt]=add[rt]*v%p; 58 sum[rt]=sum[rt]*v%p; 59 return; 60 } 61 clean(rt,len); 62 int m=(l+r)>>1; 63 if(nowl<=m)modify_(lson,nowl,nowr,v); 64 if(m<nowr)modify_(rson,nowl,nowr,v); 65 update(rt); 66 } 67 LL query(int l,int r,int rt,int nowl,int nowr) { 68 if (nowl<=l && r<=nowr) return sum[rt]; 69 clean(rt,r-l+1); 70 LL ans=0; 71 int m=(l+r)>>1; 72 if (nowl<=m) ans=(ans+query(lson,nowl,nowr))%p; 73 if (m<nowr) ans=(ans+query(rson,nowl,nowr))%p; 74 return ans; 75 }
线段树可维护的基本信息
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。