[백준 2042] 구간 합 구하기

[ 백준 2042 : 구간 합 구하기 ]

처음 문제를 보고 세그먼트 트리로 풀어야겠네 이런 생각을 하게된다.
만약 세그먼트트리를 모른다면 <백준 세그먼트 트리 설명> 해당 링크에 엄청나게 자세히 설명되있다.

어제 인덱스트리라는 로직을 새롭게 배웠는데 너무 인상깊어서 인덱스 트리 방식으로 풀어봤다.
사실 세그먼트 트리 코드가 왠만하면 위의 설명에 나온 코드나 흔히 말하는 종만북 이라는 책에 나온대로 설계하고 구현한다.
엄청 복잡(사실 복잡하진 않다.) 하고 코드가 매우 길다.

인터넷에서도 세그먼트트리 알고리즘을 사용하는 문제 풀이를 찾아보면 거의 비슷비슷하게 나와있는것을 알 수 있다.
벡터로다가 사이즈 먼저 설정하고 초기화 시키고~ 사실 인덱스 트리도 똑같은 방법이긴 한데 조금 더 쉽게 구현할 수 있어서 적어본다.

일단 기본 로직은 세그먼트 트리와 비슷하다. 초기화를 먼저 시키는데 이때 배열의 사이즈를 임의대로 n*4를 한다.

n이 10이라고 가정하면
가장 밑단에 들어가는 데이터 10개의 공간이 필요하다. 이건 입력으로 주어지는 배열과 사이즈가 같다.
그 위 층으로는 두개씩 묶어 부모이자 해당 구간의 쿼리를 저장 할 공간 5개가 필요해다.
그 위 층은 또 두개씩 묶어 3개가 필요한데 범위 10을 넘으니 임의로 0을 저장한다.
이런식으로 하면 총 25개가 필요한데 넉넉하게 그냥 4배를 잡는다.

트리 사이즈를 잡았다면 이제 초기화를 시켜준다. 초기 값은 트리사이즈-n 부터 트리사이즈까지 입력 배열들이 들어간다.
그리고 /2를 하면서 해당 공간에 문제에서 요구하는 쿼리값을 집어넣는다. 만약 쿼리가 구간의 합을 구하는 것이라면
트리의 인덱스를 /2하면서 +입력배열[i]를 해주는 식으로
그럼 초기화는 끝난다.

업데이트는 트리사이즈 - N + (업데이트 하는 인덱스)부터 /2를 해가면서 트리의 값을 수정해준다. 정말 간단하다.

쿼리함수는 조금 복잡한데
흔히 알려진 세그먼트 트리 구현하는 것보다는 간단하다. 기본 로직은

구간 시작 인덱스 IDX1 , 구간 끝 인덱스 IDX2, 결과값 RET 이라고 가정해본다.
그럼 IDX1 = 트리사이즈 - N +IDX1이 트리의 가장 밑단, 입력배열의 값이된다.

while(IDX1<=IDX2) IDX1이 홀수라면 해당 트리의 값을 RET에 갱신시킨다. 그리고 IDX1을 +1 해준다. IDX2가 짝수라면 해당 트리의 값을 RET에 갱신시킨다. IDX2를 -1 해준다. IDX1 과 IDX2를 /2해준다. 사실 배열을 그림으로 그려서 이해하면 왜 이렇게 하는지 알게되는데 직접 그려보고 이해하면 진짜 인덱스트리는 이제 자기것이라고 보면될 것 같다. 이런식으로 구간합구하기 문제를 풀었는데 처음에 트리 사이즈를 잘못구해 몇 번을 틀렸는지 모르겠다... 비슷한 문제로 [최소값] 와 엄청나게 많으니 풀어보길 추천한다.