[백준][구간합] 구간 합 구하기

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

2042번: 구간 합 구하기

 

내가 작성한 코드

import sys
read = sys.stdin.readline

N, M, K = map(int, read().rstrip().split(' '))
# num = [1] * N
num = []
thousand = [0] * 1000
for i in range(N):
    crnt_num = int(read().rstrip())
    thousand[i // 1000] += crnt_num
    # thousand[i // 1000] += num[i]
    num.append(crnt_num)


for _ in range(M+K):
    a, b, c = map(int, read().rstrip().split(' '))
    if a == 1:
        thousand[(b-1)//1000] += c - num[b-1]
        num[b-1] = c
    else:
        div_l = (b-1) // 1000
        div_r = (c-1) // 1000
        if div_l < div_r:
            left = sum(num[b-1:(div_l+1)*1000])
            right = sum(num[div_r*1000:c])
            mid = sum(thousand[(div_l+1):div_r])
            print(left+mid+right)
        else:
            print(sum(num[b-1:c]))

• 1000개 단위로 sum을 구해놓음
• 최악의 경우라도 2000개의 sum을 구하는 연산을 해야함 

 

다른 사람이 작성한 코드

# Python으로 작성한 코드가 보이지 않음
None

 

기억해야할 것

• 처음에 이진세그먼트트리로 만들었는데, 시간 초과
  • 데이터가 최대 1,000,000개 (약 2^20)
  • 높이만큼 탐색하면 최대 깊이 20인데, 트리를 만드는 시간이 이미 10초가 넘음
• 트리를 만드는 시간을 줄이고, 합을 구하는 시간을 줄이는 절충한으로 1000개씩 나눔
  • 길이가 1,000개 이하면 sum으로 구해도 충분
  • 1,000,000개 데이터의 합에 대해서 1,000개씩 합이 이미 계산되어 있으므로, 이를 1,000번 계산하면 구해짐