[P4] 백준 15967번 에바쿰 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

업데이트를 느리게 갱신하며 구간 누적합을 구하는 문제 int 범위를 초과하므로 long long타입을 사용해 줘야 한다.

https://www.acmicpc.net/problem/15967

 

전역 변수

• n, q1, q2 : 노드의 개수 n, 출력 쿼리의 개수 q1, 업데이트 쿼리의 개수 q2
• nodes : 노드의 정보를 저장할 정수형 배열, 크기는 100만으로 세팅
• tree : 세그먼트 트리 정보를 저장할 정수형 배열, 크기는 400만으로 세팅
• lazy : 업데이트 정보를 저장할 정수형 배열, 크기는 400만으로 세팅

 

함수

1. build

void build(ll node, ll s, ll e)

 

nodes배열을 사용하여 구간 합을 저장할 세그먼트 트리를 만드는 함수

 

2. propagate

void propagate(ll node, ll s, ll e)

 

적용할 업데이트가 있는지 체크하고, 업데이트를 진행하며 자식 노드에 업데이트를 전파하는 함수

 

3. update

void update(ll node, ll s, ll e, ll l, ll r, ll v)

 

업데이트 정보를 lazy배열에 전달하고, 실제 세그먼트 트리에 업데이트를 적용하는 함수

 

4. query

ll query(ll node, ll s, ll e, ll l, ll r)

 

구간의 합 정보를 출력할 함수

 

 

문제풀이

1. n, q1, q2를 입력 받고 n개의 노드를 nodes 배열에 저장해 준다.
2. build함수를 실행하고 tree배열에 세그먼트 트리 정보를 초기화 해준다.
3. q1 + q2번의 while문을 실행하여 쿼리 정보를 입력 받아준다.
4. op가 1일 경우 query 함수를 통해 l ~ r구간의 합을 구한 뒤 출력해 준다.
5. op가 2일 경우 update함수를 통해 l ~ r구간에 v를 더해주는 작어버을 수행해 준다.

 

참고 사항

• 구간의 합이 int타입을 넘는 듯 하다, long long타입으로 설정하여 예외가 발생하지 않게 한다.
• 입력은 1-based-indexing으로 주어지므로 인덱스를 알맞게 잘 설정하자

 

정답 코드

#include<iostream>
#define ll long long

using namespace std;
ll n, q1, q2;
ll nodes[1000000];
ll tree[4000000];
ll lazy[4000000];

void build(ll node, ll s, ll e) {
	if (s == e) tree[node] = nodes[s];
	else {
		ll m = (s + e) / 2;
		build(node * 2, s, m);
		build(node * 2 + 1, m + 1, e);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

void propagate(ll node, ll s, ll e) {
	if (lazy[node]) {
		tree[node] += (e - s + 1) * lazy[node];
		if (s != e) {
			lazy[node * 2] += lazy[node];
			lazy[node * 2 + 1] += lazy[node];
		}
		lazy[node] = 0;
	}
}

void update(ll node, ll s, ll e, ll l, ll r, ll v) {
	propagate(node, s, e);
	if (r < s || e < l) return;
	if (l <= s && e <= r) {
		lazy[node] += v;
		propagate(node, s, e);
		return;
	}
	ll m = (s + e) / 2;
	update(node * 2, s, m, l, r, v);
	update(node * 2 + 1, m + 1, e, l, r, v);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll query(ll node, ll s, ll e, ll l, ll r) {
	propagate(node, s, e);
	if (r < s || e < l) return 0;
	if (l <= s && e <= r) return tree[node];
	ll m = (s + e) / 2;
	ll left = query(node * 2, s, m, l, r);
	ll right = query(node * 2 + 1, m + 1, e, l, r);
	return left + right;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> q1 >> q2;
	for (ll i = 0; i < n; i++) cin >> nodes[i];
	build(1, 0, n - 1);
	ll m = q1 + q2;
	while (m--) {
		ll op; cin >> op;
		if (op == 1) {
			ll l, r; cin >> l >> r;
			cout << query(1, 0, n - 1, l - 1, r - 1) << "\n";
		}
		else {
			ll l, r, v; cin >> l >> r >> v;
			update(1, 0, n - 1, l - 1, r - 1, v);
		}
	}
}