백준 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를 루트노드가..
Python알고리즘
2023. 10. 21. 19:35
