[C/C++] 백준 19975번 - 수열과 쿼리 21

✏️ 문제 링크

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

16975번: 수열과 쿼리 21

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

이 문제 역시 느리게 갱신되는 세그먼트 트리로 구현하는 문제입니다.

여기서 조금 더 생각해 봐야 할 것은 x번째 원소를 출력하는 건데, x번째 인덱스를 구하는 과정은

이분 탐색 과정을 통해서 값을 찾아낼 수 있습니다.

아래 문제는 느리게 갱신되는 세그먼트 트리의 기본 틀을 구현한 문제입니다.

https://pooreumjung.tistory.com/334

[C/C++] 백준 10999번 - 구간 합 구하기 2

 

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;

#define ll long long
vector<ll>arr, tree, lazy;
ll initTree(ll node, ll start, ll end);
ll update(ll node, ll start, ll end, ll l, ll r, ll diff);
void lazyUpdate(ll node, ll start, ll end);
ll findValue(ll node, ll start, ll end, ll index);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N, M;
	cin >> N;

	arr.resize(N + 1);
	tree.resize(N * 4);
	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	initTree(1, 1, N);
	lazy.resize(N * 4);

	cin >> M;
	int query;
	while (M--) {
		cin >> query;
		if (query == 1) {
			ll l, r, value;
			cin >> l >> r >> value;
			update(1, 1, N, l, r, value);
		}
		else if (query == 2) {
			ll index;
			cin >> index;
			cout << findValue(1, 1, N, index) << '\n';
		}
	}
}

ll initTree(ll node, ll start, ll end)
{
	if (start == end)
		return tree[node] = arr[start];

	ll mid = (start + end) / 2;

	ll leftSum = initTree(node * 2, start, mid);
	ll rightSum = initTree(node * 2 + 1, mid + 1, end);

	return tree[node] = leftSum + rightSum;
}

ll update(ll node, ll start, ll end, ll l, ll r, ll diff)
{
	lazyUpdate(node, start, end);

	if (r < start || end < l)
		return tree[node];

	if (l <= start && end <= r) {
		lazy[node] += diff;
		lazyUpdate(node, start, end);
		return tree[node];
	}

	ll mid = (start + end) / 2;
	ll leftSum = update(node * 2, start, mid, l, r, diff);
	ll rightSum = update(node * 2 + 1, mid + 1, end, l, r, diff);

	return tree[node] = leftSum + rightSum;
}

void lazyUpdate(ll node, ll start, ll end)
{
	if (lazy[node] == 0)
		return;

	tree[node] += (end - start + 1) * lazy[node];

	if (start != end) {
		lazy[node * 2] += lazy[node];
		lazy[node * 2 + 1] += lazy[node];
	}

	lazy[node] = 0;
}

ll findValue(ll node, ll start, ll end, ll index)
{
	lazyUpdate(node, start, end);

	if (start == end)
		return tree[node];

	ll mid = (start + end) / 2;
	if (index <= mid)
		return findValue(node * 2, start, mid, index);
	else
		return  findValue(node * 2 + 1, mid + 1, end, index);
}

 

 

 

✏️ 수열과 쿼리 문제 더 보기

https://pooreumjung.tistory.com/328

[C/C++] 백준 18436번 - 수열과 쿼리 37

https://pooreumjung.tistory.com/313

[C/C++] 백준 - 수열과 쿼리 문제

 

✏️ 세그먼트 트리 문제 더 보기

https://pooreumjung.tistory.com/330

[C/C++] 백준 5676번 - 음주 코딩

https://pooreumjung.tistory.com/314

[C/C++] 백준 - 머지 소트 트리 문제