Fenwick tree 썸네일형 리스트형 BOJ)14288 내리 갈굼4 문제:icpc.me/14288 트리에서 질의를 처리하는 문제이다. 우선 dfs를 이용하여 트리의 번호를 reordering 시켜주어 트리를 구간으로 생각해보자. 문제를 풀기 위해서 일반의 경우와 야자의 경우에 업데이트 시켜주는 영역을 다르게 생각해보자 일반의 경우만 생각해본다면 value가 아래로 전파되기 때문에 나의 자식들의 구간에 업데이트 시켜준 뒤, 답을 가져올 때는 해당 지점의 값을 출력하면 될것이다. 야자의 경우에는 value가 위로 전파되므로 나의 위치에 업데이트 시킨 뒤, 답을 가져올 때, 내 자식들의 업데이트 현황을 다 더해주면 되므로, 자식들의 구간의 합을 출력하면 될것이다. 두가지 모두 Fenwick tree를 이용하여 구현 가능하므로 2개의 fenwick tree를 구현하면 문제를 해.. 더보기 Fenwick Tree(Binary Indexed Tree) http://jason9319.tistory.com/282 문제를 lazy progatition을 이용한 segment tree를 이용하다가 멘탈이 나가서 fenwick tree를 공부하였다. (https://www.acmicpc.net/board/view/15993) 펜윅트리는 BIT(Binary Indexed Tree)로도 불리며 갱신이 이루어지는 range의 구간 합 연산을 빠르게 해결해주는 자료구조로 알려져있다. 자료구조의 정당성과 시간복잡도등은 https://www.acmicpc.net/blog/view/21에 잘 설명이 되어있고 여기서는 간단하게 사용법만 알아보겠다. 123456789101112131415ll tree[MAX_N+1];void update(ll x, ll val) { while.. 더보기 이전 1 다음