segment tree

세그먼트 트리는 어떤 범위에 대한 쿼리를 효율적으로 대답해 줄 수 있는, 또 그러면서 수정도 가능한 자료구조 중 하나입니다.

아래와 같은 쿼리 2개를 생각해 봅시다.

1. 길이가 N인 어떤 수열 A에서 A[i]부터 A[j]까지의 합을 구하라

2. 길이가 N인 어떤 수열 A에서 A[i]를 v로 바꿔라

일반적인 경우 이 두 쿼리는 $O\left ( N \right )$으로 해결 할 수 있습니다.

그런데 구간 트리를 이용하면 $O\left ( logN \right )$으로 쿼리를 해결 할 수 있습니다.

 

segment tree

위 그림과 같이 각 노드가 구간을 커버하면서 구간에 해당하는 값을 가지고 있는 형태를 세그먼트 트리는 가지고 있습니다.

 

세그먼트 트리 예시

1번이 루트 노트이고 아래로 2,3번을 자식 노드로 갖는점에 유의해주세요!

 

세그 트리를 구현하는데는 몇가지 어려운 점이 있습니다.

1. 세그 트리의 사이즈

인터넷에서는 쉽게 4*N 정도를 메모리에 잡아줍니다.

저는 $2^{\left ( log_{2}\left ( N \right )+1 \right )+1}$정도를 메모리에 잡아줍니다.

아마 정확한 사이즈는 $2^{\left \lceil logN\right \rceil+1}$인걸로 알고 있는데 보통 올림을 해줘야하다보니 지금까지는 그냥 더해서 사이즈를 잡았습니다.

2. 어디서부터 어디까지?

세그 트리에서는 보통 method의 param으로 노드 번호, 시작, 끝, 구하고자 하는 범위(Left, Right)를 넘겨줍니다.

이때 루트 노드가 관리하는 시작은 1부터(1-based) 끝은 N보다 큰 $2^{k}$ 중 가장 작은 값입니다.(Trivial)

 

*소스 코드 추가 예정

 

관련 문제

 

수열과 쿼리 15

수열과 쿼리 16

수열과 쿼리 17

 

풀이 추가 예정