이 글은 BOJ 블로그에 있는 글과 동일합니다.

흔히 lazy propagation을 사용하여 푸는 것으로 알려진 이 두 문제는 사실 펜윅 트리만으로 풀 수 있습니다.

구간 덧셈, 포인트 쿼리

다음 연산을 효율적으로 수행하는 자료구조를 만들어 봅시다. 이것으로 16975번 - 수열과 쿼리 21을 풀 수 있습니다.

1. $A_L$, $A_{L+1}$, $\cdots$, $A_R$에 각각 $x$씩 더한다.
2. $A_k$를 출력한다.

$B_1 = A_1$, $B_k = A_k - A_{k-1}$이라고 두면, 각각의 쿼리는 이렇게 변합니다.

1. $B_L$에 $x$를 더하고, R이 마지막 인덱스가 아니면 $B_{R+1}$에서 $x$를 뺀다.
2. $B_1 + \cdots + B_k$를 출력한다.

따라서 펜윅 트리로 구현할 수 있습니다.

같은 원리로, 1번 쿼리만 계속 들어온 다음 2번 쿼리만 계속 들어옴이 보장되면, 단순 배열 연산으로 O(N+Q)에 풀 수 있습니다. 스위핑을 생각하시면 됩니다.

연습 문제집

구간 덧셈, 구간 합 쿼리

세그먼트 트리 lazy propagation을 쓰는 대표적인 예시로 알려진 이 문제 역시 놀랍게도 펜윅 트리 두 개로 풀 수 있습니다.

1. $L, L+1, \cdots, R$번째 원소에 각각 $x$씩 더한다.
2. $L, L+1, \cdots, R$번째 원소의 합을 출력한다.

우선, L과 R이 있는 것이 거슬리니까 이렇게 바꿉시다. 원래 있었던 쿼리는 밑의 쿼리 두 번으로 처리할 수 있습니다.

1. $k, k+1, \cdots, N$번째 원소에 각각 $x$씩 더한다.
2. $1, 2, \cdots, k$번째 원소의 합을 출력한다.

$k, k+1, \cdots, N$번째 원소에 각각 $x$씩 더할 때, 각 $m = 1, 2, \cdots, N$에 대해 “$m$번째까지 원소의 합“이 얼마나 늘어나는지 생각해봅시다.

• $m < k$라면, $m$번째까지 원소의 합은 변화하지 않습니다.
• $m \geq k$라면, $m$번째까지 원소의 합은 $(m-k+1)x$ 늘어납니다.

이것은 곧 $k$번째 칸에 일차함수 $f(m) = xm + (-k+1)x$를 집어넣는 펜윅 트리라고 볼 수 있습니다. 두 일차함수의 합은 여전히 일차함수이므로 각 칸마다 일차항의 계수를 저장하는 펜윅 트리를 만들고, 각 칸마다 상수항을 저장하는 펜윅 트리를 만들면 됩니다. 그렇게 만든 트리에서 첫 번째부터 $k$번째까지 원소(일차함수)의 합을 계산하여 또다른 일차함수를 얻고, 그 일차함수의 변수에 $k$를 집어넣어 계산한 값이 2번 쿼리의 답입니다.