백준/ Gold 1 문제 , 백준 파이썬 2042 , 구간 합 구하기 [세그먼트 트리]

백준/ Gold 1 문제 , 백준 파이썬 2042 , 구간 합 구하기 [세그먼트 트리]

 

 

풀이 시간

 

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
이제 풀이를 진행할 세그먼트 트리 첫문제이다.
처음 세그먼트 트리를 공부하고 나서 풀어본 문제인데, 트리에 대해서  더 깊은 이해가 필요한 것 같다.
참고 안하고 혼자 스스로 풀 수 있을정도로 당분간 쭉 풀어보겠다.

 

 

문제 출처

https://www.acmicpc.net/problem/2042

2042번: 구간 합 구하기

 

 

 

풀이

 

1. 세그먼트 트리 생성

 

배열의 첫번째 인덱스와, 끝인덱스, 그리고 1 이 담겨져 호출 된다.

 

첫 시작 index 가 1 인 이유는 2를 곱하면 왼쪽 자식 노드 2를 곱하고+1 을 하면 오른쪽 자식 노드이기 때문에 편하게 인덱스를 가지고 계산 할 수 있다.

 

초반에 0,9,1 이 주어졌다면

 

이후 호출 되는 init 함수에는 0,4,2 / 5,9,3   이 담길 것이다.

 

 

각각 1의 왼쪽 자식노드 2 , 오른쪽 자식노드 3 이 부여되었다.

 

이후 왼쪽 자식노드의 2는 0,2,4  / 3,4,5  를 각각 왼쪽자식, 오른쪽 자식에게 부여,

 

오른쪽 노드의 3은 5,7,6 / 8,9,7 을 각각 왼쪽자식,오른쪽 자식에게 부여한다.

 

이런식으로 세그먼트 트리를 생성하는 것이다.

 

 

물론 트리 에 저장되는 것은 이것들이 재귀적으로 호출 되는 수들의 합이다.

 

 

 

2. 구간 합을 구하는 함수

 

재귀적으로 부여되는 start, end, mid 는 init 함수와 동일하다.

 

재귀적으로 탐색하면서 부여된 left, right 구간 내에 있는 tree 들의 합을 구해주는 함수이다.

 

각 구간들의 합이 서로 합해지면서 최종적으로 left~right 구간의 합이 return 된다.

 

 

3. 특정 노드의 값을 변경해주는 함수

 

이또한 start,end,mid 가 재귀적으로 호출되는 방법은 동일하며, 바꿀 위치를 what에담고 , 바꿀값을 value 에 담는다.

 

 

 

4. 입력받기 및 각 함수들 호출

 

배열을 입력 받고 tree는 배열의 길이 * 4의 크기만큼 선언한다.

 

이후 init 함수를 호출하여 세그먼트 트리를 생성한다.

 

 

a가 1일경우 배열의 c를 b-1 위치의 값과 우선 빼준다. +- 의 차이인 값이 나올텐데 그 값을 ch에 담고

 

b-1위치의 값의 c 로 바꿔준다.

 

이후 update 함수에 아까 구한 차이인 ch를 담아 호출하여 변경되는 노드와 관련된 세그먼트 트리의 노드들의 값을 수정한다.

 

 

a가 2일 경우 구간 합을 구해야한다. 이때는 b-1 ~ c-1 위치의 구간합을 구해야하므로 이 구간 을 interval_sum 함수에 담아 호출 한다.

 

 

 

참고

 

다음과 같은 블로그와 유튜브를 참고하였습니다.

 

 

https://velog.io/@kimdukbae/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%84%B8%EA%B7%B8%EB%A8%BC%ED%8A%B8-%ED%8A%B8%EB%A6%AC-Segment-Tree

[자료구조] 세그먼트 트리 (Segment Tree)

 

https://seraup.dev/12

백준 2042번 구간 합 (Python)

 

 

https://www.youtube.com/watch?v=XaodfglnhVs 

 

 

정답

 

 

 

import sys
input=sys.stdin.readline

def init(start,end,index):  # 세그먼트 트리 생성 함수
    if start==end:
        tree[index]=arr[start]
        return tree[index]
    mid=(start+end)//2
    tree[index]=init(start,mid,index*2)+init(mid+1,end,index*2+1)
    return tree[index]

def interval_sum(start,end,index,left,right):  # 구간 합 구하는 함수
    if left>end or right<start:
        return 0
    if left<=start and right >= end:
        return tree[index]
    mid=(start+end)//2
    return interval_sum(start,mid,index*2,left,right)+interval_sum(mid+1,end,index*2+1,left,right)

def update(start,end,index,what,value):
    if what < start or what > end:
        return
    tree[index]+=value
    if start==end:
        return 
    mid=(start+end)//2
    update(start,mid,index*2,what,value)
    update(mid+1,end,index*2+1,what,value)
    
N,M,K=map(int,input().split())
arr=[]
for i in range(N):
    arr.append(int(input()))
tree=[0]*(len(arr)*4)

init(0,len(arr)-1,1)  # 트리 생성

for j in range(M+K):
    a,b,c=map(int,input().split())
    if a==1:
        ch=c-arr[b-1]
        arr[b-1]=c
        update(0,len(arr)-1,1,b-1,ch)  
    elif a==2:
        print(interval_sum(0,len(arr)-1,1,b-1,c-1))