[백준 2042] 구간 합 구하기- python (solved.ac - 골드 1)

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

2042번: 구간 합 구하기

풀이

문제를 보았을때 알수있는 힌트

세그먼트 트리 쪽을 공부하기위해 찾아 풀어본 문제이다.

문제에 여러개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구한다고하면 세그먼트 트리로 풀수있는 문제이다.

2042번 구간 합 구하기 문제 역시 12345와 같이 연속적으로 존재하는 리스트에 2번째 부터 5번째 까지의 합 등으로 되어있으니 세그먼트 트리로 풀수있다.

세그먼트 트리는 총 3가지 함수를 만들어서 진행하면 된다.

1. 구분 합 트리 생성하기

2. 구분 합을 구하는 함수 만들기

3. 특정 원소의 값을 수정하는 함수 만들기

 

나중에 알고리즘으로 작성을 하고 정확히 알고 문제를 풀수있어야할듯하다.

 

import sys

input = sys.stdin.readline

n,m,k= map(int, input().split())
n_list=[]
tree = [0 for _ in range(n*4)]

def init(start, end, node):
    if start == end:
        tree[node] = n_list[start]
        return tree[node]
    mid =(start+end)//2
    tree[node] = init(start,mid,node*2)+init(mid+1,end,node*2+1)
    return tree[node]

def sum(start, end, node, left, right):
    if left > end or right < start:
        return 0
    if left<=start and end <= right:
        return tree[node]
    mid = (start+end)//2
    return sum(start,mid,node*2,left,right)+sum(mid+1,end,node*2+1,left,right)

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

for i in range(n):
    n_list.append(int(input()))
init(0,n-1,1)
# print(tree)
for i in range(m+k):
    a,b,c = map(int, input().split())
    if a ==1:
        b= b-1
        diff = c- n_list[b]
        n_list[b] =c
        update(0,n-1,1,b,diff)
        # print(tree)
    elif a ==2:
        print(sum(0,n-1,1,b-1,c-1))

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon2042.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리