The Segment Tree with the Maximum Sum

 

INTRODUCTION

  이번 포스팅에서는 최대 연속 부분합을 다루는 세그먼트 트리에 대해 다루고자 한다.

이 기술은 대한민국에서 특히 더 잘 알려져 있다. 2014년 한국정보올림피아드 중등부 4번 문제 금광을 통해 유명해졌으며 이로 인해 주로 "금광 세그"라는 이름으로 불린다.

 

  해당 세그먼트 트리에 관해서는 Codeforces에서 찾을 수 있는 ITMO Academy: pilot course에서도 다루었다. 강의가 필요하다면 확인하기 바란다.

https://codeforces.com/edu/course/2/lesson/4/2

Courses - Codeforces

IDEA

우리가 segment tree를 이용할 때를 생각해 보자. tree의 노드가 관리하는 segment를 다른 두 개의 segment로 나누고 그 나뉜 segment를 관리하는 노드를 설정한다. 그리고 나뉜 두 개의 segment를 관리하는 노드들이 가지고 있는 정보를 이용하여 조금 더 큰 segment의 정보를 관리한다. 이제, 어떻게 각 segment의 maximum subarray를 관리할지 고민해 보자. 일단, 현재 segment를 \(\mbox{seg}_0\)라 하고, 이 segment가 \(\mbox{seg}_1\), \(\mbox{seg}_2\)로 나뉘어 있다고 하자. 그러면, 여기서 \(\mbox{seg}_0\)의 maximum subarray를 구하기 위해, \(\mbox{seg}_1\)와 \(\mbox{seg}_2\)의 어떤 정보를 알아야 할까?

 

METHOD

Maximum Subarray

\(\mbox{seg}_1\)와 \(\mbox{seg}_2\)를 연결한 형태를 살펴보자. fig 1은 위에서 링크해 둔 강의의 그림이다.

\(\mbox{seg}_0\)의 maximum subarray의 값이 될 수 있는 경우는 총 3가지이다.

 

1. maximum subarray가 \(\mbox{seg}_1\)과 \(\mbox{seg}_2\)에 걸친 원소들의 합인 경우

2. \(\mbox{seg}_1\)와 \(\mbox{seg}_0\)의 maximum subarray가 같은 경우

3. \(\mbox{seg}_2\)와 \(\mbox{seg}_0\)의 maximum subarray가 같은 경우

 

즉, \(\mbox{seg}_1\)의 maximum suffix sum과 \(\mbox{seg}_2\)의 maximum prefix sum 합, \(\mbox{seg}_1\)의 maximum subarray 그리고 \(\mbox{seg}_2\)의 maximum subarray이다.

fig1

모든 segment에 대해 이 연산을 하기 위해서, 우리는 각 segment의 maximum prefix sum과 maximum suffix sum 도 알고 있어야 한다.

 

Maximum Prefix Sum and Maximum Suffix Sum

\(\mbox{seg}_0\)의 maximum prefix sum이 될 수 있는 것은 두 가지가 있다.

1. \(\mbox{seg}_1\)과 \(\mbox{seg}_0\)의 maximum prefix sum이 같은 경우

2. \(\mbox{seg}_1\)의 전체 합 + \(\mbox{seg}_2\)의 maximum prefix sum이 \(\mbox{seg}_0\)의 maximum prefix sum인 경우

 

Maximum suffix sum이 될 수 있는 것 또한 두 가지이다.

1. \(\mbox{seg}_2\)와 \(\mbox{seg}_0\)의 maximum suffix sum이 같은 경우

2. \(\mbox{seg}_1\)의 maximum suffix sum + \(\mbox{seg}_2\)의 전체 합이 \(\mbox{seg}_0\)의 maximum suffix sum인 경우

\(\mbox{seg}_0\)
\(\mbox{seg}_1\)	\(\mbox{seg}_2\)

이 연산을 위해서 각 segment의 합 또한 알고 있어야 한다.

나머지는 일반적인 segment tree와 같으며, 연산을 위에서 설명한 대로만 해주면 된다.

 

 

아래는 필자가 구현한 것이다.

https://github.com/Sora-Sugiyama/Libs/blob/main/Data-Structure/MSA_SEGTREE.h

GitHub - Sora-Sugiyama/DG1S-Algorithm-Resarch-Club