[P4] 백준 10999번 구간 합 구하기 2 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

lazy propagate를 배우고 처음으로 문제에 접목해 봤다, 함수 구현보단 정수형 타입때문에 애를 좀 먹었다.

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

 

문제 풀이

전역변수

• MAX_N : 배열의 크기를 초기화 할 상수형 long long타입 변수
• nodes : 수열의 정보를 받아 저장할 배열 크기는 MAX_N으로 초기화
• tree : 세그먼트 트리 정보를 저장할 배열 크기는 MAX_N * 4로 초기화
• lazy : 업데이트 갱신용 트리 정보, tree와 같은 구조를 가진다.
• n, m, k : 수열의 길이를 나타낼 n, 업데이트 쿼리의 개수 m, 구간합 출력 쿼리의 개수 k

함수

1. build

void build(ll node, ll start, ll end)

 

세그먼트 트리를 빌드해 준다.

 

2. propagate

void propagate(ll node, ll start, ll end)

 

구간 내 갱신될 업데이트가 있는지 확인 후 존재한다면 업데이트를 적용시켜 준 뒤에 업데이트 값을 초기화 해준다.

 

3. update

void update(ll node, ll start, ll end, ll L, ll R, ll val)

 

구간 업데이트를 진행해 준다, propagate를 통해 미리 tree에 갱신이 필요한 내용을 적용시켜 준다.

구간 내 val만큼의 업데이트를 진행하고, 하위 노드는 lazy를 추가하여 다음에 필요할 경우 적용하면 된다.

이때 현재 노드가 리프 노드인지 여부를 꼭 체크 해 주어야 된다.

 

4. query

ll query(ll node, ll start, ll end, ll L, ll R)

 

기존의 query 함수와 달라진건 없다, 각 재귀 전 propagate함수를 호출하여 갱신될 업데이트가 있는지 체크해 준다.

 

1. n, m, k값을 입력 받고, nodes배열에 수열의 정보를 입력 받아준다.
2. build함수를 통해 tree배열에 세그먼트 트리를 빌드 해준다.
3. 변수 q에 m + k값을 저장하고 q번 while루프를 실행하여 쿼리를 입력 받아준다.
4. a, b, c를 입력 받아준 뒤 b ~ c 구간에 대해 1인 경우 업데이트 쿼리를 실행하고, 2인 경우 구간합 쿼리를 실행해 준다.
5. propagate 함수를 통해 현재 범위 내에 갱신될 업데이트가 있는지 체크를 해준 뒤 적용 후 업데이트를 초기화 한다.
6. 업데이트 및 쿼리 함수가 실행될 때 propagate 함수를 수행해 주면 된다.
7. 구간 업데이트 쿼리의 경우 기존 query함수와 동일하게 진행하되, 업데이트를 구간으로 적용해 준다.

 

참고 사항

입력으로 주어지는 모든 수는 -2^63보다 크거나 같고, 2^63-1보다 작거나 같은 정수이다.

main함수의 타입인 int를 제외한 모든 타입을 long long으로 설정해 주는 것이 마음 편하다.

 

 

정답 코드

#include<iostream>
#define ll long long

using namespace std;

const ll MAX_N = 1000000;
ll nodes[MAX_N];
ll tree[MAX_N * 4] = { 0, };
ll lazy[MAX_N * 4] = { 0, };
ll n, m, k;

void build(ll node, ll start, ll end) {
	if (start == end) tree[node] = nodes[start];
	else {
		ll mid = (start + end) / 2;
		build(node * 2, start, mid);
		build(node * 2 + 1, mid + 1, end);
		tree[node] = tree[node * 2] + tree[node * 2 + 1];
	}
}

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

void update(ll node, ll start, ll end, ll L, ll R, ll val) {
	propagate(node, start, end);
	if (R < start || end < L) return;
	if (L <= start && end <= R) {
		tree[node] += (end - start + 1) * val;
		if (start != end) {
			lazy[node * 2] += val;
			lazy[node * 2 + 1] += val;
		}
		return;
	}
	ll mid = (start + end) / 2;
	update(node * 2, start, mid, L, R, val);
	update(node * 2 + 1, mid + 1, end, L, R, val);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll query(ll node, ll start, ll end, ll L, ll R) {
	propagate(node, start, end);
	if (R < start || end < L) return 0;
	if (L <= start && end <= R) return tree[node];
	ll mid = (start + end) / 2;
	ll left = query(node * 2, start, mid, L, R);
	ll right = query(node * 2 + 1, mid + 1, end, L, R);
	return left + right;
}

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

	cin >> n >> m >> k;
	for (ll i = 0; i < n; i++) cin >> nodes[i];
	build(1, 0, n - 1);
	ll q = m + k;
	while (q--) {
		ll a, b, c; cin >> a >> b >> c;
		if (a == 1) {
			ll d; cin >> d;
			update(1, 0, n - 1, b - 1, c - 1, d);
		}
		else {
			cout << query(1, 0, n - 1, b - 1, c - 1) << "\n";
		}
	}
}