글 읽기 - Lazy 세그먼트 트리 시간 초과 질문입니다

noye 4년 전 0

mask에 변화값을 넣어놓고 연산 후 mask를 더해 출력시켰는데 0% 시간초과네요

구간 합 구하기, 구간 곱 구하기 등을 풀었는데 더 최적화시킬 방법이 생각이 나지 않습니다.

pypy3로도 시간초과입니다.

어떤 방법을 사용해야 할까요?

import sys

def build(base, now):
    global tree
    tree = [tree[i] + tree[i+1] for i in range(0, now, 2)] + tree
    if now > 2:
        build(base+now, now//2)    

def trace(index, start, end, left, right):
    global tree
    #print('tracing', index, start, end, left, right)
    if start > right or left > end:
        return 0
    if start <= left and right <= end:
        return tree[index] + sum(mask[left:right+1])
    mid = (left + right)//2
    return trace(index*2+1, start, end, left, mid) + trace(index*2+2, start, end, mid+1, right)

def update(finds, finde, n):
    global mask
    for i in range(finds, finde+1):
        mask[i] += n

n, m, k = map(int, input().split())
tree = []

for i in range(n):
    tree.append(int(sys.stdin.readline()))

floor = 1
while floor < len(tree):
    floor *= 2
tree.extend([0] * (floor - len(tree)))

mask = [0] * floor
build(0, floor)


for _ in range(m+k):
    inp = list(map(int, sys.stdin.readline().split()))
    if inp[0] == 1:
        update(inp[1]-1, inp[2]-1, inp[3])
    else:
        sys.stdout.write(str(trace(0, inp[1]-1, inp[2]-1, 0, floor-1))+'\n')
    #print(tree)

lim551 4년 전 0

trace에서 sum을 쓴 이유가 뭔가요?

noye 4년 전 0

헉 생각해보니까 sum은 그냥 바깥으로 빼도 되네요! 다시 해보겠습니다 감사랍니다

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

문제

문제

출처

ICPC

Lazy 세그먼트 트리 시간 초과 질문입니다

noye 4년 전 0

lim551 4년 전 0

noye 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말