본문 바로가기

Algorithm/Data structure

Segment Tree and Lazy Propagation

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

 

 

10999번: 구간 합 구하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

 

#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';
	}
}

'Algorithm > Data structure' 카테고리의 다른 글

경로 가중치 합 hld 구현 코드  (0) 2021.07.06
Segment Tree and Lazy Propagation  (0) 2021.05.28
연속합 최대 Segment Tree  (2) 2021.05.22
Li Chao Tree  (2) 2021.05.18
Bottom-Up Segment Tree  (2) 2021.04.18
Fenwick Tree  (4) 2021.04.04