세그 (2) 썸네일형 리스트형 [BOJ 12858] Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net Tag : segment tree 문제요약 구간 업데이트(덧셈)가 있을 때 쿼리마다 구간의 gcd를 구하라. 풀이 a > b일 때 gcd(a, b) = gcd(a, a - b)임이 잘 알려져있습니다. 따라서 gcd(A[l], ... , A[r]) = gcd(A[l], A[l + 1] - A[l], ... , A[r] - A[r - 1])이 성립합니다. 세그먼트 트리의 각 노.. Randomize Binary Search Trees, Treap INTRO 잘 아려진 BBST(Balanced Binary Search Tree : 균형이진탐색트리)의 종류로는 rb tree, b tree 등이 있습니다. 그러나 위의 rb tree와 같이 대부분의 연산을 \(O(logN)\)에 처리하는 트리는 동작 자체도 복잡하고 구현량이 많기 때문에 직접 구현해가며 PS에 사용하기 어렵습니다. (stl에 있는 것을 가져다 쓰면 좋겠지만 연산을 변형해야하는 경우도 존재하니까요) 그래서 삽입, 삭제 등의 연산에 amortized \(O(logN)\)의 시간복잡도를 가지며 상대적으로 구현량이 적은 Splay Tree를 가장 많이 사용합니다. 하지만 Splay Tree도 zig-zag step 등 헷갈릴만한 요소가 많아서 저는 Treap을 선호합니다. Treap은 일반적인.. 이전 1 다음
