구간에 원소를 더하는 쿼리가 많이 주어질 때 필요한 누적합 테크닉(imos법)

19951번: 태상이의 훈련소 생활 (acmicpc.net)

19951번: 태상이의 훈련소 생활

 

 

배열이 주어질때, 구간 [a,b]에 c를 더하는 쿼리가 여러개 주어지고,

 

모든 쿼리를 해결하고 나서 최종 배열을 구하는 문제

 

1 2 3 4 5 -1 -2 -3 -4 -5 라는 배열에서 [1,5]에 -3을 더하면...

 

-2 -1 0 1 2 -1 -2 -3 -4 -5

 

여기서 [6,10]에 5를 더하면 -2 -1 0 1 2 4 3 2 1 0

 

여기서 [2,7]에 2를 더하면 -2 1 2 3 4 6 5 2 1 0

 

물론 쿼리 수가 몇개 없고, 쿼리 구간 길이가 작다면 매번 쿼리가 주어질때마다 해당 구간을 순회해서 원소 c를 더해주면 되는데

 

쿼리 수가 최대 10만개이고 구간 길이가 최대 10만이라 매번 이렇게 하면 $O(N^{2})$으로 시간초과날것

 

그래서 매번 구간 쿼리마다 오프셋 배열을 만들고, 특정 위치에 표시를 해둔 다음,

 

구간 쿼리가 끝나고 나서 한번에 누적합을 한다면?

 

1 2 3 4 5 -1 -2 -3 -4 -5 배열에서 [1,5]에 -3을 더하는 쿼리가 주어진다면...

 

나중에 오른쪽으로 한번에 누적합할 생각을 한다면, 어디에 표시를 해두어야할까?

 

1번에 -3을 더해주고, 6번에 +3을 더해둔다면?

 

-3 0 0 0 0 +3 0 0 0 0

 

이 배열을 누적합을 한다면 -3 -3 -3 -3 -3 0 0 0 0 0가 된다

 

즉 [1,5]에 -3을 더하는 것과 동일해진다.

 

다시 2번째 쿼리 [6,10]에 5를 더한다면? 6번에 5를 더해두고, 11번에 -5를 더해둔다.

 

-3 0 0 0 0 +3+5 0 0 0 0

 

물론 11번이 없으니까 11번에는 -5를 더하지 않아도 상관없다.. 11번 이후로는 없으니까

 

그러면 다시 이 배열을 누적합해볼까?

 

-3 -3 -3 -3 -3 5 5 5 5 5

 

그러면 [1,5]에 -3을 더하고, [6,10]에 +5를 더하는 것과 마찬가지다.

 

마찬가지로 3번째 쿼리 [2,7]에 2를 더하면? 2번에 2를 더하고, 8번에 -2를 더한다.

 

-3 +2 0 0 0 +3+5 0 -2 0 0

 

이제 이 배열을 누적합하면, -3 -1 -1 -1 -1 +7 +7 +5 +5 +5

 

이 배열을 1 2 3 4 5 -1 -2 -3 -4 -5에 더해준다면...?

 

-2 1 2 3 4 6 5 2 1 0으로 정답과 동일하다.

 

따라서, [a,b]에 c를 더하는 쿼리가 주어지면 인덱스 a에 +c를 더하고 인덱스 b+1에 -c를 더한다.

 

모든 쿼리가 끝나면 오프셋 배열을 누적합 시킨다.

 

오프셋 배열과 원래 배열을 동시에 순회해서, 최종 배열을 구해주면 O(N)에 문제를 해결할 수 있다

 

#[a,b]에 c를 더하는 구간 쿼리 해결하는 누적합 테크닉 imos법

from sys import stdin

n,m = map(int,stdin.readline().split())

h = list(map(int,stdin.readline().split()))

#[a,b]가 주어질때, a-1번 위치에 +k를 더해주고
#b번에 -k를 더해준다.
#b가 n 이상이면 없는 위치이므로 무시해도 된다
offset = [0]*n

for _ in range(m):
    
    a,b,k = map(int,stdin.readline().split())

    offset[a-1] += k

    if b < n:

        offset[b] += -k

#모든 쿼리를 해결하고 오프셋 배열을 누적합
for i in range(1,n):
    
    offset[i] += offset[i-1]

#누적합된 오프셋 배열의 원소를 원래 배열 원소에 대응하는 위치마다 더해준다
for i in range(n):
    
    h[i] += offset[i]

print(' '.join(map(str,h)))

 

 

 

똑같은 문제

 

 

28018번: 시간이 겹칠까? (acmicpc.net)

28018번: 시간이 겹칠까?