백준 10999 c++ "구간 합 구하기 2" -PlusUltraCode-

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

 

[필자 사고]
새로운 알고리즘의 만남이다. 세그먼트 트리에 lazy 전파를 적용하는 것이다.

아직 익숙지 않다. 많은 문제를 통해 lazy전파 알고리즘에 익숙해져 보자.

약간 정리하자면 Query 나 update에서 항상 propagate를 1행에 실행시킨다.

그리고 update에서 갱신되는 부분이 생기면 lazy[node] +=diff 를 갱신해주고

다시 propagate 를 선언한다. 이정도??
[코드 해설]

• 세그먼트 트리 초기화 (Init_Tree 함수)
  이 함수는 세그먼트 트리를 생성하는 역할을 한다.
  • 리프 노드에 도달하면 arr 배열의 값을 트리에 저장한다.
  • 내부 노드에서는 왼쪽과 오른쪽 자식의 값을 더하여 부모 노드에 저장한다.
• 지연 전파 (Propagate 함수)
  이 함수는 현재 노드에 저장된 lazy 값을 처리한다.
  • 현재 노드에 지연된 값(lazy)이 있으면 해당 값을 트리에 반영한다.
  • 리프 노드가 아닌 경우, 자식 노드의 lazy 배열에도 값을 전달한다.
  • 이후 현재 노드의 lazy 값을 0으로 초기화한다.
• 구간 합 쿼리 (Query 함수)
  특정 범위의 합을 구하기 위해 호출된다.
  • 지연 전파를 먼저 실행하여 최신 상태를 반영한다.
  • 쿼리 범위가 현재 범위와 겹치지 않으면 0을 반환한다.
  • 현재 범위가 쿼리 범위에 완전히 포함되면 해당 노드 값을 반환한다.
  • 그렇지 않으면 왼쪽과 오른쪽 자식을 재귀적으로 탐색하며 값을 합산한다.
• 구간 업데이트 (RangeUpdate 함수)
  특정 범위에 값을 더하는 연산을 처리한다.
  • 지연 전파를 먼저 실행하여 최신 상태를 반영한다.
  • 업데이트 범위가 현재 범위와 겹치지 않으면 종료한다.
  • 현재 범위가 업데이트 범위에 완전히 포함되면 lazy 값을 갱신하고 다시 전파한다.
  • 그렇지 않으면 왼쪽과 오른쪽 자식을 재귀적으로 탐색하며 트리를 갱신한다.
• 게임 시작 (Game_Start 함수)
  입력을 받아 세그먼트 트리를 초기화하고, 쿼리 및 업데이트 연산을 처리한다.
  • N은 배열의 크기, M은 업데이트 연산의 수, K는 쿼리 연산의 수이다.
  • 배열 arr를 입력받아 세그먼트 트리를 초기화한다.
  • 이후 M + K개의 연산을 처리하며, 플래그 값에 따라 업데이트 또는 쿼리를 실행한다.
• 메인 함수
  • 입출력 속도를 최적화하기 위해 ios::sync_with_stdio(false)와 cin.tie(0)를 사용한다.
  • Game_Start 함수를 호출하여 프로그램을 실행한다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<long> tree;
vector<long> lazy;
vector<long> arr;
long N, M, K;
void Init_Tree(long node, long start, long end) {
	if (start == end) {
		tree[node] = arr[start];
		return;
	}
	long 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 Propagate(long node, long start, long 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;
	}
}

long Query(long node, long start, long end, long left, long right) {
	Propagate(node, start, end);
	if (right < start || end < left) return 0;
	if (left <= start && end <= right) return tree[node];
	long mid = (start + end) / 2;
	return Query(node * 2, start, mid, left, right) +
		Query(node * 2 + 1, mid + 1, end, left, right);
}
void RangeUpdate(long node, long start, long end, long left, long right, long diff) {
	Propagate(node, start, end);
	if (right < start || end < left) return; //
	if (left <= start && end <= right) {
		lazy[node] += diff;
		Propagate(node, start, end);
		return;
	}
	long mid = (start + end) / 2;
	RangeUpdate(node * 2, start, mid, left, right, diff);
	RangeUpdate(node * 2 + 1, mid + 1, end, left, right, diff);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}