배열을 이용한 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의 거듭제곱수여야 한다.

 

코드는 다음과 같다.

#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;