백준 1280번 나무심기

문제링크: https://www.acmicpc.net/problem/1280

사용한 알고리즘: 펜윅트리


나무를 심을 때 마다 발생하는 비용을 곱한 합을 출력하는 문제였습니다.
문제풀이는 다음과 같습니다.
(1) 나무들의 심는 위치들을 펜윅트리로 구현합니다.
(2) i번째에 나무를 심을 때, (왼쪽나무개수Xi) - (왼쪽 나무(i보다 작은)들의 비용합) 과 (오른쪽 나무(i보다 큰)들의 비용합) - (오른쪽나무개수Xi) 를 더해 이를 구하고자 하는 값에 곱해줍니다.
(3) Moudlo 1000000007 을 주었으므로 이를 신경써주며 위 과정을 통해 답을 얻습니다.

2<=N 이라는 조건을 주었으므로 N=1인 경우는 생각할 필요가 없었습니다.

혹시 펜윅트리에대한 자세한 내용이 궁금한 분들은 아래 링크에 잘 정리되어 잇으니 참고해주세요.
https://www.acmicpc.net/blog/view/21