[백준] 2042 구간 합 구하기, python

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

 

 

 

 

 

 

[백준] 2357 최솟값과 최댓값

[백준] 2357 최솟값과 최댓값

 

 

 

구간합을 계산할 때는 합 세그먼트 트리를 생성한 다음, 이전에 풀었던 최솟값 최댓값 구하는 로직과 똑같이 

왼쪽 자식 노드가 홀수일 경우 해당 노드값을 합에 반영시키고 노드번호를 1 증가시키고,

오른쪽 자식 노드가 짝수일 경우 해당 노드값을 합에 반영시키고 노드번호를 1 감소시킨다.

그리고 위의 경우가 아닐 경우 에는 각각 노드의 부모노드로 올라가서 탐색한다.

 

 

만약 배열에 값이 변경되었다면, 해당 배열 인덱스에 해당하는 리프노드(세그먼트 트리의 size+인덱스 번 노드)부터 출발해서  부모노드로 거슬러 올라가며 기존값을 빼고 변경된 값을 추가해 줘서 세그먼트 트리를 업데이트해주었다.

 

 

 

 

 

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
arr = [int(input()) for _ in range(n)]
query = [list(map(int, input().split())) for _ in range(m+k)]

size = 1
while size < n:
    size *= 2

# 합 세그먼트 트리 생성
segtree = [0]*(size*2)

for i in range(n):
    segtree[size+i] = arr[i]

for i in range(size-1,0,-1):
    segtree[i] = segtree[i*2] + segtree[i*2+1]

# 값을 변경함. 리프에서부터 부모노드를 추적하면서 업데이트
def change_num(b,c):
    val = arr[b]
    arr[b] = c
    b += size
    while b>0:
        segtree[b] = segtree[b]-val+c
        b //= 2
    

# 세그먼트 트리에서 구간 합을 구함
def get_sum(b,c):
    result = 0
    b += size
    c += size
    while b<=c:
        if b % 2 == 1:
            result += segtree[b]
            b += 1
        if c % 2 == 0:
            result += segtree[c]
            c -= 1
        b //= 2
        c //= 2
    print(result)

for a,b,c in query:
    if a == 1:
        change_num(b-1,c)
    elif a == 2:
        get_sum(b-1,c-1)