[백준] 2042: 구간 합 구하기 (Python)

문제

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

접근 방법

1. 구간 합을 세그먼트 트리를 이용하여 구현해 보았다.
2. 재귀를 통해 리프 노드의 값을 변경하고, 부모 노드들의 값을 새롭게 자식 노드 들의 합으로 갱신 해주는 방법으로, 구현 하였더니 시간초과가 발생하였다.
3. 입력으로 들어온 수의 배열과 변경하려는 수의 차이를 이용하는 방법으로 바꾸어 시간초과를 해결하였다.

풀이 코드

def seg(idx, start, end):
    if start == end:
        tree[idx] = nums[start]
        return tree[idx]

    tree[idx] = seg(idx*2 , start , (start+end)//2) + seg(idx*2+1, (start+end)//2 + 1 , end)
    return tree[idx]

def change(target, diff , idx, start, end):
    if end < target or target < start:
        return 

    tree[idx] += diff
    if start != end:
        change(target, diff , idx*2 , start , (start+end)//2)
        change(target, diff , idx*2+1, (start+end)//2 + 1 , end)

def p_sum(left, right , idx, start, end):
    if end < left or right < start:
        return 0

    if start >= left and right >= end:
        return tree[idx]

    return p_sum(left, right , idx*2, start, (start+end)//2) + p_sum(left, right , idx*2 + 1 , (start+end)//2 + 1, end)


N, M, K = map(int,input().split()) # 수, 변경 횟수, 구간 합 횟수
nums = [0] + [int(input()) for _ in range(N)]
for i in range(N):
    if 2**i >= N:
        break
tree = [0] * (2**(i+1))
seg(1,1,N)
for _ in range(M+K):
    a, b, c = map(int,input().split())
    if a == 1:
        diff = c - nums[b]
        nums[b] = c
        change(b,diff,1,1,N)
    else:
        print(p_sum(b,c,1,1,N))