162. Segment Tree with Lazy Propagation

다음과 같은 쿼리를 처리하는 문제를 생각해 보자.

$1\ x\ y\ k$: $x$번째 수부터 $y$번째 수까지에 $k$를 더한다.

$2\ x\ y$: $x$번째 수부터 $y$번째 수까지의 합을 출력한다.

 

만약 세그먼트 트리를 이용해서 이 쿼리를 처리하려고 한다면 $1$번 쿼리를 처리할 때 원소의 값을 바꾸는 작업을 $y - x + 1$번 실행해야 하고, 수의 개수가 $n$이라면 이 작업에는 $(y - x + 1) \lg n$만큼의 시간이 걸린다. 즉 이 시간은 바꿔야 하는 구간의 크기에 영향을 받는다. 만약 $x = 1, y = n$이라면 $1$번 쿼리 하나를 처리하는 데 $n \lg n$만큼의 시간이 걸릴 것이고 이런 쿼리가 $m$개 있다면 $nm \lg n$만큼의 시간이 걸리게 된다. 이런 시간복잡도로는 $n$과 $m$이 $10^5$ 정도인 문제를 풀기 어렵다.

---

느리게 갱신되는 세그먼트 트리(Segment Tree with Lazy Propagation)^[각주:1]는 $1$번 쿼리를 $O(lg n)$ 시간만에 처리하여 $m$개의 쿼리를 $O(m \lg n)$ 시간에 처리할 수 있는 세그먼트 트리이다. 이름에서 나타나듯 갱신을 미루는 방법을 통해서 쿼리를 빠르게 처리할 수 있는데, 어떻게 미루는 건지 예시를 들어 살펴보기로 한다.

$n = 8$이고 초기값이 리프 노드에 적힌 것과 같은 수열이 있다고 하자. 여기서 $5$번째 수에 $2$를 더하면 다음과 같이 노드들의 값이 바뀔 것이다.

여기서 기존 수열과 새로 더해진 값을 분리해 보자. 즉 다음과 같이 두 개의 세그먼트 트리가 있고 원소들의 초기값을 저장한 첫 번째 세그먼트 트리는 변하지 않은 채로 두 번째 세그먼트 트리에 값이 더해진다고 생각하는 것이다.

이 상태에서 $6$ ~ $8$번째 수에도 전부 $2$씩 더하면 세그먼트 트리의 상태는 다음과 같이 변할 것이다.

세그먼트 트리에서 구간의 값을 갱신하는 쿼리가 느렸던 이유는 루트 노드에서 무조건 리프 노드까지 이동하면서 값들을 전부 다 갱신했기 때문이었다. 느리게 갱신되는 세그먼트 트리는 이 과정을 최적화함으로써 쿼리를 빠르게 처리한다. 먼저 값을 변경하는 쿼리를 어떻게 처리하는지 살펴보자. $2$ ~ $4$번째 수에 각각 $3$을 더할 것이다. 루트 노드부터 탐색을 진행한다.

이제부터 오른쪽 세그먼트 트리는 해당 노드를 조상으로 하는 리프 노드들에 더해야 하는 값을 저장한다. 일단 탐색하는 노드에 대응하는 구간의 일부만 $[2, 4]$에 포함되므로 양쪽 자식 노드를 탐색하는데, 그전에 해야 할 작업이 있다.

• 왼쪽 세그먼트 트리에서 현재 노드에 대응하는 노드의 값을 갱신(Update)한다.
• 현재 노드가 리프가 아닌 경우, 현재 노드에 있는 '더해야 하는 값'을 양쪽 자식 노드에 전파(Propagation)한다.
• 현재 노드에 있는 더해야 하는 값을 $0$으로 초기화한다.

왼쪽 세그먼트 트리에서 노드의 값을 갱신할 때는 (더해야 하는 값) $\times$ (노드에 대응하는 구간의 길이)를 더하면 된다. 현재는 더해야 하는 값이 $0$이라서 갱신을 해도 값이 그대로이다. 이어서 더해야 하는 값 $0$으로 자식 노드에 전파하고, 더해야 하는 값을 초기화하고 양쪽 자식 노드를 탐색한다.

계속해서 양쪽 자식 노드를 탐색해야 하는 상황이 발생하므로 자식 노드로 계속해서 내려간다.

리프 노드까지 내려왔다. 리프 노드에서는 전파를 생략한다. 또한 이 노드에 대응하는 구간 $[1,1]$이 $[2, 4]$와 겹치지 않으므로 부모 노드로 돌아가 오른쪽 자식 노드를 탐색한다.

이 노드에 대응하는 구간 $[2, 2]$는 $[2, 4]$에 완전히 포함된다. 이런 노드에서는 갱신 전에 한 가지 처리를 더 해야 한다.

• 이 노드의 값에 구간에 더하는 값을 더한다.

그래서 이 노드의 값은 먼저 $0$에서 $3$으로 변하고,

그 다음에 갱신이 일어난다.

다시 부모 노드로 돌아가는데, 부모 노드의 탐색이 종료될 때 또 한 가지 작업을 해야 한다.

• 왼쪽 세그먼트 트리에서 대응하는 노드의 값을 양쪽 자식 노드의 합으로 바꾼다.

따라서 왼쪽 세그먼트 트리에 있는 왼쪽 $9$는 $12$로 바뀐다.

이제 나머지 노드들은 위에서 설명한 대로 탐색하면 된다.

이 노드에서 갱신과 전파를 완료하면 다음과 같이 되는데 이 노드에 대응하는 구간 $[3, 4]$가 $[2, 4]$에 완전히 포함되므로 처리가 끝나면 부모 노드로 돌아간다. 따라서 두 자식 노드에는 값 $3$이 그대로 남아 있게 되고 대응하는 왼쪽 세그먼트 트리의 노드들의 값은 변하지 않는다.

즉 부모 노드의 값이 양쪽 자식 노드의 값의 합과 다르지만, 이것이 바로 오른쪽 세그먼트 트리에서 갱신을 뒤로 미룬 상태인 것이다.

계속해서 탐색을 진행한다.

이 노드는 자식 노드로 더이상 들어가지 않고 바로 부모 노드로 돌아가게 된다. 루트 노드까지 값의 갱신이 완료되면 탐색을 종료한다.

세그먼트 트리와 마찬가지로 층마다 최대 $4$개의 노드만 탐색하므로 이 쿼리를 처리하는 시간복잡도는 $O(\lg n)$이다.

---

이번에는 합을 구하는 쿼리를 어떻게 처리하는지 살펴보자. 사실 값을 변경하는 쿼리를 이런 식으로 처리했다면 합을 구하는 쿼리를 처리하는 것은 매우 쉽다. 값을 변경하는 쿼리를 처리할 때 값이 변한 구간의 합을 반환하게 하면 된다. 예를 들어 앞에서 값을 변경하는 쿼리를 처리했을 때는 $2$ ~ $4$번째 수들의 합인 $19$를 반환한다.

그렇다면, 어떤 구간의 합을 구하는 것은 그냥 그 구간에 $0$을 더하는 쿼리를 처리하고 반환값을 얻으면 끝난다. 따라서 값을 변경하는 쿼리와 동일한 $O(\lg n)$의 시간복잡도로 쿼리를 처리할 수 있다.

 

구현은 다음과 같다. 전처리는 세그먼트 트리와 거의 동일하다.

int n, p = 1 << 17, a[1 << 18], l[1 << 18], r[1 << 18], lazy[1 << 18];

for(int i = 0; i < p; i++)l[p + i] = r[p + i] = i;
for(int i = p; --i;)
{
    l[i] = l[i << 1];
    r[i] = r[i << 1 | 1];
} // i번 노드에 대응하는 구간은 [l[i], r[i]]가 된다.

cin >> n;
for(int i = 1; i <= n; i++)cin >> a[p + i];
for(int i = p; --i;)a[i] = a[i << 1] + a[i << 1 | 1];

값을 변경하고 합을 구하는 쿼리는 다음과 같이 구현할 수 있다. 두 쿼리를 하나의 함수로 처리할 수 있어서 간편하다.

int REP(int x, int y, int d, int k) // x번째 원소부터 y번째 원소에 각각 k를 더해야 하고, 현재 탐색하는 노드가 d번인 경우
{
    if(x <= l[d] && r[d] <= y)lazy[d] += k;
    a[d] += (r[d] - l[d] + 1) * lazy[d]; // Update
    if(d < p) // Propagation
    {
        lazy[d << 1] += lazy[d];
        lazy[d << 1 | 1] += lazy[d];
    }
    lazy[d] = 0;
    
    if(x <= l[d] && r[d] <= y)return a[d];
    if(x > r[d] || l[d] < r)return 0;
    int v = REP(x, y, d << 1, k) + REP(x, y, d << 1 | 1, k);
    a[d] = a[d << 1] + a[d << 1 | 1];
    return v;
}

값을 변경하는 쿼리는 $\text{REP}(x, y, 1, k)$를, 구간의 합을 구하는 쿼리는 $\text{REP}(x, y, 1, 0)$을 호출하면 된다.

 

이제 구간 업데이트 + 구간 쿼리를 $O(n \lg n)$에 처리할 수 있다. ( 점 업데이트 + 구간 쿼리나 구간 업데이트 + 점 쿼리는 그냥 세그먼트 트리만으로도 처리가 가능함을 앞에서 소개했다.) 기본 세그먼트 트리만큼이나 응용이 많이 되기 때문에 다양한 응용 방식을 알아 두면 좋다.

 

[연습문제]

 

BOJ 10999. 구간 합 구하기 2 (Platinum IV)

느리게 갱신되는 세그먼트 트리로 풀 수 있는 기본적인 문제이다.

 

BOJ 14245. XOR (Platinum IV)

이번에는 구간의 XOR을 구해야 하는데 합 대신 XOR을 구하는 식으로 코드를 수정하면 된다.

 

BOJ 10277. JuQueen (Platinum II)

최댓값과 최솟값을 구하는 레이지 세그먼트 트리를 사용하는 문제이다.

 

BOJ 22873. A+B와 쿼리 (Platinum II)

특정 위치에서 왼쪽으로 연속한 $0$이나 $9$의 개수를 세야 한다. 느리게 갱신되는 세그먼트 트리에서의 이분 탐색을 쓰면 풀 수 있다. 다른 풀이들도 존재한다고 하는데 자세히는 모른다.

 

BOJ 13925. 수열과 쿼리 13 (Platinum I)

수열의 값에 $ax + b$ 연산을 하는 레이지 세그먼트 트리를 이용하면 된다. 이런 유형도 가끔씩 나온다.

 

BOJ 27530. UFO in the Sinchon (Diamond V)

좌표를 정렬한 다음 $ax + b$ 레이지 세그먼트 트리를 사용해서 최종 좌표를 구한다. $x$좌표와 $y$좌표를 따로 처리한다.

 

BOJ 25727. Building Bombing (Diamond V)

이번에는 DP를 느리게 갱신되는 세그먼트 트리로 처리하는 문제이다. 이번에도 $ax + b$ 레이지 세그먼트 트리를 써서 풀 수 있다. 자세한 풀이는 까먹어서..

 

→ solved.ac tag: lazyprop

---

 

1. 사실 영어를 직역하면 '느리게 전파되는 세그먼트 트리'라고 하는 게 자연스럽지만 '느리게 갱신되는 세그먼트 트리'가 꽤 널리 쓰이고 있으므로 여기서는 이 용어를 쓰기로 한다. 그밖에 이 용어가 좀 길다 보니 세그레이지, 레이지세그 등 여러 줄임말이 존재한다. [본문으로]