Segment Tree and Lazy Propagation

드디어 느리게 갱신하는 세그먼트 트리의 구현을 끝냈다. update에서 r을 e로 쓴 오타를 몇 시간동안 찾지 못해 고생했다.

 

10999번: 구간 합 구하기 2

 

#include<bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
const int N=1e6+1;
struct Segment {
	ll a[N];
	ll tree[4*N],lazy[4*N];
	void init(int l,int r,int i) {
		if(l==r) { tree[i]=a[l]; return; }
		int m=l+r>>1;
		init(l,m,i<<1); init(m+1,r,i<<1|1);
		tree[i]=tree[i<<1]+tree[i<<1|1];
	}
	void prop(int l,int r,int i) {
		if(!lazy[i]) return;
		tree[i]+=(r-l+1)*lazy[i];
		if(l<r){
			lazy[i<<1]+=lazy[i];
			lazy[i<<1|1]+=lazy[i];
		}
		lazy[i]=0;
	}
	void update(int l,int r,int nl,int nr,int i,ll v) {
		prop(nl,nr,i);
		if(r<nl||nr<l) return;
		if(l<=nl&&nr<=r){
			lazy[i]=v;
			prop(nl,nr,i);
			return;
		}
		int nm=nl+nr>>1;
		update(l,r,nl,nm,i<<1,v); update(l,r,nm+1,nr,i<<1|1,v);
		tree[i]=tree[i<<1]+tree[i<<1|1];
	}
	ll query(int l,int r,int nl,int nr,int i) {
		prop(nl,nr,i);
		if(r<nl||nr<l) return 0;
		if(l<=nl&&nr<=r) return tree[i];
		int nm=nl+nr>>1;
		return query(l,r,nl,nm,i<<1)+query(l,r,nm+1,nr,i<<1|1);
	}
} tree;
int main()
{
	fastio;
	int n,m,k,q;
	cin >> n >> m >> k; q=m+k;
	for(int i=1;i<=n;i++) cin >> tree.a[i];
	tree.init(1,n,1);
	while(q--){
		int t,l,r; ll v;
		cin >> t >> l >> r; if(t==1) cin >> v;
		if(t==1) tree.update(l,r,1,n,1,v);
		else cout << tree.query(l,r,1,n,1) << '\n';
	}
}

 

 

2. 구간 곱 업데이트, 구간 합 쿼리

 

#include<bits/stdc++.h>
using namespace std;
#define nm (nl+nr>>1)
const int N = 1e5+1;
int n,q,a[N],tree[4*N],lazy[4*N];
void init(int nl=1,int nr=n,int i=1) {
	if(nl==nr){ tree[i]=a[nl]; return; }
	init(nl,nm,i<<1); init(nm+1,nr,i<<1|1);
	tree[i]=tree[i<<1]+tree[i<<1|1];
}
void prop(int nl,int nr,int i) {
	if(lazy[i]==1) return;
	tree[i]*=lazy[i];
	if(nl^nr) lazy[i<<1]*=lazy[i], lazy[i<<1|1]*=lazy[i];
	lazy[i]=1;
}
void update(int l,int r,int v,int nl=1,int nr=n,int i=1) {
	prop(nl,nr,i);
	if(r<nl||nr<l) return;
	if(l<=nl&&nr<=r){ lazy[i]*=v; prop(nl,nr,i); return; }
	update(l,r,v,nl,nm,i<<1); update(l,r,v,nm+1,nr,i<<1|1);
	tree[i]=tree[i<<1]+tree[i<<1|1];
}
int query(int l,int r,int nl=1,int nr=n,int i=1) {
	prop(nl,nr,i);
	if(r<nl||nr<l) return 0;
	if(l<=nl&&nr<=r) return tree[i];
	return query(l,r,nl,nm,i<<1)+query(l,r,nm+1,nr,i<<1|1);
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	fill(lazy,lazy+4*N,1);
	cin >> n >> q;
	for(int i=1;i<=n;i++) cin >> a[i];
	init();
	while(q--){
		int t,l,r,v; cin >> t >> l >> r;
		if(t==1) cin >> v, update(l,r,v);
		else cout << query(l,r) << '\n';
	}
}