Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- ICPC 연습
- boj
- 그래프
- 컨벡스 헐
- Divide and conquer optimization
- 코드포스
- codeforces
- Manacher's algorithm
- 8192
- 기하 알고리즘
- 기하
- IOI 2013
- POI Solution
- Z 알고리즘
- acmicpc.net
- DP
- BAPC
- 2794
- 구현
- convex hull
- 14179
- 백준 온라인 저지
- 볼록 껍질
- JOI 2018
- JOI
- 세그먼트 트리
- Implementation
- Manacher 알고리즘
- BAPC 2018
- Z algorithm
Archives
- Today
- Total
프로그래밍 연습장
배열을 이용한 Persistent Segment Tree의 구현 본문
[UPD: 2019. 10. 04] 우리 팀 팀노트 버전으로 바꾸었다. 완전히 나의 코딩 스타일로 구현되었다.
PST를 배열로는 처음 짜 봤다. 은근 굉장히 간결하고 이쁘게 나와서 여기다 박제해두려 한다. 포인터 기반보다 안정적이고 훨씬 더 빠르다.
$create(s, e)$ : 구간 $[s, e]$를 나타내는 빈 구간 트리를 하나 만들고, 그 루트 번호를 반환한다.
$update(s, e, x, p, v)$ : $x$를 루트로 하는 트리가 이미 존재해야 한다. 구간의 위치 $p \in [s, e]$에다가 $v$를 더해 만든 새로운 트리의 루트 번호를 반환한다.
$query(s, e, x, l, r)$ : $x$를 루트로 한 트리에서 $[l, r]$ 구간의 값의 합을 반환한다.
위 모두에 $(s, e)$는 구현의 편의를 위해 만든 변수이며, 구조체 밖에서 호출할 때에는 항상 고정되어야 한다. $(s, e)$를 $(0, maxn-1)$로 고정시켜 둔 복사본을 각 함수마다 만들어 두었다.
$maxn$은 항상 2의 거듭제곱수여야 한다.
코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<17, logn = 17, maxq = 200004, noden = 2 * maxn + maxq * (logn + 1);
int root[maxn];
struct pst {
int t[noden], l[noden], r[noden], cnt;
int create(int s, int e) {
int k = cnt++;
t[k] = 0;
if (s<e) {
int m = (s+e)/2;
l[k] = create(s, m);
r[k] = create(m+1, e);
}
return k;
}
int create() { return create(0, maxn-1); }
int update(int s, int e, int x, int p, int v) {
if (not (s<=p and p<=e)) return x;
int k = cnt++;
if (s==e) {
t[k] = t[x] + v;
} else {
int m = (s+e)/2;
l[k] = update(s, m, l[x], p, v);
r[k] = update(m+1, e, r[x], p, v);
t[k] = t[l[k]] + t[r[k]];
} return k;
}
int update(int x, int p, int v) { return update(0, maxn-1, x, p, v); }
int query(int s, int e, int x, int ql, int qr) {
if (ql<=s and e<=qr) return t[x];
else if (ql<=e and s<=qr) {
int m = (s+e)/2;
return query(s, m, l[x], ql, qr) + query(m+1, e, r[x], ql, qr);
} return 0;
}
int query(int x, int l, int r) { return query(0, maxn-1, x, l, r); }
} t;
|
cs |
'알고리즘' 카테고리의 다른 글
Manacher의 알고리즘과 Z 알고리즘 (0) | 2018.02.27 |
---|---|
그래프의 간선 리스트 표현 (2) | 2017.12.06 |
Heavy Light Decomposition의 구현 (0) | 2017.12.03 |
좌표평면에서 가장 먼 점 찾기 (2) | 2017.09.08 |
Graham Scan (0) | 2017.08.19 |
Comments