백준 1280 : 나무심기 (C++) [세그멘트 트리, 펜윅트리]

  처음에 segment tree관련 문제를 찾아보다가 알게되어 풀게되었다. 당연히 segment tree문제이므로 segment tree를 이용해서 구현해야 하지만, 문제 내용만 보니 단순히 배열 입력 받은 후 이중 for문으로 구현이 가능할 것 같아서 구현해보았다. 아니나 다를까 시간초과가 되었다. 그래서 관련 해설을 찾아보던 중 '얍문'님의 블로그에서 펜윅트리를 이용한 풀이와, 펜윅트리에 대한 학습을 할 수 있었다. 

  풀이 코드는 '얍문'님의 코드를 거의 그대로 가져온 것이며, 개인 기록을 위해 작성해놓은 것이다. 자세한 설명을 원한다면 '얍문'님의 블로그를 확인하기를 강추한다. 정말 똑똑한 친구가 옆에서 수학문제 하나하나 설명해주는 것처럼 글을 잘 써주셨다. (감사합니다!)

 

**문제풀이 방법

- 홀수 인덱스에는 leaf값이, 짝수 인덱스에는 특정 구간합이 저장되는 펜윅트리를 사용 - 짝수 인덱스의 '특정 구간합'은 인덱스를 2진수로 변환 후 비트를 순회하며 구간 검색('얍문'님 블로그 상세 설명!) - 인덱스 i를 기준으로 앞쪽과 뒤쪽에 있는 '나무들의 갯수'와 '차이값'을 각각 계산 - 연산 결과값 모듈러 연산

 

***코드

#include <stdio.h>
#include <vector>
#define denum 1000000007
#define MAX_N 200001

typedef long long int ll;

using namespace std;

int N;
int Arr[MAX_N];
vector<int> Cnt_FenwickTree;
vector<ll> Dist_FenwickTree;

void init() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		int x;
		scanf("%d", &x);
		Arr[i] = x+1;
	}
}

void Update_Cnt(int pos) {
	while (pos <= MAX_N) {
		Cnt_FenwickTree[pos] = Cnt_FenwickTree[pos] + 1;	// 위치 업데이트
		pos = pos + (pos & -pos);
	}
}

void Update_Dist(int pos, int value) {
	while (pos <= MAX_N) {
		Dist_FenwickTree[pos] = Dist_FenwickTree[pos] + value;	// 값 업데이트
		pos = pos + (pos & -pos);
	}
}

int Query_Cnt(int pos) {
	int result = 0;
	while (pos > 0) {
		result = result + Cnt_FenwickTree[pos];
		pos = pos - (pos & -pos);
	}
	return result;
}

ll Query_Dist(int pos) {
	ll result = 0;
	while (pos > 0) {
		result = result + Dist_FenwickTree[pos];
		pos = pos - (pos & -pos);
	}
	return result;
}

ll Solution() {
	Cnt_FenwickTree.resize(MAX_N + 1, 0);
	Dist_FenwickTree.resize(MAX_N + 1, 0);

	Update_Cnt(Arr[1]);
	Update_Dist(Arr[1], Arr[1]);

	ll ans = 1;
	for (int i = 2; i <= N; i++) {
		ll Left_Cnt = Query_Cnt(Arr[i] - 1);
		ll Right_Cnt = Query_Cnt(MAX_N) - Query_Cnt(Arr[i]);
		ll Left_Dist = Query_Dist(Arr[i] - 1);
		ll Right_Dist = Query_Dist(MAX_N) - Query_Dist(Arr[i]);

		ll Left_Result = Arr[i] * Left_Cnt - Left_Dist;
		Left_Result = Left_Result % denum;
		ll Right_Result = Right_Dist - Arr[i] * Right_Cnt;
		Right_Result = Right_Result % denum;

		ll Result = (Left_Result + Right_Result) % denum;
		ans = ans * Result;
		ans = ans % denum;

		Update_Cnt(Arr[i]);
		Update_Dist(Arr[i], Arr[i]);
	}

	return ans % denum;
}

int main() {
    
    init();
    ll result = Solution();
	printf("%lld",result);

	return 0;
}

 

****주의할 점

- 자료형 long long int 사용 - (A + B) % K = ( (A % K) + (B % K) ) % K 임을 이용   : A=9, B=7, K=4이면,  (9+7) % 4 = 0 = ( (9 % 4 = 1) + (7 % 4 = 3) ) % 4 = 0   * (A * B) % K = ( (A % K) * (B % K) ) % K (곱의 연산도 성립)

 

<Reference>

- https://www.acmicpc.net/problem/1280

- https://yabmoons.tistory.com/479

- https://yabmoons.tistory.com/438