线段树2

区间修改与区间查询

避免区间修改超时两个方法：标记下传操作，或者标记永久化。

标记下传

更新一个结点后，它和它祖先的区间和都能直接得到，但它的子结点的区间和无法立即更新。

解决方案：用到子结点的信息时再更新。具体来说，从某个结点递归时，将当前结点的tag下传，更新两个子结点的tag和数值，并清零当前结点的tag（所有步骤缺一不可）。

时间复杂度：O(mlog⁡n) O(m\log n)

核心代码 
void Add(int l,int r,int i,int v){
	add[i]+=v; //打标记 
	sum[i]+=(r-l+1)*v; //维护对应区间和 
}

void pushdown(int l,int r,int i,int mid){
	if(add[i]==0) return;
	Add(l,mid,i*2,add[i]);
	Add(mid+1,r,i*2+1,add[i]);
	add[i]=0; 
} //标记下传

void update(int l,int r,int i,int x,int y,int v){
	if(x<=l&&r<=y){
		Add(l,r,i,v);
		return;
	}
	int mid=(l+r)/2;
	pushdown(l,r,i,mid); //下放标记 
	if(x<=mid) update(l,mid,i*2,x,y,v);
	if(mid<y) update(mid+1,r,i*2+1,x,y,v);
	sum[i]=sum[i*2]+sum[i*2+1]; //更新sum 
} //给[x,y]中的每个数+v 

int find(int l,int r,int i,int x,int y){
	if(x<=l&&y<=r) return sum[k];
	int mid=(l+r)/2,ans=0;
	pushdown(l,r,i,mid); //标记下传 
	if(x<=mid) ans+=find(l,mid,i*2,x,y);
	if(mid<y) ans+=find(mid+1,r,i*2+1,x,y);
	//不需要修改区间和
	return ans; 
}

当有多个标记时，注意下放顺序。

模板

洛谷P3372

代码 
# include<iostream>
using namespace std;
# define ll long long

const int N=1e5+2;
int n,m,op,x,y;
ll k,a[N],sum[4*N],add[4*N];

void build(int l,int r,int i){
	if(l==r){
		sum[i]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	sum[i]=sum[2*i]+sum[2*i+1];
}

void Add(int l,int r,int i,ll k){
	add[i]+=k;
	sum[i]+=k*(r-l+1);
}

void pushdown(int l,int r,int i,int mid){
	if(add[i]==0) return;
	Add(l,mid,2*i,add[i]);
	Add(mid+1,r,2*i+1,add[i]);
	add[i]=0;
}

void update(int l,int r,int i,int x,int y,ll k){
	if(x<=l&&r<=y){
		Add(l,r,i,k);
		return;
	}
	int mid=(l+r)/2;
	pushdown(l,r,i,mid);
	if(x<=mid) update(l,mid,2*i,x,y,k);
	if(mid<y) update(mid+1,r,2*i+1,x,y,k);
	sum[i]=sum[2*i]+sum[2*i+1];
}

ll find(int l,int r,int i,int x,int y){
	if(x<=l&&r<=y) return sum[i];
	int mid=(l+r)/2;
	ll ans=0;
	pushdown(l,r,i,mid);
	if(x<=mid) ans+=find(l,mid,2*i,x,y);
	if(mid<y) ans+=find(mid+1,r,2*i+1,x,y);
	return ans;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>a[i];
	build(1,n,1);
	while(m--){
		cin>>op;
		if(op-1){
			cin>>x>>y;
			cout<<find(1,n,1,x,y)<<endl;
		}
		else{
			cin>>x>>y>>k;
			update(1,n,1,x,y,k); 
		}
	}
	return 0;
}

洛谷P3373

代码 
# include<iostream>
using namespace std;
# define ll long long

const int N=1e5+2;
int n,q,op,x,y;
ll m,k,a[N],sum[4*N],add[4*N],mul[4*N];

void Add(int l,int r,int i,ll k){
	if(!k) return;
	add[i]=(add[i]+k)%m;
	sum[i]=(sum[i]+(r-l+1)%m*k%m)%m;
}

void Mul(int l,int r,int i,ll k){
	if(k==1) return;
	mul[i]=mul[i]*k%m;
	add[i]=add[i]*k%m;
	sum[i]=sum[i]*k%m;
}

void pushdown(int l,int r,int i,int mid){
	Mul(l,mid,2*i,mul[i]);
	Mul(mid+1,r,2*i+1,mul[i]);
	Add(l,mid,2*i,add[i]);
	Add(mid+1,r,2*i+1,add[i]);
	mul[i]=1,add[i]=0;
}

void build(int l,int r,int i){
	mul[i]=1;
	if(l==r){
		sum[i]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	sum[i]=(sum[2*i]+sum[2*i+1])%m;
}

void update(int l,int r,int i,int x,int y,ll k1,ll k2){
	if(x<=l&&r<=y){
		Add(l,r,i,k1);
		Mul(l,r,i,k2);
		return;
	}
	int mid=(l+r)/2;
	pushdown(l,r,i,mid);
	if(x<=mid) update(l,mid,2*i,x,y,k1,k2);
	if(mid<y) update(mid+1,r,2*i+1,x,y,k1,k2);
	sum[i]=(sum[2*i]+sum[2*i+1])%m;
}

ll find(int l,int r,int i,int x,int y){
	if(x<=l&&r<=y) return sum[i];
	int mid=(l+r)/2;
	ll ans=0;
	pushdown(l,r,i,mid);
	if(x<=mid) ans=(ans+find(l,mid,2*i,x,y))%m;
	if(mid<y) ans=(ans+find(mid+1,r,2*i+1,x,y))%m;
	return ans%m;
}

int main(){
	cin>>n>>q>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		a[i]%=m;
	}
	build(1,n,1);
	while(q--){
		cin>>op>>x>>y;
		if(op==3)
			cout<<find(1,n,1,x,y)<<endl;
		else{
			cin>>k;
			if(op==2) update(1,n,1,x,y,k%m,1);
			else update(1,n,1,x,y,0,k%m);
		}
	}
	return 0;
}

练习

  1. 提高P130

思路：维护两个线段树，一个存储区间和，另一个存储区间内的所有数是否均为 0 0 或 1 1 。

这样做的好处是，如果这个区间内所有数均为 0 0 或 1 1 ，则它们开方后的值不变，因此直接跳过，不进行操作。 ​ 开心值的最大值为 109 10^9 ，经过至多 6 6 次开方就会变为 1 1 ，而国家总数 n≤105 n \le 10^5 ，因此理想操作次数为 O(6kn) O(6kn) ，其中 k k 是一个常数。

总时间复杂度：O(mlog⁡n+n) O(m\log n+n) 。

代码 
# include<iostream>
# include<cmath>
using namespace std;
# define ll long long

const int N=1e5+2;
int n,m,k,l,r;
ll a[N],t[4*N];
bool f[4*N];

void build(int l,int r,int i){
	if(l==r){
		t[i]=a[l];
		f[i]=(a[l]<2);
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	t[i]=t[2*i]+t[2*i+1];
	f[i]=f[2*i]&&f[2*i+1];
}

void update(int l,int r,int i,int x,int y){
	if(f[i]) return;
	if(l==r){
		t[i]=floor(sqrt(t[i]));
		f[i]=(t[i]<2);
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid) update(l,mid,2*i,x,y);
	if(mid<y) update(mid+1,r,2*i+1,x,y);
	t[i]=t[2*i]+t[2*i+1];
	f[i]=f[2*i]&&f[2*i+1];
}

ll find(int l,int r,int i,int x,int y){
	if(x<=l&&r<=y) return t[i];
	int mid=(l+r)/2;
	ll ans=0;
	if(x<=mid) ans+=find(l,mid,2*i,x,y);
	if(mid<y) ans+=find(mid+1,r,2*i+1,x,y);
	return ans;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	build(1,n,1);
	cin>>m;
	while(m--){
		cin>>k>>l>>r;
		if(k==1)
			cout<<find(1,n,1,l,r)<<endl;
		else
			update(1,n,1,l,r);
	}
	return 0;
}
  • 数据加强：洛谷P4145

代码 
# include<iostream>
# include<cmath>
using namespace std;
# define ll long long

const int N=1e5+2;
int n,m,k,l,r;
ll a[N],t[4*N];
bool f[4*N];

void build(int l,int r,int i){
	if(l==r){
		t[i]=a[l];
		f[i]=(a[l]<2);
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	t[i]=t[2*i]+t[2*i+1];
	f[i]=f[2*i]&&f[2*i+1];
}

void update(int l,int r,int i,int x,int y){
	if(f[i]) return;
	if(l==r){
		t[i]=floor(sqrt(t[i]));
		f[i]=(t[i]<2);
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid) update(l,mid,2*i,x,y);
	if(mid<y) update(mid+1,r,2*i+1,x,y);
	t[i]=t[2*i]+t[2*i+1];
	f[i]=f[2*i]&&f[2*i+1];
}

ll find(int l,int r,int i,int x,int y){
	if(x<=l&&r<=y) return t[i];
	int mid=(l+r)/2;
	ll ans=0;
	if(x<=mid) ans+=find(l,mid,2*i,x,y);
	if(mid<y) ans+=find(mid+1,r,2*i+1,x,y);
	return ans;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>a[i];
	build(1,n,1);
	cin>>m;
	while(m--){
		cin>>k>>l>>r;
		if(k)
			cout<<find(1,n,1,min(l,r),max(l,r))<<endl;
		else
			update(1,n,1,min(l,r),max(l,r));
	}
	return 0;
}
  1. 提高P131，洛谷P2023

对应洛谷P2023，类似洛谷P3373（上方模板）

代码 
# include<iostream>
using namespace std;
# define ll long long

const int N=1e5+2;
int n,q,op,x,y;
ll m,k,a[N],sum[4*N],add[4*N],mul[4*N];

void Add(int l,int r,int i,ll k){
	if(!k) return;
	add[i]=(add[i]+k)%m;
	sum[i]=(sum[i]+(r-l+1)%m*k%m)%m;
}

void Mul(int l,int r,int i,ll k){
	if(k==1) return;
	mul[i]=mul[i]*k%m;
	add[i]=add[i]*k%m;
	sum[i]=sum[i]*k%m;
}

void pushdown(int l,int r,int i,int mid){
	Mul(l,mid,2*i,mul[i]);
	Mul(mid+1,r,2*i+1,mul[i]);
	Add(l,mid,2*i,add[i]);
	Add(mid+1,r,2*i+1,add[i]);
	mul[i]=1,add[i]=0;
}

void build(int l,int r,int i){
	mul[i]=1;
	if(l==r){
		sum[i]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	sum[i]=(sum[2*i]+sum[2*i+1])%m;
}

void update(int l,int r,int i,int x,int y,ll k1,ll k2){
	if(x<=l&&r<=y){
		Add(l,r,i,k1);
		Mul(l,r,i,k2);
		return;
	}
	int mid=(l+r)/2;
	pushdown(l,r,i,mid);
	if(x<=mid) update(l,mid,2*i,x,y,k1,k2);
	if(mid<y) update(mid+1,r,2*i+1,x,y,k1,k2);
	sum[i]=(sum[2*i]+sum[2*i+1])%m;
}

ll find(int l,int r,int i,int x,int y){
	if(x<=l&&r<=y) return sum[i];
	int mid=(l+r)/2;
	ll ans=0;
	pushdown(l,r,i,mid);
	if(x<=mid) ans=(ans+find(l,mid,2*i,x,y))%m;
	if(mid<y) ans=(ans+find(mid+1,r,2*i+1,x,y))%m;
	return ans%m;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		a[i]%=m;
	}
	cin>>q;
	build(1,n,1);
	while(q--){
		cin>>op>>x>>y;
		if(op==3)
			cout<<find(1,n,1,x,y)<<endl;
		else{
			cin>>k;
			if(op==2) update(1,n,1,x,y,k%m,1);
			else update(1,n,1,x,y,0,k%m);
		}
	}
	return 0;
}
  1. 洛谷P1253 扶苏的问题

注意pushdown的先后顺序以及数据范围（不开 long long 见祖宗，最小值一定要开到 −2×1018 -2 \times 10^{18} ）！

代码 
# include<iostream>
using namespace std;
# define ll long long

const int N=1e6+2;
const ll inf=-2e18;
int n,q,op,x,y;
ll k,a[N],ma[4*N],add[4*N],chg[4*N];

void Add(int l,int r,int i,ll k){
  if(!k) return;
  add[i]+=k;
  ma[i]+=k;
}

void change(int l,int r,int i,ll k){
  if(k==inf) return;
  chg[i]=k;
  add[i]=0;
  ma[i]=k;
}

void pushdown(int l,int r,int i,int mid){
  change(l,mid,2*i,chg[i]);
  change(mid+1,r,2*i+1,chg[i]);
  Add(l,mid,2*i,add[i]);
  Add(mid+1,r,2*i+1,add[i]);
  chg[i]=inf,add[i]=0;
}

void build(int l,int r,int i){
  chg[i]=inf;
  if(l==r){
  	ma[i]=a[l];
  	return;
  }
  int mid=(l+r)/2;
  build(l,mid,2*i);
  build(mid+1,r,2*i+1);
  ma[i]=max(ma[2*i],ma[2*i+1]);
}

void update(int l,int r,int i,int x,int y,ll k,bool f){
  if(x<=l&&r<=y){
  	if(f) Add(l,r,i,k);
  	else change(l,r,i,k);
  	return;
  }
  int mid=(l+r)/2;
  pushdown(l,r,i,mid);
  if(x<=mid) update(l,mid,2*i,x,y,k,f);
  if(mid<y) update(mid+1,r,2*i+1,x,y,k,f);
  ma[i]=max(ma[2*i],ma[2*i+1]);
}//f=0:change;f=1:add

ll find(int l,int r,int i,int x,int y){
  if(x<=l&&r<=y) return ma[i];
  int mid=(l+r)/2;
  ll ans=inf;
  pushdown(l,r,i,mid);
  if(x<=mid) ans=max(ans,find(l,mid,2*i,x,y));
  if(mid<y) ans=max(ans,find(mid+1,r,2*i+1,x,y));
  return ans;
}

int main(){
  ios::sync_with_stdio(false);
  cin>>n>>q;
  for(int i=1;i<=n;++i) cin>>a[i];
  build(1,n,1);
  while(q--){
  	cin>>op>>x>>y;
  	if(op==3){
  		cout<<find(1,n,1,min(x,y),max(x,y))<<endl;
  		continue;
  	}
  	cin>>k;
  	update(1,n,1,min(x,y),max(x,y),k,op-1);
  }
  return 0;
}
  1. 洛谷P1558 色板游戏

思路：对每种颜色维护一个线段树，统计区间内是否存在当前颜色的格子。

代码 
# include<iostream>
using namespace std;

const int N=1e5+2,T=32;
int n,t,q,x,y,k,tot;
char op;
bool f[T][4*N]; //颜色i在区间j内是否有 
int tag[T][4*N]; //1表示全部清空，2表示全部涂满 

void change(int t,int i,int p){
	tag[t][i]=p;
	f[t][i]=p-1;
}

void pushdown(int t,int i){
	if(!tag[t][i]) return;
	change(t,2*i,tag[t][i]);
	change(t,2*i+1,tag[t][i]);
	tag[t][i]=0;
}

void build(int l,int r,int i){
	if(l==r){
		f[1][i]=1;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*i);
	build(mid+1,r,2*i+1);
	f[1][i]=1;
}

void update(int t,int l,int r,int i,int x,int y,int k){
	if(x<=l&&r<=y){
		if(t==k) change(t,i,2);
		else change(t,i,1);
		return;
	}
	int mid=(l+r)/2;
	pushdown(t,i);
	if(x<=mid) update(t,l,mid,2*i,x,y,k);
	if(mid<y) update(t,mid+1,r,2*i+1,x,y,k);
	f[t][i]=f[t][2*i]||f[t][2*i+1];
} //[x,y]全部涂上k 

bool find(int t,int l,int r,int i,int x,int y){
	if(x<=l&&r<=y) return f[t][i];
	int mid=(l+r)/2;
	bool ans=0;
	pushdown(t,i);
	if(x<=mid) ans=ans||find(t,l,mid,2*i,x,y);
	if(mid<y) ans=ans||find(t,mid+1,r,2*i+1,x,y);
	return ans;
} //[x,y]内是否存在颜色t，是返回1，否返回0 

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>t>>q;
	build(1,n,1);
	while(q--){
		cin>>op>>x>>y;
		if(op=='C'){
			cin>>k;
			for(int i=1;i<=t;++i)
				update(i,1,n,1,min(x,y),max(x,y),k);
		}
		else{
			tot=0;
			for(int i=1;i<=t;++i)
				tot+=find(i,1,n,1,min(x,y),max(x,y));
			cout<<tot<<endl;
		}
	}
	return 0;
}
  1. 洛谷P8818 [CSP-S 2022 T2] 策略游戏

  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 粤ICP备2021104657号
  3. Worker 0, 13ms
  4. Powered by Hydro v4.14.1 Community