import sys
input = sys.stdin.readline
def update(i,v):
d = v-value[i]; value[i] = v
while i<M:
fen[i] += d
i += i&-i
def cal(i):
S = 0
while i:
S += fen[i]
i -= i&-i
return S
N = int(input()); M = 1<<20
seq = [*map(int,input().split())]
value = [0]*M
fen = [0]*M
for i in range(N):
update(i+1,seq[i])
query = [[],[]]
for _ in range(int(input())):
q,*a = map(int,input().split())
query[q-1].append([*a,len(query[q-1])])
query[1].sort()
result = [0]*len(query[1]); l=0
for k,i,j,n in query[1]:
for l in range(l,k):
update(*query[0][l][:-1])
result[n] = cal(j)-cal(i-1)
print(*result,sep="\n")팬윅트리로 해결하였다.
수들의 합 7 [백준 2268번] 수들의 합 7 (Python3) (tistory.com) 과 거의 유사하지만 현재 상태에서의 합을 출력하는 것이 아니라 k번째까지 진행한 상태에서의 합을 출력한다는 차이점이 존재한다. 따라서 이에 대한 처리를 추가로 해주어야한다.
풀이를 설명하면,
1. 입력받은 수열에 대해 팬윅트리를 만든다.
2. 쿼리를 입력받아 저장한다. 쿼리1과 쿼리2를 따로 저장하고, 쿼리2는 입력받은 순서를 저장하고, k를 기준으로 정렬한다.
3. 쿼리2를 for문을 돌리면서 각 쿼리의 k에 따라 쿼리1을 실행, 결과값은 입력받은 순서에 따라 result 리스트에 저장한다.
4. result 리스트를 출력한다.
쿼리를 순서대로 정렬하는 전처리 과정이 필요한 문제였다. 문제를 해결하고 나서 알게된 사실이 이렇게 쿼리를 입력받을 때마다 출력하지 않는것을 "오프라인 쿼리" 방식이라 부른다고 한다.
오늘의 교훈) 오프라인 쿼리에 대해서 알아보자