📖문제
💡구상
단순히 생각해서 완전탐색을 한다면 최악의 경우는?
N이 200,000일 경우 1+2+3+4+....+199999 대략 200억 정도이므로 완탐으로 풀 수 없다.
그렇다면 펜윅트리를 이용해서 탐색 시간을 줄일 수 있지 않을까?
펙윅트리를 사용한다면 어떤 방식으로 사용해야 할까?
우선 n번 나무를 심었을 때, 비용을 어떻게 계산할지 고민해 보자.
이렇게 4,5,8 순서대로 입력이 주어졌을 때, 8 위치에 나무를 심는다면?
파란색으로 표시한 4와 3을 더해주면 될 것이다.
4와 3이 어떻게 나온 숫자인지 생각해보면, 현재 심으려는 위치(8)에서 심어진곳 까지의 위치(4,5)를 빼면 나온다.
즉 현재 심으려는 위치를 A, 위치보다 이전에 심어진 갯수를 B 이라 하면
비용 = A x B - (위치보다 이전에 심어진 거리들의 합)
다른 케이스도 살펴보자.
8,5가 심어진 상태에서 4를 심으려고 한다면?
이러한 경우도 이전 케이스와 비슷하게
현재 심으려는 위치를 A, 위치보다 이후에 심어진 갯수를 B 이라 하면
비용 = (위치보다 이후에 심어진 거리들의 합) - A x B
즉, 현재 심는 위치의 왼쪽과 오른쪽으로 분리하여 계산한 후 더해주면 총 비용이 된다.
코드를 보며 살펴보자.
🔍코드
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int max_n = 200004;
const ll mod = 1e9+7;
int n,value;
ll ret = 1;
vector<ll> tree_cnt(max_n,0),tree_sum(max_n,0);
// value 까지의 구간합 구하기
ll _sum(vector<ll> &tree, int value){
ll _ret = 0;
int i= value;
while(i){
_ret +=tree[i];
i-= (i&-i);
}
return _ret;
}
// s 부터 e 까지의 구간합 구하기
ll sum(vector<ll> &tree, int s, int e){
if(s > e) return 0;
return (_sum(tree, e) - _sum(tree, s - 1));
}
// 트리 업데이트
void update(vector<ll> &tree, int x, ll value){
int i = x;
while(i<=max_n){
tree[i] += value;
i += (i&-i);
}
return;
}
int main() {
cin>>n;
for(int i=1; i<=n; i++){
cin>>value; value++;
if(i!=1){
ll left = value*sum(tree_cnt,1,value-1) - sum(tree_sum,1,value-1);
ll right = sum(tree_sum, value+1, max_n) - value*sum(tree_cnt,value+1,max_n);
ret *= (left+right) % mod;
ret %= mod;
}
update(tree_cnt, value, 1);
update(tree_sum, value, value);
}
cout<<ret;
return 0;
}value++
cin>>value; value++;문제의 조건을 살펴보면 좌표는 0부터 시작한다. 하지만 펜윅트리의 인덱스는 1부터 정의되어야 하므로 ++해서 사용한다.
펜윅트리
vector<ll> tree_cnt(max_n,0),tree_sum(max_n,0);우리가 펜윅트리에 저장해야할 값은, 현재 위치에서 왼쪽에 몇개가 심어져있는지 와 저장된 값들의 합이 얼마인지가 필요하므로 2개의 펜윅트리를 사용한다.
비용 구하기
앞서 말한대로 왼쪽과 오른쪽을 나눠서 구해주면 된다.
ll left = value*sum(tree_cnt,1,value-1) - sum(tree_sum,1,value-1);
ll right = sum(tree_sum, value+1, max_n) - value*sum(tree_cnt,value+1,max_n);value-1, value+1 을 해주는 것은 현재 값과 겹치면 안되므로 이후, 이전의 값부터 사용한 것임을 명시하자.
🔥배운 점
펜윅트리를 어떻게 사용해야할지 잘 체감이 안되었는데, 이번 문제를 통해 구간합을 빠르게 얻을 수 있는 자료구조임을 한번 더 체감했다. 더 익숙해지도록 노력해야겠다는 생각이 들었다.
