간단한 설명을 위해 변경되는 배열의 구간합 구하기 문제정도로 예시를 들어 설명드리겠습니다.
혹시 세그먼트 트리를 모르신다면 여기를 눌러주세요.
동적 세그먼트 트리란 무엇일까
정의
영어로 Dynamic Segment Tree 즉 값의 수정됨에 따라 동적으로 세그먼트 트리의 모양이 변하는 것을 의미합니다.
목적
기존 세그먼트 트리보다 효율적으로 메모리를 사용하기 위해 고안된 자료구조입니다.
기존 세그먼트 트리의 공간 복잡도는 1 ~ N까지의 숫자들로 이루어진 숫자들을 저장하기 위해서 약 의 공간 복잡도가 필요하였습니다. 하지만 N이 10억개라고 한다면 공간 복잡도는 커지게 될 것입니다. 하지만 저장되는 숫자가 10만개로 적은 경우 10만개의 숫자를 저장하기 위해 10억개 약 1000배의 공간복잡도를 필요하게 되니 이는 공간 복잡도를 낭비하지 않기 위해 고안된 자료구조입니다.
동적 세그먼트 트리 아이디어
위와 같이 8개의 수를 저장하고 구간 합을 저장하는 노드들의 수는 15개입니다.
하지만 3개의 수를 저장한다면 3개의 수를 저장하기 위해 무려 15개의 노드를 사용하는 낭비를 보여주게 됩니다.
이때 위와 같이 필요가 없는 노드를 제거한다면 3개의 노드를 저장하기 위해 8개의 노드를 사용하게 되어 공간을 무려 반을 줄이게 됩니다.
동적 세스먼트 트리의 동작 개념
가장 중요한 개념은 “필요없는 부분을 제거하고 필요하면 생성한다”입니다.
초기 상태
초기 상태는 루트 노드가 하나 존재하면 됩니다. 자식 노드들은 데이터 추가를 통해 생성됩니다.
데이터 추가 - 노드 생성
해당 데이터의 위치까지 갈 때 필요한 노드를 생성 및 업데이트를 진행합니다.
데이터 1 추가
기존 세그먼트 트리에서 데이터 1을 조회하기에 필요한 노드들을 빨간색으로 색칠하였습니다. 바로 저 노드들만 생성하고 저장하면 됩니다.
데이터 4 추가
업데이트가 필요한 노드는 노란색, 생성이 필요한 노드는 빨간색으로 처리하였습니다.
따라서 필요한 노드들을 생성 및 업데이트를 진행합니다.
데이터 삭제 - 노드 삭제
해당 데이터를 삭제하고 업데이트할 때, 해당 노드의 필요성을 파악하고 필요가 없는 경우 제거합니다.
데이터 4 삭제
4를 삭제할 경우 업데이트가 필요한 노드들을 빨간색으로 색칠하였습니다.
업데이트를 한 후 0을 저장하고 있는 경우 해당 노드의 필요성이 없다고 판단하여 해당 노드를 삭제하게 됩니다.
데이터 1 삭제
데이터 1을 삭제하면 모든 노드가 업데이트가 됩니다.
루트 노드는 삭제하지 않으며 자식 노드이면서 0을 가지는 모든 노드를 삭제합니다.
조회
조회는 기존과 거의 같으며 하위 노드가 존재하지 않는 경우 조회하지 않습니다.
위와 같이 세그먼트 트리가 구성됩니다.
2 - 5 구간 합 조회
하늘색은 조회를 위해 지나가는 구간, 노란색은 결과에 반영될 노드입니다.
2 - 4의 경우 기존 세그먼트 트리의 조회 방법으로 조회가 가능합니다.
하지만 우측의 경우 좌측 노드가 비어있어 기존 세그먼트 트리의 조회 방법으로 조회하면 Null에러가 나오며 실패할 것입니다. 하지만 위와 같이 빈 경우 조회하지 않고 지나가시면 기존 세그먼트 트리와 동일하게 조회가 가능합니다.
코드
깃허브
문제 링크
https://www.codetree.ai/training-field/frequent-problems/problems/codetree-db
