https://www.acmicpc.net/problem/10999
10999번: 구간 합 구하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c 또는 a, b, c, d가 주어지는데, a가 1인 경우 b번째 수부터 c번째 수에 d를 더하고, a가 2
www.acmicpc.net
문제 풀이 및 설명
문제의 분류는 세그먼트 트리 with Lazy Propagation 이다.
이문제를 처음 접했을때, lazy propagation에 대한 사전지식이 없다면 매우 어렵게 느낄 것이다.
또한 구글링이나, 검색을통해 lazy propagation을 배우려고 할때에 세그먼트 트리의 update와 query의 작동방식을 알고 있다면, 금방 lazy propagation 도 이해할 수 있겠지만, 세그먼트 트리의 작동원리를 알지못하고 그저 코드를 외워서 문제를 풀어왔다면 lazy propagation풀이를 봐도 이해하지 못할 것이다. 이문제의 유형을 처음 접했다면, lazy propagation을 먼저 검색해보고, lazy propagation이 이해가 가지 않는다면, 세그먼트 트리를 다시 공부 할 필요가 있다. (다른 수많은 블로그에 엄청 자세하게 나와있다)
전체 코드
#include <iostream>
using namespace std;
#define MAX_N 1000001
#define endl '\n'
typedef long long ll;
ll seg[MAX_N * 4];
ll lazy[MAX_N * 4];
void update_tree(int now, int target, int start, int end, ll value) {
if (target > end || target < start) return;
if (start == end) {
seg[now] = value;
return;
}
int mid = (start + end) / 2;
update_tree(now * 2, target, start, mid, value);
update_tree(now * 2 + 1, target, mid + 1, end, value);
seg[now] = seg[now * 2] + seg[now * 2 + 1];
}
void update_lazy(int now,int start, int end){
if (lazy[now] != 0) {
seg[now] += (end - start + 1) * lazy[now];
// 자신의 자식 리프노드의 갯수만큼 segment tree에 더해줌
if (start != end) { // 만약 리프노드가 아니라면
lazy[now * 2] += lazy[now];
lazy[now * 2 + 1] += lazy[now];
// 자신의 자식들의 노드에게 lazy 전달
}
lazy[now] = 0; // 해당 세그먼트 트리 노드에 대해서 업데이트 완료 했음으로 lazy 초기화
}
}
void update_range(int now, int left, int right, int start, int end, ll value) {
update_lazy(now, start, end);
if (left > end || right < start) return;
if (left <= start && end <= right) {
seg[now] += (end - start + 1) * value;
if (start != end) {
lazy[now * 2] += value;
lazy[now * 2 + 1] += value;
}
return;
}
int mid = (start + end) / 2;
update_range(now * 2, left, right, start, mid, value);
update_range(now * 2 + 1, left, right, mid + 1, end, value);
seg[now] = seg[now * 2] + seg[now * 2 + 1];
}
ll query(int now, int left, int right, int start, int end) {
update_lazy(now, start, end);
if (left >end || right < start) return 0;
if (left <= start && end <= right) {
return seg[now];
}
int mid = (start + end) / 2;
return (
query(now * 2, left, right, start, mid) +
query(now * 2 + 1, left, right, mid + 1, end)
);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int N, M, K;
cin >> N >> M >> K;
for (int i = 0; i < N; i++) {
ll data; cin >> data;
update_tree(1, i, 0, N - 1, data);
}
for (int i = 0; i < M + K; i++) {
int tag; cin >> tag;
if (tag == 1) { // b ~ c , d update
int b, c; ll value;
cin >> b >> c >> value;
update_range(1, b - 1, c - 1, 0, N - 1, value);
}
else { // b ~ c 구간합
int b, c; cin >> b >> c;
cout << query(1, b - 1, c - 1, 0, N - 1) << endl;
}
}
}'알고리즘 > [C++]BOJ' 카테고리의 다른 글
| [백준BOJ] 1395 스위치 (0) | 2019.10.04 |
|---|---|
| [백준BOJ] 1626 두 번째로 작은 스패닝 트리 (0) | 2019.10.03 |
| [백준BOJ] 15481 그래프와 MST (0) | 2019.10.03 |
