📌 선행 개념
해당 알고리즘은 세그먼트 트리에 대한 이해가 필요한 알고리즘입니다.
세그먼트 트리
📌 범위 업데이트에 대한 세그먼트 트리 시간 복잡도
세그먼트 트리의 장점은 부분에 대한 정보를 가지고 있다는 점이고, 특정 index의 원소가 변경되어도 그 index가 포함된 부분의 정보만 수정하면 되기 때문에 간단합니다. 그러나 한 번에 여러 개의 노드의 정보가 변경된다면 시간 복잡도는 크게 증가합니다. 단일 노드에 대한 갱신 시간 복잡도는 O(logN)이었습니다. 이것이 범위로 확장된다면 O(NlogN)이 됩니다. 구간의 크기 만큼 leaf 노드까지 방문해야 하기 때문입니다. 이러한 갱신의 횟수가 증가하면 증가할수록 시간복잡도는 크게 증가합니다.
다음과 같은 문제를 해결할 때는, 기존에 세그먼트 트리로 해결하게 된다면 O(MNlogN)의 시간복잡도를 가지게 되고, 문제를 해결할 수 없게 됩니다. 따라서 이러한 상황에서는 느리게 갱신되는 세그먼트 트리를 이용해야 합니다. (Lazy Propagation)
📌 Lazy Propagation의 기본 원리
Lazy Propagation은 기본적으로 Lazy라는 배열을 갖습니다. 트리의 각 노드들은 lazy 값과 대응하게 되는데, index값이 변경되어도 즉각적으로 갱신하지 않습니다. 갱신할 필요가 있는, 나중에 해당 노드를 방문하여 정보를 이용할때까지 갱신을 미루어서 시간적 효율을 높입니다.
📌 Lazy Propagation의 동작
index 4부터 10까지의 원소를 갱신한다고 생각해보자.
index 4 ~ 10 까지의 원소에 + 10
가장 최상단인 root (1~10)의 경우 구간이 포함되므로 양 자식노드에 대하여 재귀실행한다.
1~5의 경우 역시 포함되므로 양 자식노드에 대하여 재귀실행한다.
1~3의 경우 구간에 포함되지 않으므로, 종료한다.
4~5의 경우 4~10에 완전히 포함되는 구간이므로 구간의 크기( 4~5이므로 2 )만큼에 update되는 값을 증가시킨다. 양쪽 자식 노드는 갱신하지 않고 대응되는 lazy 값에 각각 10씩 저장한다. 나중에 4, 5 직접 방문하게 될 경우에 해당 연산을 수행한다.
해당 노드가 업데이트 하는 구간에 완전히 포함되는 경우 재귀를 멈추고, lazy값을 더해준다.
이렇게 4 ~ 10 구간의 구간 갱신 연산은 끝나게 됩니다. 일반적인 세그먼트 트리와 비교해서 참조하는 노드의 수가 현저하게 적은 것을 확인 할 수 있습니다.
📌 Lazy Propagation 코드
세그먼트 트리 생성 부분을 제외한 느리게 갱신되는 세그먼트 트리 일부분의 코드입니다.
void update_lazy(long long start, long long end, long long node)
{
if (lazy[node] != 0) {
segment_tree[node] += (end - start + 1) * lazy[node];
if (start != end)
{
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
}
// lazy 값을 저장하는 함수이다.
void update_range(long long start, long long end, long long node, long long left, long long right, long long num)
{
update_lazy(start, end, node);
if (left > end || right < start) return;
if (left <= start && end <= right)
{
segment_tree[node] += (end - start + 1) * num;
if (start != end)
{
lazy[node * 2] += num;
lazy[node * 2 + 1] += num;
}
return;
}
int mid = (start + end) / 2;
update_range(start, mid, node * 2, left, right, num);
update_range(mid + 1, end, node * 2 + 1, left, right, num);
segment_tree[node] = segment_tree[node * 2] + segment_tree[node * 2 + 1];
}
// 구간에 대한 업데이트를 직접 실시하는 부분이다. lazy값 참조에 대한 부분을 확인하기 위해서 update_lazy를 포함하고 있다.
long long find_sum(long long start, long long end, long long node, long long left, long long right)
{
update_lazy(start, end, node);
if (right < start || end < left)
return 0;
if (left <= start && end <= right)
return segment_tree[node];
int mid = (start + end) / 2;
return find_sum(start, mid, node * 2, left, right) + find_sum(mid + 1, end, node * 2 + 1, left, right);
}
// 수정이 모두 완료되거나 완료되기 전에 부분합에 대한 쿼리문이다. 참조하는 경우 값을 업데이트 해준다.
📌 마무리
느리게 갱신되는 세그먼트 트리의 경우, 구간 업데이트 부분에 대해서 시간 복잡도에서 강점을 갖습니다. 방문(참조)하는 노드의 수가 현저히 적기 때문에, 특정 index가 아니라 특정 범위에 대한 갱신을 하기 위해서는 해당 알고리즘을 사용해야 합니다.
구간 갱신에 대한 세그먼트 트리의 시간 복잡도 : O(NlogN)
구간 갱신에 대한 lazy propagation 알고리즘의 시간 복잡도 : O(logN)
