10999 구간 합 구하기 2 python

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

10999번: 구간 합 구하기 2

 

 

 

 

 

문제 접근

세그먼트 트리로 그냥 풀면 틀릴것같아서 좀 찾아봤다.

느리게 갱신되는 세그먼트 트리라는게 있어서 공부했더니 쉽게 풀렸다.

방법은 아래 링크에서 잘알려준다

https://book.acmicpc.net/ds/segment-tree-lazy-propagation

느리게 갱신되는 세그먼트 트리

 

지금 값을 갱신해버리면 너무 시간소모가 크기때문에, 새로운 변수를 만들어두고 갱신할 값을 적어둔다.

누적합 부분만 갱신하면서 트리의 아래로 더 내려가지않고 버티는 느낌이다.

그리고 아래 노드에 접근해야하면 한번에 갱신한다.

매번 접근할때마다 새로만든 lazy라는 변수에 값이 0인지 체크해야한다.

 

 

 

 

코드

import sys
import math

input = sys.stdin.readline
"""
 10999
 세그먼트 트리로 만들면 되긴 한데
 넓은 범위를 부분이 넓어도 시간초과가 안날까?
 1000000개를 10000번 수정하고 시간제한2초. 시간초과
 !느리게 갱신되는 세그먼트 트리! 사용 시 해결가능
 """

N, M, K = map(int,input().split())
node = 2**(math.ceil(math.log2(N)))
tree = [0 for i in range(node*2)]
lazy = [0 for i in range(node*2)]

for i in range(N):
  tree[node+i] = int(input())


def init(index):
  if index<node:
    tree[index] = init(index*2) + init(index*2+1)
  return tree[index]


def updateLazy(start, end, index):
  if lazy[index]:
    tree[index] += (end-start+1) * lazy[index]
    if start!=end:
      lazy[index*2] += lazy[index]
      lazy[index*2+1] += lazy[index]
    lazy[index] = 0
        

def updateRange(targetStart, targetEnd, start, end, index, val):
  updateLazy(start, end, index)
  if start > targetEnd or end < targetStart:
    return 
    
  if targetStart <= start and end <= targetEnd:
    tree[index] += (end-start+1) * val
    if start != end:
      lazy[index*2] += val
      lazy[index*2+1] += val
    return 
    
  mid = (start + end) // 2
  updateRange(targetStart, targetEnd, start, mid, index*2, val) 
  updateRange(targetStart, targetEnd, mid + 1, end, index*2+1, val)
  tree[index] = tree[index*2] + tree[index*2+1]
  

def printSum(targetStart, targetEnd, start, end, index):
  updateLazy(start, end, index)
  if start > targetEnd or end < targetStart:
    return 0

  if targetStart <= start and end <= targetEnd:
    return tree[index]

  mid = (start + end) // 2
  return printSum(targetStart, targetEnd, start, mid, index*2) + printSum(targetStart, targetEnd, mid + 1, end, index*2+1)

init(1)


for i in range(M+K):
  abc = list(map(int,input().split()))
  if abc[0] == 1:
    updateRange(abc[1], abc[2], 1, node, 1, abc[3])
  else:
    print(printSum(abc[1], abc[2], 1, node, 1))