[P4] 백준 16975번 수열과 쿼리 21 C++ 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

리뷰

 

느리게 갱신되는 세그먼트 트리의 기초 문제, 쿼리가 구간합이 아닌 특정 인덱스를 출력하는 문제이다.

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

 

문제 풀이

전역 변수

• MAX_N : 노드의 최대 개수를 지정할 상수 변수, 10만으로 초기화 한다.
• nodes : 수열의 정보를 저장할 배열, 크기는 MAX_N으로 초기화 한다.
• tree : 세그먼트 트리 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.
• lazy : 느린 업데이트 정보를 저장할 배열, 크기는 MAX_N * 4로 초기화 한다.
• n, m : 수열의 크기 n, 쿼리의 개수 m을 저장할 변수

 

함수

1. build

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

 

nodes 수열을 갖고 tree배열에 세그먼트 트리를 만들 함수, 최초 한번 실행된다.

 

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)

 

업데이트 관련 쿼리가 들어왔을때 업데이트가 필요한 구간에 적용을 해주는 함수

당장 리프노드까지 갈 필요가 없다면 상위 노드까지만 업데이트 해주고 나머진 lazy 배열에 저장해 준다.

 

4. query

ll query(ll node, ll start, ll end, ll P)

 

출력 관련 쿼리가 들어왔을때 출력이 필요한 인덱스를 찾아 리턴해 주는 함수

 

문제 풀이

1. n값을 입력 받고 nodes배열에 수열의 정보를 입력 받아준다, 이후 build 함수를 통해 세그먼트 트리를 빌드해준다.
2. m값을 입력 받고 m개의 쿼리를 입력 받아준 뒤 각각의 요구사항에 맞게 업데이트, 출력을 진행해 준다.
3. 0-based-indexing상태이므로 입력 받은 구간을 함수로 전달해 줄때 1을 감소시킨 상태로 전달해 준다.
4. a가 1이라면 추가로 숫자를 세개 더 받은 뒤 update를, 2라면 추가로 숫자를 한개 더 받은 뒤  query를 실행한다.
5. 타 문제와는 다르게 query가 구간의 합이 아닌 특정 인덱스를 출력한다는 점인 것을 기억해야 한다.
6. 업데이트 및 쿼리가 진행될때 propagate함수를 출력해 갱신되지 않은 값이 있는지 먼저 체크해 주어야 한다.

 

참고 사항

업데이트로 들어올 수 있는 값이 최대 -100만 ~ 100만이므로 long long타입으로 해주어야 한다.

 

 

정답 코드

 

#include<iostream>
#define ll long long

using namespace std;

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

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) {
		lazy[node] += val;
		propagate(node, start, end);
		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 P) {
	propagate(node, start, end);
	if (P == start && end == P) return tree[node];
	ll mid = (start + end) / 2;
	if (P <= mid) return query(node * 2, start, mid, P);
	return query(node * 2 + 1, mid + 1, end, P);
}

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

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