백준 2042: 구간 합 구하기 (Segment Tree / with PythoN)

 

 

Segment Tree 구현은

1. segment( 1차원 배열에 담겨있는 Data를 기준으로 Segment Tree를 만들어주는 함수 )

2. update ( idx째에 있는 원소에 diff만큼의 변화를 줌)

3. subsum (구간합 구해주는 함수)

 

 

Point

 

우리가 펜윅트리 (Binary Index Tree)를 구현할 때는 arr과 tree모두 1번 인덱스부터 사용했지만,

Segment Tree에서는 arr은 0번부터 붙여서 사용해야한다.

(Tree는 자식노드 번호를 2*node, 2*node + 1로 사용해야하므로 BIT와 동일하게 1번이 루트노드가 되어야한다)

그 이뉴는 arr을 1번부터 사용할 경우 완전 이진트리 형태로 Segment  Tree를 만들 수 없기 때문이다.

 

( 0 ~2를 루트노드가 합으로 갖고있다고 생각하자.  이 경우 left노드가 0~ (0+2) // 2 로 0~ 1까지 총 두 자식노드를 가지고,

right노드가 (0+2) // 2 + 1 ~ 2 로 "2" 하나만을 자식노드를 가져 우리가 생각하는 완전이진트리 형태로 구성할 수 있다.

 

물론! mid를 구하는 과정 (start_index + end_index) // 2 

이 연산을 (start_index + end_index)  / 2.0 연산 후 올림하는 방식으로 한다면, 

arr배열을 1번부터 n번까지로 사용해도 된다.

그치만 이 방식보다는 0~n-1번으로 사용하면서 그냥 몫연산으로 mid를 구하는것이 간편할 것이다!