[2042번] 구간 합 구하기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리 :: http://www.crocus.co.kr/648

사실 이 문제를 이전에 C++로 푼 내용이 있다. :: http://www.crocus.co.kr/649

따라서 위의 링크를 타고 가서 문제 내용을 이해하면 되고, 파이썬에서 무얼 이용했는지만 설명하고자 한다.

우선 파이썬3에서 이용되는 input() 메서드를 이용하면 TLE가 나온다.

input 메서드 자체가 시간 복잡도면으로 무거운 면이 있는지 절대 알고리즘이 같아도 정답이 나오지 않는다.

따라서 import sys를 하고 sys.stdin.readline()을 이용하여 인풋을 받고 그것을 split하여 각 변수에 넣어주는 과정을 이용한다.

그리고 C++에서는 vector<int> &arr, vector<int> &tree로 참조식으로 썼지만, 파이썬에서는 매개변수 자체가 참조를 이용하고 있으므로 따로 참조구문을 쓰지 않아도 된다.

나머지는 C++ 코드와 동일하다.

소스 코드 : 

from math import *
import sys
 
def init(arr, tree, node, start, end):
 
    if start == end:
        tree[node] = arr[start]
        return tree[node]
 
    mid = (start + end) // 2
 
    tree[node] = init(arr, tree, node*2, start, mid) + init(arr, tree, node*2+1, mid+1, end)
    return tree[node]
 
def update(tree, node, start, end, index, diff):
    if not (start <= index and index <= end):
        return
 
    tree[node] += diff
 
    if start == end: # update finish
        return
 
    elif start != end:
        mid = (start + end) // 2
        update(tree, node * 2, start, mid, index, diff)
        update(tree, node * 2 + 1, mid + 1, end, index, diff)
 
def query(tree, node, start, end, left, right):
    if start > right or end < left:
        return 0
 
    if left <= start and end <= right:
        return tree[node]
 
    mid = (start + end) // 2
    return query(tree, node * 2, start, mid, left, right) + query(tree, node * 2+ 1, mid + 1, end, left, right)
 
 
n,m,k = [int(x) for x in sys.stdin.readline().split()]
 
h = int(ceil(log2(n)))
tree_size = 1 << (h+1)
 
arr = [0]*(n+1)
tree = [0]*(tree_size)
 
for i in range(n):
    arr[i] = int(sys.stdin.readline())
 
init(arr, tree, 1, 0 , n-1)
m += k
 
while m:
    val,a,b = [int(x) for x in sys.stdin.readline().split()]
 
    if val == 1:
        diff = b - arr[a - 1]
        arr[a-1] = b
        update(tree, 1, 0, n - 1, a-1, diff)
 
    elif val == 2:
        print(query(tree, 1,0,n-1,a-1,b-1))
 
    m -= 1
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>