[Data Structure] Binary Indexed Tree

오늘은 Binary Indexed Tree 를 정리해볼까 한다. 나만을 위한. 나를 위한 정리다.

Binary Indexed Tree의 존재 이유는 부모노드가 자식노드들을 대표할 수 있게 하기 위함인데 자식들의 합이 부모노드가 된다. 예를 들어 방대한 수의 배열이 있을 때 그것들을 다 더하다가 시간이 다 지나는 경우에 쓰기 적합하다. 최솟값, 최댓값도 적용 가능한 대표적인 예다.

Binary 라는 이름이 붙은 것 답게 부모 노드는 자식 노드를 오직 2개만 갖게 된다.
기본적인 개념은 아래와 같다.





검색 하다보니 정말 잘 정리된 사이트를 찾았다.

https://www.acmicpc.net/blog/view/21
위의 설명을 손으로 따라간 흔적을 여기에 남긴다.

해당 블로그에 있는 코드

#include <cstdio> #include <vector> using namespace std; long long sum(vector<long long> &tree, int i) { long long ans = 0; while (i > 0) { ans += tree[i]; i -= (i & -i); } return ans; } void update(vector<long long> &tree, int i, long long diff) { while (i < tree.size()) { tree[i] += diff; i += (i & -i); } }

[Algorithm] Prim 과 Kruskal 그리고 Dijkstra 와 Floyd

이 4가지 알고리즘이 자꾸만 헷갈려서 심플하게 정리해 둔다.


- Prim과 Kruskal : MST (Minimumm Spanning Tree) 를 만드는 알고리즘

Prim 은 시작 정점부터 시작해서 가까이에 있는 정점으로 가는 패스 중 가장 최소값을 찾아서 연결해 나가는 방식이다. Greedy 적인 요소가 다분하다. 또한 Shortest Path를 찾는 알고리즘인 Dijkstra와 아주아주아주아주 유사하다.

반면 Kruskal은 Heap과 Union-Find 자료구조를 이용해서 MST를 만드는데 전체에서 가장 작은 Path들을 찾아서 서로서로 연결시켜 나가면서 MST를 만든다. Kruskal도 Greedy 적이다.



- Shortest Path 를 찾는 알고리즘 : Dijkstra 와 Floyd

Dijkstra는 시작점에서 가장 가까운 정점들 중 가장 최소값을 가진 Path를 따라간다. Prim과 매우 유사하다.

Floyd는 DP(Dynamic Programming) 방식으로 전체를 모두 스캔해 가면서 개선한다... 코드가 아주 짧은 것이 특징!

정리 종료!!