백준 2042번 구간 합 구하기

< 백준 2042번 구간 합 구하기 - 마포 코딩박 >

사용한 알고리즘: 세그트리


 구간합을 구하는 문제였습니다. 저는 세그트리를 써서 해결하였습니다.
 ( Fenwick tree 나 기타 다른 방법으로도 구현이 가능합니다. )

문제풀이는 다음과 같습니다.
(1) (코드 4, 7)
 N 이 최대 10^6 입니다.
 Segtree 크기는 2 제곱으로 잡아줘야 합니다. ( node가 8개일때 생각하면 편합니다. )
 2^20>10^6 이므로 노드개수가 2^20 개라 생각했습니다.
 노드들을 쌓아올릴 2^20개가 추가로 필요하여 총 2*2^20 으로 배열 크기를 잡았습니다.

(2) (코드 22~30)
 세그트리를 업데이트 (구성) 하는 코드입니다.
 해당 index 를 바꿀 숫자로 바꾼 후 위에 쌓아올린 칸을 바꿔줍니다.

(3) (코드 8~20)
 구간합을 구하는 코드입니다.
 Segtree 의 Root 인 index=1 인 지점부터 차례로 보며 원하는 구간에 쏙 들어오는 index칸의 값을 구해줍니다.

 세그트리가 한번에 생각이 어려우신 분들은 8개의 노드들을 쌓아올리는걸 그려보시면 편합니다. ( 저도 항상 8개 가지고 생각을 합니다. )