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에 대해서 알아보자.