백준 10999번: 구간 합 구하기 2
구간 합 구하기 2
아이디어
구간의 길이가 최대 N이므로 구간에 존재하는 모든 노드를 바꾸려면 NlogN이 걸린다.
해당 구간에 존재하는 모든 노드를 업데이트하지 말고, 이 노드는 업데이트가 필요합니다! 라고 표시만 해놓고 나중에 방문할 때 업데이트를 해주면 어떨까?
딱 맞는 구간까지만 업데이트하고, 그 구간을 표시하는 노드의 left, right child에 표시를 해둔다. 나중에 그 child를 방문했을 때, 값을 업데이트하고, 다시 left, right child에 표시를(리프 노드라면 못하겠죠?) 해 둔다.
이렇게 하면 업데이트를 로그 시간에 진행할 수 있다!!
백준 선생님이 아주 야무지게 설명해주시는 세그먼트 트리 나중에 업데이트 해야지!를 읽어보자.
propagate 함수는 해당 구간의 합을 저장하는 노드를 방문했을 때 lazy[node]가 존재하면, 즉 이전에 업데이트를 미뤄서 표시가 되어 있으면 해당 구간의 합을 저장하는 노드에 구간 사이즈에 비례해서 업데이트를 미룬 difference를 더해준다. 그리고 양쪽 자식에게 또 업데이트 미룹니다 ㅋㅋ 나중에 방문할 때 업데이트하세요 라고 표시를 해 둔다. 언젠가 리프 노드에 도달하면 폭탄돌리기는 끝이 난다.
코드
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
int N, M, K;
vector<long long> arr(MAX), tree(1<<21), lazy(1<<21);
long long init(int start, int end, int node) {
if (start == end) return tree[node] = arr[start];
return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}
void propagate(int start, int end, int node) {
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;
}
}
long long query(int start, int end, int left, int right, int node) {
propagate(start, end, node);
if (end < left || right < start) return 0;
if (left <= start && end <= right) return tree[node];
return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}
void update(int start, int end, int left, int right, long long diff, int node) {
propagate(start, end, node);
if (end < left || right < start) return;
if (left <= start && end <= right) {
tree[node] += (end-start+1)*diff;
if (start != end) {
lazy[node*2] += diff;
lazy[node*2+1] += diff;
}
return;
}
update(start, (start+end)/2, left, right, diff, node*2);
update((start+end)/2+1, end, left, right, diff, node*2+1);
tree[node] = tree[node*2] + tree[node*2+1];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
init(0, N-1, 1);
for (int i = 0; i < M+K; i++) {
int q, a, b;
cin >> q;
if (q == 1) {
long long c;
cin >> a >> b >> c;
update(0, N-1, a-1, b-1, c, 1);
}
else if (q == 2) {
cin >> a >> b;
cout << query(0, N-1, a-1, b-1, 1) << '\n';
}
}
return 0;
}
여담
어떻게 이런 신박한 생각을.. 머리를 한대 얻어맞은 기분이 든다.
Author And Source
이 문제에 관하여(백준 10999번: 구간 합 구하기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-10999번-구간-합-구하기-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)