[Algorithm] Merge Sort Tree 구현 Merge Sort Tree는 Segment Tree의 한 종류로, 그 값이 구간의 정렬된 배열을 들고 있는 것이 특징이다. Merge Sort Tree의 구현 또한 Struct를 써서 깔끔하게 구현할 수 있다. Merge Sort Tree를 사용해서 구현할 수 있는 연산은 (1) 특정 구간의 k번째 작은값/큰값 -> O(log^3 N) => query(root, s, e,
[Algorithm] Segment Tree 구현 세그먼트 트리를 구조체로 구현하면 정말 깔끔해진다. 무한 자기참조를 위해 남겨 놓는다. Maximum 세그먼트 트리를 구현한 소스를 남긴다. #include using namespace std; struct Node { Node *l, *r; int s,e; int v; Node(int s,int e) : l(NULL), r(NULL), s(s), e(e), v(0){} ~Node(){if(l) delete
PS 알고리즘 정리(Last Edit : 2023/04/17) 아래 분류는 계속해서 수정되고 추가될 예정이다. 내가 공부한 거를 정리하고 있다. 알고리즘 분류 00_Complete Search Backtracking : Pruning 01_Math Number Theory =Prime Number ==Sieve of Eratosthenes =Extended Euclidean Algorithm =Chinese Remainder Theorem FFT - DFT 02_Geometry =Convex Hull ==Rotating Calipers 03_Greedy 04_DP ==Convex Hull Trick 05_