풀이
import sys; from math import ceil, log
def init(node, start, end):
# 리프 노드임
if start == end:
tree[node] = nums[start]
return tree[node]
else:
# bottom -> top 방식으로 내려가면서 값을 구하고 그 값을 올려줘서 더해줌
tree[node] = init(node*2, start, (start+end)//2) + init(node*2+1, (start+end)//2+1, end)
return tree[node]
def sub_sum(node, start, end, left, right):
# 탐색 구간이 벗어난 경우는 0을 return
if left > end or right < start:
return 0
# 쪼개고 쪼개서 완전히 포함되는 경우 -> 더 쪼개서 봐야됨 -> 그러다 0이 나오거나 여기서 return 한번 더 되면 그 값을 리턴하면 됨
# 재귀적인 부분이라 설명이 어렵네요
if left <= start and end <= right:
# print(tree[node])
return tree[node]
return sub_sum(node*2, start, (start+end)//2, left, right) + sub_sum(node*2 + 1, (start+end)//2+1, end, left, right)
if __name__ == '__main__':
N, M = map(int, sys.stdin.readline().strip().split())
nums = list(map(int, sys.stdin.readline().strip().split()))
tree = [0] * 2**(ceil(log(N, 2) + 1))
init(1, 0, N-1)
# print(tree)
for _ in range(M):
left, right = map(int, sys.stdin.readline().strip().split())
print(sub_sum(1, 0, N-1, left-1, right-1))
# sub_sum(1, 0, N - 1, left - 1, right - 1)
# print('---------------------')
후기
- 어쩌다 구간 합 문제를 봤는데 세그먼트 트리 강의를 잠깐 들은게 있어서 사용해보면 좋겠다 해서 사용해봄
- 이게 그림으로 그리면 쉬운데 코드로 구현하려니 많이 복잡함
- 그림으로 따지면 간단한데 코드로 구현하자니 재귀에다가 bottom에서 top으로 올라오니까
- dp를 안배운 나로서는 복잡했다.
- 여기서 update함수만 추가하면 세그먼트 트리의 구간 합 사용 이유를 제대로 알 것 같음 풀 예정임
'백준' 카테고리의 다른 글
백준 2232 지뢰 (파이썬) (0) | 2022.12.05 |
---|---|
백준 2042 구간 합 구하기 (파이썬) (세그먼트) (0) | 2022.12.05 |
백준 11003 최솟값 찾기 (파이썬) (0) | 2022.12.03 |
백준 16930 달리기 (파이썬) (1) | 2022.12.03 |
백준 5430 AC (파이썬) (0) | 2022.12.01 |