펜윅 트리 200% 활용하기

흔히 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)에 풀 수 있습니다. 스위핑을 생각하시면 됩니다.

연습 문제집: https://www.acmicpc.net/workbook/view/5043

구간 덧셈, 구간 합 쿼리

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

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

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

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

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

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

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

(제가 쓰는 구현과 식이 조금 다르므로 오류가 있을 시 알려 주시면 감사하겠습니다.)


댓글 (2개) 댓글 쓰기


sohnryang 4년 전

:fan:이에요!


pentagon03 4년 전

진짜 아름다운 구현이네요. 무릎 탁 치고 갑니다.