[백준 10999번] 구간 합 구하기2

---

10999번: 구간 합 구하기 2

---

 

목차

• 사전 지식
• 문제 접근
• 문제 풀이

 

 

사전 지식

• 세그먼트 트리(Segment Tree)에 대한 기본 지식을 알고 있어야 한다. (링크)
• 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 알고 있으면 좋다 (링크)

 

 

 

문제 접근

백준 2042번 문제(링크)와 이번 문제의 차이점을 정확히 인지하는 것이 중요하다.

2042번 문제는 한 번에 한 개의 원소만 갱신되는 반면, 이번 문제는 한 번에 구간 단위로 갱신된다.

 

기본 세그먼트 트리 풀이

이번 문제를 기본 세그먼트 트리를 이용하여 풀면 어떻게 될까?

배열의 길이는 $N \leq 10^6 \ $이며, 쿼리(질의)의 개수는 각각 $M \leq 10^4, K \leq 10^4 \ $이다.

구간의 합을 구하는 쿼리는 $O(\log N)$의 시간이 걸리므로 별 문제가 안 된다.

하지만, 구간에 수를 더하는 쿼리는 $O(N \cdot \log N)$에 근사하는 시간이 걸린다.

그러므로, 최종 시간 복잡도는 $O(N + (MN + K) \cdot \log N)$이 나오므로 TLE(Time Limit Exceed) 오류가 발생한다.

 

따라서, 우리는 구간의 합을 구하는 쿼리를 더 효율적으로 처리하는 방법을 찾아야 한다.

 

 

 

문제 풀이

결론부터 말하면 이 문제는 느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)를 이용하여 풀 수 있다.

이를 이용하면 구간 단위로 업데이트하는 쿼리를 구간 쿼리와 비슷하게 처리할 수 있다.

즉, 구간에 수를 더하는 쿼리와 구간의 합을 구하는 쿼리를 모두 $O(\log N)$의 시간에 수행할 수 있다.

따라서, 최종 시간 복잡도는 $O(N + (M+K) \cdot \log N)$으로 문제를 해결할 수 있다.

 

느리게 갱신 되는 세그먼트 트리에 관한 자세한 설명은 여기를 참조하기 바란다.

 

	// BOJ 10999
	// Lazy SegTree
	#include <bits/stdc++.h>
	using namespace std;
	using ll = long long;
	ll sz;
	struct Seg {
	vector<ll> tree, lazy;
	void build(int n) {
	for (sz=1; sz<n; sz*=2);
	tree.assign(2*sz, 0);
	lazy.assign(2*sz, 0);
	for (int i=sz; i<sz+n; i++) cin >> tree[i];
	for (int i=sz-1; i>=1; i--) tree[i] = tree[2*i] + tree[2*i+1];
	}
	void update(int l, int r, ll x, int n=1, int nl=0, int nr=sz-1) {
	propagate(n, nl, nr);
	if (nr<l || r<nl) return;
	if (l<=nl && nr<=r) {
	lazy[n] += x;
	propagate(n, nl, nr);
	return;
	}
	int mid = (nl + nr) / 2;
	update(l, r, x, 2*n, nl, mid);
	update(l, r, x, 2*n+1, mid+1, nr);
	tree[n] = tree[2*n] + tree[2*n+1]; // update current node
	}
	ll query(int l, int r, int n=1, int nl=0, int nr=sz-1) {
	propagate(n, nl, nr);
	if (nr<l || r<nl) return 0;
	if (l<=nl && nr<=r) return tree[n];
	int mid = (nl + nr) / 2;
	return query(l, r, 2*n, nl, mid) + query(l, r, 2*n+1, mid+1, nr);
	}
	void propagate(int n, int nl, int nr) {
	if (lazy[n] != 0) {
	if (n < sz) { // (if not leaf node) propagte child node
	lazy[2*n] += lazy[n];
	lazy[2*n+1] += lazy[n];
	}
	// update current node
	tree[n] += lazy[n] * (nr-nl+1);
	lazy[n] = 0;
	}
	}
	} seg;
	int main()
	{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M, K; cin >> N >> M >> K;
	seg.build(N);
	for (int i=0; i<M+K; i++) {
	ll op, a, b, x; cin >> op >> a >> b;
	if (op == 1) {
	cin >> x;
	seg.update(a-1, b-1, x);
	}
	if (op == 2) {
	cout << seg.query(a-1, b-1) << '\n';
	}
	}
	return 0;
	}

view raw 10999.cpp hosted with ❤ by GitHub