자료구조 (4) 썸네일형 리스트형 Segment tree beats (세그 비츠) 4년 전 코포 블로그 글로 올라온 자료구조로, 언젠가부터 웰노운이 된 듯하다. segment tree with lazy propogation을 확장한 형태로, $O(NlogN)$ 혹은 $O(Nlog^2N)$ 정도의 시간복잡도를 가진다. 아이디어 일반적인 레이지 세그트리는 아래와 같이 구현한다. void updseg(int idx, int l, int r, int x, int y, int z) { if (r < x || y < l) return; if (x Propogation 없는 lazy 세그트리 "lazy 세그트리" 자체가 "segment tree with lazy propogation"를 줄여서 부르는 말이기 때문에 propogation이 없다는 것이 다소 이상하기는 하지만, 일부 문제의 경우 세그트리에서 propogation을 lazy하게 하는 것을 넘어서서 아예 하지 않으면 더 효율성을 올릴 수 있다. 시간복잡도는 $O(NlogN)$으로 같다. 이 글에도 같은 내용이 정리되어 있다. 우선 일반적인 lazy 세그트리를 먼저 되짚어보자. 구간 갱신 쿼리와 구간 조회 쿼리(혹은 점 조회 쿼리)가 존재한다. 구간 조회 쿼리에 해당하는 값들을 각 노드에서 들고 있고, $O(logN)$개의 노드를 merge하면 구간 조회 쿼리의 답을 구할 수 있다. 구간 갱신 쿼리는 원래는 $O(N)$개의 노드를 갱.. Fenwick Tree (Binary Indexed Tree, BIT) Fenwick Tree (a.k.a. Binary Indexed Tree, BIT)에 대해 알아보도록 하겠다. 펜윅의 기능은 segment tree와 비슷하고, 더 한정적이다. 하지만 비재귀로 쉽게 구현이 가능하고 속도가 훨씬 빠르다. (세그로 짠 $O(logN)$보다 펜윅으로 짠 $O(log^2N)$이 더 빠를 정도.) 그렇기 때문에 펜윅으로 구현이 가능하다면 세그 대신 펜윅을 사용하는 것이 좋다. 수열의 누적합 문제를 풀어보자. 수열 $A[1 ... N]$에 대해 $A[i]$의 값을 바꾸는 점 갱신 쿼리와, 누적합 $A[1] + ... + A[i]$를 구하는 쿼리가 들어온다. 편의상 $N=2^m$이라 하자. 펜윅 $bit[1 ... N]$은 $A$의 구간합에 해당하는 값을 가진다. 구체적으로는, $b.. Persistent Segment Tree (PST) $x, y$좌표가 $0$ 이상 $N$ 미만의 정수인 점 $N$개가 있다. $x, y$좌표는 모두 다르다. 이 때, 특정 직사각형 내부에 있는 점의 개수를 묻는 쿼리가 들어온다. offline 풀이를 생각해보자. 직사각형 내부의 점의 개수를 구하는 쿼리는, $\sqsupset$ 형태의 구역에 있는 점들의 개수를 구하는 쿼리 2개로 쪼갤 수 있다. $\sqsupset$ 내부의 점의 개수를 구하는 쿼리들을을 $x$ 좌표($\sqsupset$에서 오른쪽 |) 순으로 정렬하고, 그 $x$ 좌표까지의 점들에 대해 $y$ 좌표를 BIT 또는 segment tree로 관리하면 $O(NlogN+QlogN)$에 해결할 수 있다. 이제 online 풀이를 생각해보자. offline과 같이 풀려고 하면 $O(N)$ 크기의 s.. 이전 1 다음