티스토리 뷰
a번째 수 부터 b번째 수 까지의 합 구하기
7개의 수 1, 10, 3, 6, 5, 6, 4가 있을 때
a번째 수 부터 b번째 수 까지의 합을 구하는 상황을 생각해봅시다.
2번째 수 부터 4번째 수 까지의 합을 구하라는 질의가 들어오면
10+3+6 = 19
2번째 수 부터 7번째 수 까지의 합을 구하라는 질의가 들어오면
10+3+6+5+6+4 = 34
처럼 a번째 수에서 b번째 수까지를 순회하면서 합을 구하면 됩니다.
이와 같은 방법으로 a번째 수 부터 b번째 수까지의 합을 구하면 숫자의 개수가 N개, 질의의 개수가 M개일 때
M개의 질의 각각에 대해 최대 N번 순회해야하므로 시간복잡도는 O(NM)이 됩니다.
이 보다 더 빠르게 할 수 있을까요?
다음과 같이 배열을 sum을 정의합시다.
sum[i] = 1 번째 수 부터 i번째 수
이제 1~9번째 수까지 순회하면 아래 표와 같이 sum배열을 채울 수 있습니다.
i |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
sum[i] |
1 |
11 |
14 |
20 |
25 |
31 |
35 |
이제 다시 a번째 수 부터 b번째 수 까지의 합을 구하는 상황을 생각해봅시다.
2번째 수 부터 4번째 수 까지의 합을 구하라는 질의가 들어오면
sum[4]-sum[2-1] = 19
1번째 수 부터 7번째 수 까지의 합을 구하라는 질의가 들어오면
sum[7]-sum[2-1] = 35
처럼 a번째 수에서 b번째 수까지를 순회하면서 합을 구하면 됩니다.
이와 같은 방법으로 a번째 수 부터 b번째 수까지의 합을 구하면 숫자의 개수가 N개 질의의 개수가 M개일때
sum 배열을 전처리하는데 필요한 시간 O(N)이 필요하고
M개의 질의 각각에 대해 최대 O(1)번 연산이 필요합니다. 따라서 전체 시간복잡도는 O(N+M)이 됩니다.
이와 같이 sum 배열을 전처리해서 이전 방법보다 훨씬 빠르게 수행할 수 있습니다.
k번째 수를 바꿀 때 a번째 수 부터 b번째 수 까지의 합 구하기
이 경우 위와 같이 sum배열을 전처리해서 이득을 얻을 수 없습니다.
만약 3번째 수가 바뀌면 sum배열의 3~9번째 값을 모두 바꿔줘야하기 때문에
O(N)번의 연산과정이 매 질의 마다 추가로 발생하기 때문입니다.
그럼 K번째 수가 바뀌는 상황에서 a~b번째 수들의 합을 빠르게 구하는 방법이 있을까요?
있습니다! Segment Tree를 이용하면 됩니다!
Segment Tree
Segment Tree란 구간의 대표값을 트리형태로 저장하는 자료구조 입니다.
각 노드는 자식 노드들을 대표하는 값을 가집니다.
7개의 수를 나타내는 Sement Tree를 아래 그림으로 표현했습니다. 아래 그림의 각 노드에는 대표하는 구간의 범위를 표기하였습니다.
구간 a~b를 대표하는 노드의 왼쪽 자식은 a ~ (a+b)/2 구간을, 오른쪽 자식은 (a+b)/2+1 ~ b 구간을 대표하도록 정했습니다.
이제 위에서 사용한 예시 1 10 3 6 5 6 4와 같이 7개의 수를 segment트리로 나타내보겠습니다.
합을 구해야하는 상황이기 때문에 대표값은 합을 표기합니다.
각 노드에 구간/대표값 형식으로 값을 나타냈습니다.
이진 트리인 Segment트리의 높이만큼의 대표노드가 업데이트 되기 때문입니다.
Segment Tree 에서 합을 구할 때
Segment 트리에 익숙해 지기 위해 특정 구간에 질의가 들어올 때 어떤 대표값이 선택되는지 색칠해보겠습니다.
1. 1~4 구간의 합을 구하라
1~4구간은 초록색으로 나타낸 하나의 대표노드로 합을 구할 수 있습니다. 합은 20
2. 2~6 구간의 합을 구하라
2~6구간은 초록색으로 나타낸 2, 3~4, 5~6 세개의 대표노드로 합을 구할 수 있습니다. 합은 10+9+11 = 30
Segment Tree 에서 합을 구하는 연산의 시간복잡도는 O(logN)입니다. (N : 수열의 길이)
이진 트리인 Segment트리의 높이만큼의 대표노드가 최대로 선택될 수 있기 때문입니다.
Segment Tree 에서 값을 업데이트 할 때
이제 값이 업데이트 되는 경우를 생각해봅시다. 값이 업데이트 되면 그 값을 대표하는 노드의 값을 모두 수정해야 합니다.
1. 7번째 수를 6으로 업데이트 할 때
7번째 수를 대표 구간에 포함하는 노드들을 초록색으로 나타냈습니다. 또 값의 변화를 화살표로 나타냈습니다.
2. 4번째 수를 10으로 업데이트 할 때
4번째 수를 대표 구간에 포함하는 노드들을 초록색으로 나타냈습니다. 또 값의 변화를 화살표로 나타냈습니다.
Segment Tree 에서 하나의 값을 업데이트하는 연산의 시간복잡도는 O(logN)입니다. (N : 수열의 길이)
이진 트리인 Segment트리의 높이 만큼의 대표노드가 최대로 업데이트 될 수 있기 때문입니다.
Segment Tree 구현
백준 온라인 저지 2042번 구간 합 구하기 문제를 Segment Tree로 구현해보겠습니다.
Segment트리를 구현하는 함수의 인자로 node. start. end인자가 모두 포함되는데
node는 트리에서 이 노드의 번호, start와 end는 이 노드가 대표하는 구간의 범위를 의미합니다.
구간 [a,b]를 업데이트 하기
위에서 다룬 것 처럼 한번에 하나의 수를 업데이트 하는것이 아니라
7개의 수 1, 10, 3, 6, 5, 6, 4에 대해 2번째 수부터 6번째 수 까지 10씩 더하라는 것 같이
구간을 업데이트해야 하는 질의가 들어오는 상황을 생각해봅시다.
위에서 사용한 업데이트 방식을 사용하면 업데이트 함수를 2,3,4,5,6번째 숫자에 대해 각각 호출해야합니다.
즉, 길이 N인 수열에 질의가 K번 들어올 때
하나의 수를 Segement Tree에서 업데이트하는데 O(logN)이 필요하므로
한 번의 질의에 최악의 경우 O(NlogN)연산이 필요 합니다. 따라서 전체 업데이트에 O(NKlogN) 연산 필요합니다.
특정한 구간에 대해 업데이트가 필요할 때 이 보다 더 빠르게 하는 방법은 없을까요?
"Lazy Propagation"이라는 개념을 이용하면
하나씩 업데이트해서 구간을 업데이트하는 것이 아니라
한번에 그 구간을 대표하는 노드를 수정해서 O( logN )만에 구간을 업데이트 할 수 있습니다.
Lazy Propagation
Lazy Propagation은 직역하면 게으른 전파라는 뜻으로
게으르게 업데이트를 전파시켜서 O( logN )만에 Segment Tree에서 구간 업데이트를 달성하는 알고리즘입니다.
어떻게 이게 가능한지 알아봅시다.
위에서 계속 예시로 든 7개의 수 1, 10, 3, 6, 5, 6, 4에 대한 Segment Tree에 대해
구간 [1,6]에 5를 더하는 업데이트를 해봅시다.
이 때 대표노드로 선택되는 노드를 파란색으로 색칠하고
오른쪽에 이 구간에 5를 더하는 업데이트가 됬다는 정보를 작은 동그라미로 표시해주었습니다.
앞으로 이 정보를 lazy라고 하겠습니다.
이제 첫번째로 구간 [1,4]의 합을 구하라는 질의가 들어온 상황을 생각해봅시다.
대표노드로 1~4노드가 선택될 것이고 이 구간에 5를 더하라는 정보가 lazy로 남아있으니
대표노드 값 20 + 5(구간 업데이트 정보인 lazy)*4(구간의 길이) = 40으로
구간 업데이트 질의가 들어온 후에도 훌륭하게 구간 합을 처리하는 것을 관찰할 수 있습니다.
그러면 두번째로 구간 [2,4]의 합을 구하라는 질의가 들어온 상황을 생각해봅시다.
이때 선택되는 대표노드를 빨간색으로 색칠했습니다.
위와 같은 과정으로 구간 합을 계산하면
대표노드 값 10 + 0(구간 업데이트 정보인 lazy)*1(구간의 길이)
+ 대표노드 값 9 + 0(구간 업데이트 정보인 lazy)*2(구간의 길이) = 19로
구간 업데이트가 반영된 결과 19+5*3 = 34가 올바르게 나오지 않습니다.
왜 이런 잘못된 결과가 나오는 걸까요?
위쪽 대표노드에서 구간 업데이트된 정보인 lazy가 아래쪽으로 전파되지 않았기 때문입니다.
구간이 업데이트이 되기 위해 대표 노드가 선택될 때 lazy가 아래 그림처럼 모두 아래쪽으로 전파되었다면
대표노드 값 10 + 5(구간 업데이트 정보인 lazy)*1(구간의 길이)
+ 대표노드 값 9 + 5(구간 업데이트 정보인 lazy)*2(구간의 길이) = 34로
구간 업데이트가 반영된 결과가 올바르게 나올 것입니다.
이렇게 한번 구간이 업데이트 될때 마다 이렇게 모든 자손노드에 lazy를 전파시킨다면
훌륭하게 구간업데이트를 수행할 수 있습니다.
그런데 여기서 조금만 더 생각해보면
한번 구간이 업데이트 될때 마다 이렇게 모든 자손노드에 lazy를 전파시키지 않고도
같은 목적을 달성할 수 있음을 알 수 있습니다.
게으르게 전파 시키자
구간 업데이트 정보를 반영하기 위해 조상노드의 lazy가 자손노드에 필요한 상황이라면
반드시 조상노드를 거쳐야 자손노드에 도달할 수 있기 때문에
조상 노드를 지날 때 마다 아래쪽으로 lazy를 전파시키면 됩니다.
이때 한번 아래쪽으로 전파시키고 나면 다음에 또 지나가면서
같은 lazy가 두번 전파되면 안되기 때문에
lazy값을 대표노드의 값으로 반영하고 0으로 만들어 줍니다.
이런 방식으로
한번 구간이 업데이트 될때 마다 부지런하게 모든 자손노드에 lazy를 전파시키지 않고
lazy를 필요할 때 마다 게으르게 조금씩 전파시켜서 동일한 목적을 달성할 수 있습니다.
이제 아래 그래프와 같이 lazy를 가진 트리가 있을 때(위 문단에서 주어진 상황과 별개로 아래와 같은 새로운 트리가 있다고 생각합시다.)
[2,4]의 합을 구하라는 질의가 들어온 상황을 Lazy Propagation 으로 해결 해보겠습니다.
1. 먼저 구간[2,4]를 대표하는 노드를 찾아서 출발합니다.
2. 가던 도중에 lazy가 있는 조상 노드를 만났습니다. lazy를 해당 노드에 반영하고
아래쪽 노드에 전파시켜준 뒤에 동일한 lazy가 두번 연속 전파되지 않기 위해 이 lazy를 0으로 수정합니다.
3. 위 과정을 반복합니다.
4. 위 과정을 반복합니다.
5. lazy를 전파하면서 아래쪽으로 내려오면서 [2,4] 구간을 대표하는 빨간색으로 색칠한 노드에 도달했습니다.
이제 [2,4] 구간합을 계산하면 19+15=34로 올바른 값을 얻을 수 있습니다.
잠깐! 위쪽으로도 전파시켜야 하는거 아닌가?
위와 같이 아래쪽으로 lazy를 전파시켜서
조상노드의 lazy를 자손노드가 필요로 하는 상황을 해결했습니다.
그럼 아래 상황 처럼 자손노드의 lazy를 조상노드가 필요로 하는 경우도 해결해야하지 않을까요?
1. 구간 [1, 2]에 5를 더하는 업데이트 발생
2. 구간 [1, 7]의 합을 구하는 질의가 발생
이렇게 위쪽으로 lazy를 전파시켜야 하는 상황은 세그먼트 트리를
루트에서 출발하는 재귀함수를 이용해서 업데이트 하기 때문에 해결할 수 있습니다.
업데이트 함수가 호출되면 이 함수는 왼쪽 자식과 오른쪽 자식에도 재귀적으로 업데이트 함수를 호출합니다.
업데이트 함수(현재 노드){
//lazy 전파
업데이트 함수(왼쪽 자식 노드)
업데이트 함수(오른쪽 자식 노드)
//여기!
}
이때 //여기! 부분에서 재귀적으로 호출된 두 업데이트 함수가 종료된 상태입니다.
따라서 자식노드에 대한 업데이트가 완료된 상태이므로 자식 노드에는 올바른 값 저장되어 있을 것입니다.
또한 이 트리의 값은 자식 노드의 합을 나타내므로, 아래와 같은 코드를 /여기! 에 추가하여 현재 노드 또한 올바른 값을 얻을 수 있습니다.
tree[현재 노드].value = tree[왼쪽 자식 노드].value + tree[오른쪽 자식 노드].value;
이렇게 한 줄을 추가하므로서 lazy를 위쪽으로 전파시켜야하는 상황도 쉽게 해결할 수 있습니다.
(아래 Lazy Propagation 구현 코드 42번째 라인에서 확인할 수 있습니다.)
Lazy Propagation 구현
Segment Tree의 update와 sum함수에 lazy 전파 부분만 추가하면
쉽게 Lazy Propagation을 적용하여 구간 업데이트가 가능한 자료구조인 Segment Tree를 이용할 수 있습니다.
이때 lazy 전파는 합을 구하는 과정 뿐만 아니라 구간 업데이트 시에도 행해져야 합니다.
백준 온라인 저지 10999번 구간 합 구하기2 문제를 Lazy Propagation을 적용한 Segment Tree로 구현해보겠습니다.
- Total
- Today
- Yesterday