글 읽기 - [Python3]세그먼트 트리 시간초과 질문..

yccian 7년 전 1

세그먼트 트리를 배우면서 아래와 같이 코드를 작성했는데요,

그래도 시간초과가 뜹니다..

줄일 수 있는 부분은 다 줄였다고 생각했는데 어디를 손봐야할까요??

불필요한 부분이나 잘못된 부분좀 잡아주세요 ㅠㅠ

class Seg_Tree :
    def __init__(self,values) :
        self.data = [0 for _ in values] + values
        self.n = len(values)
        for idx in reversed(range(1,self.n)) :
            self.data[idx] = self.data[2*idx] + self.data[2*idx+1]

    def update(self, idx, value) :
        idx += self.n
        self.data[idx] = value

        while idx>1 :
            idx//=2
            self.data[idx] = self.data[2*idx] + self.data[2*idx+1]

    def Sum(self, left, right) :
        left += self.n
        right += self.n
        sum = 0
        
        while left < right :
            if left%2 :
                sum += self.data[left]
                left +=1
            if right%2 :
                right -= 1
                sum += self.data[right]
            left//=2
            right//=2
        return sum
    

inputb = input('')
inputa = inputb.split()
N = int(inputa[0])
M = int(inputa[1])
K = int(inputa[2])

values = []
for _ in range(N):
    values.append(int(input('')))

answer = []


Tree = Seg_Tree(values)

for i in range (M+K) :
    list1 = input('')
    list2 = list1.split()
    if(int(list2[0])==1) :
        Tree.update(int(list2[1])-1,int(list2[2]))
    elif(int(list2[0])==2) :
        answer.append(Tree.Sum(int(list2[1])-1,int(list2[2])))

for i in range(len(answer)) :
    print(answer[i])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python3]세그먼트 트리 시간초과 질문..

yccian 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말