글 읽기 - prefix 랑 구간 트리 시간복잡도

python0326 3년 전 0

첫번째 풀이는 prefix로 두번째는 구간 트리로 풀었습니다.

첫번째 시간복잡도 O(N + M), 두번째 시간복잡도는 O(N + logN) 이 맞는지 궁금해요..!!

만약 맞다면 두번째 풀이가 더 빨라야 하는거 아닌가요? 왜 더 느릴까여??

# 1
import sys
from collections import deque
input = lambda : sys.stdin.readline().rstrip()


f = open('./main.txt', 'r')
input = lambda : f.readline().rstrip()

    
N, M = map(int, input().split())
arr = list(map(int, input().split()))
values = [0]
hap = 0
for i in range(N):
    hap += arr[i]
    values.append(hap)


for i in range(M):
    left, right =  map(int, input().split())
    print(values[right]-values[left-1])

#2

import sys
from collections import deque
input = lambda : sys.stdin.readline().rstrip()

MAX = 100005
class Hap:
    def __init__(self, arr, size):
        self.arr = arr
        self.size = size
        self.values = [0] * (size*4)
        self.init(arr, 0, size-1, 1)
    
    def init(self, arr, left, right, node):
        if left == right :
            self.values[node] = arr[left]
            return self.values[node]

        mid = (left+right)//2
        leftValue = self.init(arr, left, mid, node*2)
        rightValue = self.init(arr, mid+1, right, node*2+1)
        self.values[node] = leftValue + rightValue
        return self.values[node]

    def _find(self,left, right):
        ans = self.find(left, right, 0, self.size-1, 1)
        print(ans)
        return ans
    
    def find(self, left, right, nodeLeft, nodeRight, node):
        if left <= nodeLeft and nodeRight <= right:
            return self.values[node]
        if nodeRight < left or right < nodeLeft:
            return 0 

        mid = (nodeLeft + nodeRight) // 2
        leftValue = self.find(left, right, nodeLeft, mid,node*2)
        rightValue = self.find(left,right,mid+1, nodeRight, node*2+1)
        return leftValue + rightValue
        

N, M = map(int, input().split())
arr = list(map(int, input().split()))
hap = Hap(arr, N)

for i in range(M):
    left, right =  map(int, input().split())
    hap._find(left-1, right-1)

문제

문제

출처

ICPC

prefix 랑 구간 트리 시간복잡도

python0326 3년 전 0

taesick 3년 전 0

python0326 3년 전 0

taesick 앗 그렇네요 ㅋ쿠ㅜ 감사합니다!

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말