fenwick tree 썸네일형 리스트형 THE100YEARSWAR 백년전쟁 풀이 문제: https://algospot.com/judge/problem/read/THE100YEARSWAR 문제 해석 1,2번 왕을 제외한 모든 귀족은 종신 관계를 가지고 있으며 입력에서 종신관계의 순서는 임의의 순서로 들어오나 결국에는 1,2번을 루트로 한 두개의 트리가 완성된다. 들어오는 순서가 임의이기 때문에 입력을 받으면서 전처리는 불가능하다. 모든 입력을 다 받고 난 뒤에 전처리를 행해야 한다. 한 귀족이 배신을 하면 그 귀족 아래의 모든 귀족이 배신을 한다. 즉 그 배신하는 귀족을 루트로하는 부분트리내 모든 노드가 배신을 한다. 입력 받기 예를 들면 귀족이 총 19명이고 1~19번 귀족=노드의 입력이 이런 형태로 들어왔다고 합시다. 이러한 트리 구조를 받을 수 있는 자료형을 먼저 만들어야 합니다.. 더보기 [C++] 펜윅트리 (이진 인덱스 트리) - 구간합 구해주는 트리 struct FenwickTree { vector tree; FenwickTree(int n) : tree(n + 1) {} inline int sum(int pos) { ++pos; int ret = 0; while (pos > 0) { ret += tree[pos]; pos &= (pos - 1); } return ret; } inline void add(int pos, int val) { ++pos; while (pos < (int) tree.size()) { tree[pos] += val; pos += (pos & -pos); } }}; 사용법생성자 FenwickTree fenwickTree(n) : n은 들어갈 노드의 개수int sum(int pos) : 0번~pos번째까지의 합을 구해준다.(내.. 더보기 이전 1 다음
