백준 15967 c++ "에바쿰" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 세그먼트 트리 자료구조를 이용하여 풀 수 있다.

다만 Update하는 과정에서 특정 idx만 업데이트가 아닌 구간 udpate이므로

Propagation을 통해 지연 전파 알고리즘을 적용 해야된다.

필자는 lazy배열 크기를 설정하는데 tree배열 크기와 같게 해야되는데 N+1로 초기화를 해버렸다.

조심해야 겠다.

[코드 해설]

2. 입력 처리

Input() 함수는 프로그램의 초기 입력값을 처리하는 역할을 합니다. 배열의 크기(N), 구간 합 쿼리 개수(Q1), 구간 업데이트 쿼리 개수(Q2)를 입력받고, 배열(arr)의 값을 저장합니다. 세그먼트 트리(tree)와 Lazy Propagation 배열(lazy)은 계산 효율성을 위해 미리 크기를 설정하여 초기화합니다.

---

3. Lazy Propagation

Propagation() 함수는 세그먼트 트리 노드의 값에 지연된 업데이트를 반영합니다. Lazy 배열은 이전에 업데이트가 연기된 값을 저장하며, 필요할 때 해당 값을 현재 노드와 자식 노드에 적용합니다. 이를 통해 불필요한 연산을 줄이고 구간 단위의 작업 효율성을 높입니다.

---

4. 세그먼트 트리 초기화

Init_Tree() 함수는 입력받은 배열을 기반으로 세그먼트 트리를 초기화합니다. 배열의 값을 리프 노드에 저장하고, 상위 노드의 값은 자식 노드들의 합으로 설정됩니다. 재귀적으로 구간을 분할하여 트리를 구축합니다.

---

5. 구간 업데이트

Update() 함수는 배열의 특정 구간 값을 일정 값만큼 증가 또는 감소시키는 역할을 합니다. Lazy Propagation을 사용하여 업데이트 작업을 효율적으로 처리하며, 구간이 포함될 경우 Lazy 배열을 활용해 즉시 값을 적용하거나 나중에 반영할 수 있도록 설정합니다.

---

6. 구간 합 쿼리

Query() 함수는 배열의 특정 구간 합을 계산합니다. Lazy Propagation을 활용해 업데이트되지 않은 값을 반영한 후, 필요한 구간의 합을 계산합니다. 구간을 포함하지 않는 경우 0을 반환하며, 구간을 분할하여 탐색합니다.

---

7. 전체 흐름

Game_Start() 함수는 프로그램의 주요 로직을 실행합니다. 먼저 세그먼트 트리를 초기화한 후, 입력된 쿼리(Q1 + Q2)를 처리합니다. 각 쿼리는 다음과 같은 두 가지 작업 중 하나를 수행합니다:

1. 구간 합 쿼리: 특정 구간의 합을 출력합니다.
2. 구간 업데이트: 특정 구간의 값을 업데이트합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#define ll long long
#include <algorithm>

using namespace std;

int N, Q1, Q2;
vector<ll> tree;
vector<ll> arr;
vector<ll> lazy;

void Input() {
	cin >> N >> Q1 >> Q2;
	tree.resize(N * 4);
	arr.resize(N + 1);
	lazy.resize(N*4);

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
}

void Propagation(int node, int start, int end) {
	if (lazy[node] != 0) {
		
		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 Init_Tree(int node, int start, int end) {
	if (start == end) {
		tree[node] = arr[start];
		return;
	}

	int mid = (start + end) / 2;
	Init_Tree(node * 2, start, mid);
	Init_Tree(node * 2 + 1, mid + 1, end);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
void Update(int node, int start, int end, int left, int right, ll val) {
	Propagation(node, start, end);

	if (left <= start && end <= right) {
		lazy[node] += val;
		Propagation(node, start, end);
		return;
	}
	if (end < left || right < start)return;

	int mid = (start + end) / 2;
	Update(node * 2, start, mid, left, right, val);
	Update(node * 2+1, mid + 1, end, left, right, val);

	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
ll Query(int node, int start, int end, int left, int right) {
	Propagation(node, start, end);

	if (left <= start && end <= right) {
		return tree[node];
	}
	if (end < left || right < start)return 0;

	int mid = (start + end) / 2;
	return Query(node * 2, start, mid, left, right) +
		Query(node * 2 + 1, mid + 1, end, left, right);
}

void Game_Start() {

	Init_Tree(1, 1, N);
	for (int i = 0; i < Q1 + Q2; i++) {
		int flag;
		cin >> flag;
		if (flag == 1) {
			int p1, p2;
			cin >> p1 >> p2;
			cout << Query(1, 1, N, p1, p2) << '\n';
		}
		else {
			int a, b, c;
			cin >> a >> b >> c;
			Update(1, 1, N, a, b, c);
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	Input();
	Game_Start();
}