[백준 16975번] 수열과 쿼리 21 (Python3)

import sys
input = sys.stdin.readline

def updateseg(k,a,b,start,end,x):
  if a==start and b==end:
    seg[x] += k
    return
  mid = (start+end)//2
  if b <= mid:
    updateseg(k,a,b,start,mid,x*2)
  elif a > mid:
    updateseg(k,a,b,mid+1,end,x*2+1)
  else:
    updateseg(k,a,mid,start,mid,x*2)
    updateseg(k,mid+1,b,mid+1,end,x*2+1)

def sumseg(n,start,end,x):
  global SUM
  SUM += seg[x]
  if start==end:
    return
  mid = (start+end)//2
  if n <= mid:
    sumseg(n,start,mid,x*2)
  else:
    sumseg(n,mid+1,end,x*2+1)
    

N = int(input())
seg = [0]*(4*N)
data = [*map(int,input().split())]

M = int(input())
for _ in range(M):
  Q = [*map(int,input().split())]
  if Q[0] == 1:
    q,i,j,k = Q
    updateseg(k,i-1,j-1,0,N-1,1)
  else:
    SUM = 0
    q,i = Q
    sumseg(i-1,0,N-1,1)
    print(data[i-1]+SUM)

간단한 세그먼트 트리 응용문제.

값을 바꾸어 구간의 합을 구하는 기존의 세그먼트 트리 문제와 약간 다르게 구간을 바꾸어 값을 구한다.

따라서 구간에 더해진 값에 대한 세그먼트 트리를 만들어 문제를 해결할 수 있다.

 

a~b까지 k를 더해야 한다면, a~b 구간에 속한 세그먼트 트리에 k를 더해주고, 출력할때는 출력해야하는 인덱스를 포함하는 세그먼트 트리를 순회하면서 값을 더해주면 된다.

 

이 문제는 lazy propagation이라는 알고리즘을 소개하는 문제라고 한다. 물론 이 문제에서는 그걸 사용하지 않고도 풀 수 있었지만, 추후에 이용될 수도 있으니 이에 대해서 알아볼 필요가 있을 것 같다.

 

오늘의 교훈) lazy propagation에 대해서 알아보자.