커피숍2
2017-02-05 18:24:28 | 조회수 2029
-
유형
문제 요약
-
세그먼트 트리특정 구간의 합을 출력하거나 특정 위치의 숫자를 바꿀 때, 출력의 결과를 출력하세요.
※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
특정 위치의 합을 구하거나 값을 변경하면서 그 결과를 매 쿼리마다 처리해 줄 때는 $O(N^2)$ 의 시간복잡도로 풀 수 없습니다. 그러므로 이러한 문제를 풀 때는 세그먼트 트리라는 개념을 사용합니다. 세그먼트 트리를 이미지로 표현하면 아래와 같습니다.
출처 : algorithmandme.in
분할 정복을 공부하셨다면 위의 개념을 이해할 수 있습니다. 루트가 전체라고 하면 좌측 subtree에는 왼쪽 절반, 우측 subtree에는 우측 절반을 저장합니다. 마찬가지로 나눠진 것에 대해 또 절반, 절반, ... 을 하며 구간의 합을 저장하는 자료 구조입니다. 이러한 자료구조를 이용할 경우 삽입, 갱신을 $O(logn)$ 의 시간복잡도로 할 수 있습니다.
커피숍2와 같은 문제는 펜윅 트리를 이용하여 더욱 쉽게 짤 수 있습니다. 하지만 여기 소스코드에는 정통(?) Segment Tree로 해결한 소스코드를 첨부하겠습니다.
클릭하여 소스코드 보기
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
ll init(vector<ll> &l, vector<ll> &tree, int node, int start, int end)
{
if (start == end) return tree[node] = l[start];
return tree[node] = init(l, tree, node * 2, start, (start + end) / 2) + init(l, tree, node * 2 + 1, (start + end) / 2 + 1, end);
}
ll sum(vector<ll> &tree, int node, int left, int right, int start, int end)
{
if (left > end || right < start) return 0;
if (left <= start && end <= right) return tree[node];
return sum(tree, node * 2, left, right, start, (start+end)/2) + sum(tree, node * 2 + 1, left, right, (start+end)/2+1, end);
}
void update(vector<ll> &tree, int node, int idx, int start, int end, ll diff)
{
if (idx < start || idx > end) return;
tree[node] += diff;
if (start != end)
{
update(tree, node * 2, idx, start, (start + end) / 2, diff);
update(tree, node * 2 + 1, idx, (start + end) / 2 + 1, end, diff);
}
}
int main()
{
int n, m;
scanf("%d %d", &n, &m);
int size = (int)ceil(log2(n));
size = 1 << (size + 1);
vector<ll> l(n), tree(size);
for (int i = 0; i < n; i++) scanf("%lld", &l[i]);
init(l, tree, 1, 0, n - 1);
while(m--)
{
int x, y, z, w;
scanf("%d %d %d %d", &x, &y, &z, &w);
if (x > y) swap(x, y);
if (x>=1 && x<=n && y>=1 && y<=n) printf("%lld\n", sum(tree, 1, x - 1, y - 1, 0, n - 1));
if (z < 1 || z > n) continue;
update(tree, 1, z - 1, 0, n - 1, w - l[z - 1]);
l[z - 1] = w;
}
}