Persistent Segment Tree에서는 각 버전, 시간대에 변경된 노드만을 추가로 생성합니다.
업데이트가 일어난다면
변경되는 구간, 경로에 있는 노드만 새로 만들고, 그 외의 노드는 이전 버전의 노드를 그대로 공유합니다.
이 때문에,
하나의 업데이트마다 최대 logN 개의 노드가 추가로 생성될 수 있습니다.
메모리 사용량은 O(N+QlogN)로 됩니다. (Q: 쿼리 개수)
구현 예시
#include <bits/stdc++.h>using namespace std;typedef long long ll;// 노드 구조체 정의struct Node { Node *l, *r; // 왼쪽, 오른쪽 자식 포인터 ll val; // 노드의 값 Node() { l = r = NULL; val = 0; }};const int MAX_N = 100010; // 최대 배열 크기const int MAX_VERSION = 100010; // 최대 버전 수Node* roots[MAX_VERSION]; // 각 버전의 루트 노드int arr[MAX_N]; // 원본 배열int n; // 배열의 크기int version_count = 0; // 현재 버전 수// 세그먼트 트리 초기화 함수void init(Node* node, int start, int end) { // 리프 노드인 경우 if (start == end) { node->val = arr[start]; return; } // 중간 노드 처리 int mid = (start + end) / 2; // 왼쪽, 오른쪽 자식 노드 생성 node->l = new Node(); node->r = new Node(); // 재귀적으로 자식 노드 초기화 init(node->l, start, mid); init(node->r, mid + 1, end); // 현재 노드의 값은 자식 노드 값의 합 node->val = node->l->val + node->r->val;}// 세그먼트 트리 업데이트 함수void update(Node* prv, Node* now, int start, int end, int idx, int new_val) { // 리프 노드에 도달한 경우 if (start == end) { now->val = new_val; return; } int mid = (start + end) / 2; // 업데이트할 자식 노드 결정 if (idx <= mid) { // 왼쪽 자식 업데이트 now->r = prv->r; // 오른쪽 자식은 그대로 재사용 now->l = new Node(); // 왼쪽 자식만 새로 생성 update(prv->l, now->l, start, mid, idx, new_val); } else { // 오른쪽 자식 업데이트 now->l = prv->l; // 왼쪽 자식은 그대로 재사용 now->r = new Node(); // 오른쪽 자식만 새로 생성 update(prv->r, now->r, mid + 1, end, idx, new_val); } // 현재 노드의 값 업데이트 now->val = now->l->val + now->r->val;}// 구간 합 쿼리 함수ll query(Node* node, int start, int end, int l, int r) { // 구간을 벗어난 경우 if (r < start || end < l) return 0; // 완전히 포함된 경우 if (l <= start && end <= r) return node->val; // 부분 구간 처리 int mid = (start + end) / 2; return query(node->l, start, mid, l, r) + query(node->r, mid + 1, end, l, r);}