백준 10999 - 구간 합 구하기 2 [Python]

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

10999번: 구간 합 구하기 2

 

Lazy Propagation 기초 문제이다.

 

모른다면 읽고 오자.

https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=kks227&logNo=220824350353 

 

기존 세그먼트 트리의 방식으로라면 갱신 하나에 O(NlgN)이라는 시간이 걸려 총 O(MNlgN)이라는 시간초과받기 좋은 시간복잡도를 가진다.

 

그러나 Lazy 배열을 하나 더 선언하고, 느리게 갱신하는 과정을 통해 O(lgN)으로 갱신할 수 있다.

 

템플릿 코드

import sys, math
import heapq
 
from collections import deque
input = sys.stdin.readline
 
hqp = heapq.heappop
hqs = heapq.heappush
 
#input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split().rstrip()))
 
#gcd, lcm
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x
 
def lcm(x, y):
    return x * y // gcd(x, y)
 
#prime
def isPrime(x):
    if x<=1: return False
    for i in range(2, int(x**0.5)+1):
        if x%i==0:
            return False
    return True
 
# Union Find
# p = {i:i for i in range(1, n+1)}
def find(x):
    if x == p[x]:
        return x
    q = find(p[x])
    p[x] = q
    return q
 
def union(x, y):
    x = find(x)
    y = find(y)
 
    if x != y:
        p[y] = x
 
def getPow(a, x):
    ret = 1
    while x:
        if x&1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        x>>=1
    return ret
 
def getInv(x):
    return getPow(x, MOD-2)

 

정답코드

seg = [0 for _ in range(4040404)]
lazy = [0 for _ in range(4040404)]
 
def init(x, s, e):
    if s == e:
        seg[x] = a[s - 1]
        return seg[x]
    m = s + e >> 1
    seg[x] = init(x * 2, s, m) + init(x * 2 + 1, m + 1, e)
    return seg[x]
 
def update(x, l, r, s, e, dif):
    updateLazy(x, s, e)
    if e < l or r < s:
        return
    if l <= s and e <= r:
        seg[x] += (e - s + 1) * dif
        if s != e:
            lazy[x * 2] += dif
            lazy[x * 2 + 1] += dif
        return
    m = s + e >> 1
    update(x * 2, l, r, s, m, dif)
    update(x * 2 + 1, l, r, m + 1, e, dif)
    seg[x] = seg[x * 2] + seg[x * 2 + 1]
 
def updateLazy(x, s, e):
    if lazy[x]:
        seg[x] += (e - s + 1) * lazy[x]
        if s != e:
            lazy[x * 2] += lazy[x]
            lazy[x * 2 + 1] += lazy[x]
        lazy[x] = 0
 
def getSum(x, l, r, s, e):
    updateLazy(x, s, e)
    if e < l or r < s:
        return 0
    if l <= s and e <= r:
        return seg[x]
    m = s + e >> 1
    return getSum(x * 2, l, r, s, m) + getSum(x * 2 + 1, l, r, m + 1, e)
 
n, q1, q2 = mip()
a = []
for i in range(n):
    a.append(ip())
 
init(1, 1, n)
 
for i in range(q1 + q2):
    q = lmip()
    if q[0] == 1:
        update(1, q[1], q[2], 1, n, q[3])
    else:
        print(getSum(1, q[1], q[2], 1, n))