[모각코] 210811 Today I Learned

 

<백준 2042번 - 구간 합 구하기>

 

 

세그먼트 트리 예제 공부하고 나서 푸니까 금방 풀렸다.

다른 문제들도 풀어보고 싶긴 한데 어차피 못 풀 것 같다... 너무 어려운 문제는 고르지 말아야지.. 이게 과연 푸는 의미가 있는가....

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def init(start, end, index):
    if start == end:
        tree[index] = num[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 partial_sum(start, end, index, left, right):
    if start > right or end < left:
        return 0
    elif start >= left and end <= right:
        return tree[index]
    else:
        mid = (start + end) // 2
        return partial_sum(start, mid, index*2, left, right) + partial_sum(mid+1, end, index*2+1, left, right)

def update(node, start, end, index, diff):
    if index < start or index > end:
        return
    tree[node] += diff
    if start != end:
        update(node*2, start, (start+end)//2, index, diff)
        update(node*2+1, (start+end)//2+1, end, index, diff)

n, m, k = map(int, input().rstrip().split())
num = []
tree = [0 for i in range(3000000)]
for _ in range(n):
    num.append(int(input().rstrip()))
init(0, n-1, 1)

for _ in range(m+k):
    a, b, c = map(int, input().rstrip().split())
    if a == 1:
        diff = c - num[b-1]
        num[b-1] = c
        update(1, 0, n-1, b-1, diff)
    elif a == 2:
        print(partial_sum(0, n-1, 1, b-1, c-1))

 

 

세그먼트 트리 다 풀고 LCA 공부 조금 했는데 역시 이해 안 가서 집어치웠다.

세그먼트 트리는 코드 보면 이해는 가는데 LCA는 ㅋㅋㅋ 이해도 안 간다....