持久化資料結構完全指南 — 路徑複製、Fat Node 與持久化線段樹 | 資料結構與演算法

// ─── 持久化陣列：基於完全二元樹的路徑複製 ──────────────────

class PersistentArrayNode {
  left: PersistentArrayNode | null = null;
  right: PersistentArrayNode | null = null;
  value: number = 0; // 僅葉節點有值
}

class PersistentArray {
  private roots: PersistentArrayNode[] = [];
  private size: number;

  constructor(arr: number[]) {
    this.size = arr.length;
    // 版本 0：從原始陣列建構完全二元樹
    this.roots.push(this.build(arr, 0, this.size - 1));
  }

  // 建構完全二元樹，葉節點對應陣列元素
  private build(
    arr: number[], lo: number, hi: number
  ): PersistentArrayNode {
    const node = new PersistentArrayNode();
    if (lo === hi) {
      node.value = arr[lo];
      return node;
    }
    const mid = (lo + hi) >> 1;
    node.left = this.build(arr, lo, mid);
    node.right = this.build(arr, mid + 1, hi);
    return node;
  }

  // 在指定版本上更新位置 pos 的值，回傳新版本號
  update(version: number, pos: number, val: number): number {
    const newRoot = this.updateNode(
      this.roots[version], 0, this.size - 1, pos, val
    );
    this.roots.push(newRoot);
    return this.roots.length - 1; // 回傳新版本號
  }

  // 路徑複製：只複製根到修改點的路徑
  private updateNode(
    node: PersistentArrayNode,
    lo: number, hi: number,
    pos: number, val: number
  ): PersistentArrayNode {
    const newNode = new PersistentArrayNode();
    if (lo === hi) {
      newNode.value = val;
      return newNode;
    }
    // 複製左右子節點的參照（結構共享）
    newNode.left = node.left;
    newNode.right = node.right;

    const mid = (lo + hi) >> 1;
    if (pos <= mid) {
      // 修改點在左子樹，只複製左路徑
      newNode.left = this.updateNode(node.left!, lo, mid, pos, val);
    } else {
      // 修改點在右子樹，只複製右路徑
      newNode.right = this.updateNode(node.right!, mid + 1, hi, pos, val);
    }
    return newNode;
  }

  // 查詢指定版本、指定位置的值
  query(version: number, pos: number): number {
    return this.queryNode(this.roots[version], 0, this.size - 1, pos);
  }

  private queryNode(
    node: PersistentArrayNode,
    lo: number, hi: number, pos: number
  ): number {
    if (lo === hi) return node.value;
    const mid = (lo + hi) >> 1;
    if (pos <= mid) {
      return this.queryNode(node.left!, lo, mid, pos);
    } else {
      return this.queryNode(node.right!, mid + 1, hi, pos);
    }
  }

  // 取得目前版本數
  getVersionCount(): number {
    return this.roots.length;
  }
}

// ─── 使用範例 ──────────────────────────────────────────────

const parr = new PersistentArray([10, 20, 30, 40, 50]);

// 版本 0：[10, 20, 30, 40, 50]
console.log(parr.query(0, 2)); // 輸出：30

// 在版本 0 基礎上修改位置 2 的值為 99，產生版本 1
const v1 = parr.update(0, 2, 99);
console.log(parr.query(v1, 2)); // 輸出：99
console.log(parr.query(0, 2));  // 輸出：30（版本 0 不受影響）

// 在版本 0 基礎上修改位置 4 的值為 77，產生版本 2（分支！）
const v2 = parr.update(0, 4, 77);
console.log(parr.query(v2, 4)); // 輸出：77
console.log(parr.query(v1, 4)); // 輸出：50（版本 1 不受影響）
console.log(parr.query(0, 4));  // 輸出：50（版本 0 不受影響）

// ─── 持久化鏈結串列（Persistent Linked List）──────────────

class PNode<T> {
  constructor(
    public readonly value: T,
    public readonly next: PNode<T> | null
  ) {}
}

class PersistentList<T> {
  private constructor(
    private readonly head: PNode<T> | null,
    public readonly size: number
  ) {}

  // 建立空串列
  static empty<T>(): PersistentList<T> {
    return new PersistentList<T>(null, 0);
  }

  // 在頭部插入元素，回傳新版本（O(1) — 完美結構共享）
  prepend(value: T): PersistentList<T> {
    return new PersistentList(
      new PNode(value, this.head), this.size + 1
    );
  }

  // 取得頭部元素
  getHead(): T | undefined {
    return this.head?.value;
  }

  // 移除頭部元素，回傳新版本（O(1)）
  tail(): PersistentList<T> {
    if (!this.head) throw new Error("空串列無法 tail");
    return new PersistentList(this.head.next, this.size - 1);
  }

  // 取得第 k 個元素（O(k)）
  get(index: number): T | undefined {
    let cur = this.head;
    for (let i = 0; i < index && cur; i++) {
      cur = cur.next;
    }
    return cur?.value;
  }

  // 轉為陣列（方便除錯）
  toArray(): T[] {
    const result: T[] = [];
    let cur = this.head;
    while (cur) {
      result.push(cur.value);
      cur = cur.next;
    }
    return result;
  }
}

// ─── 使用範例 ──────────────────────────────────────────────

const list0 = PersistentList.empty<number>();
const list1 = list0.prepend(3).prepend(2).prepend(1);
const list2 = list1.prepend(0); // 在 list1 前面加 0
const list3 = list1.tail();     // 移除 list1 的頭部

console.log(list1.toArray()); // 輸出：[1, 2, 3]
console.log(list2.toArray()); // 輸出：[0, 1, 2, 3]
console.log(list3.toArray()); // 輸出：[2, 3]

// list1 完全不受 list2、list3 的影響
console.log(list1.toArray()); // 輸出：[1, 2, 3]

// ─── 持久化線段樹（主席樹）：區間第 K 小 ────────────────────

class PSegNode {
  left: PSegNode | null = null;
  right: PSegNode | null = null;
  count: number = 0;
}

class PersistentSegmentTree {
  private roots: PSegNode[] = [];
  private sorted: number[];
  private m: number; // 離散化後的值域大小

  constructor(arr: number[]) {
    // 步驟 1：離散化 — 將值映射到 [0, m-1]
    this.sorted = [...new Set(arr)].sort((a, b) => a - b);
    this.m = this.sorted.length;

    // 步驟 2：建立 n+1 個版本（v0 為空版本）
    let prev = new PSegNode();
    this.roots.push(prev); // version 0：空線段樹

    for (const val of arr) {
      const idx = this.compress(val);
      const newRoot = this.update(prev, 0, this.m - 1, idx);
      this.roots.push(newRoot);
      prev = newRoot;
    }
  }

  // 離散化：二分搜尋找到值在 sorted 中的索引
  private compress(val: number): number {
    let lo = 0, hi = this.sorted.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.sorted[mid] < val) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }

  // 路徑複製更新：在位置 pos 的計數 +1
  private update(
    node: PSegNode, lo: number, hi: number, pos: number
  ): PSegNode {
    const newNode = new PSegNode();
    newNode.left = node.left;   // 結構共享
    newNode.right = node.right; // 結構共享
    newNode.count = node.count + 1;

    if (lo === hi) return newNode;

    const mid = (lo + hi) >> 1;
    if (pos <= mid) {
      newNode.left = this.update(
        node.left ?? new PSegNode(), lo, mid, pos
      );
    } else {
      newNode.right = this.update(
        node.right ?? new PSegNode(), mid + 1, hi, pos
      );
    }
    return newNode;
  }

  // 查詢 [l, r]（1-indexed）區間第 k 小
  query(l: number, r: number, k: number): number {
    return this.kth(
      this.roots[l - 1], this.roots[r],
      0, this.m - 1, k
    );
  }

  // 差值線段樹上的第 K 小查找
  private kth(
    leftRoot: PSegNode, rightRoot: PSegNode,
    lo: number, hi: number, k: number
  ): number {
    if (lo === hi) return this.sorted[lo];

    const mid = (lo + hi) >> 1;
    // 左子樹在 [l, r] 區間內的元素數量
    const leftCount =
      (rightRoot.left?.count ?? 0) - (leftRoot.left?.count ?? 0);

    if (k <= leftCount) {
      // 第 K 小在左子樹
      return this.kth(
        leftRoot.left ?? new PSegNode(),
        rightRoot.left ?? new PSegNode(),
        lo, mid, k
      );
    } else {
      // 第 K 小在右子樹，k 要扣掉左子樹的數量
      return this.kth(
        leftRoot.right ?? new PSegNode(),
        rightRoot.right ?? new PSegNode(),
        mid + 1, hi, k - leftCount
      );
    }
  }
}

// ─── 使用範例 ──────────────────────────────────────────────

const pstArr = [3, 1, 4, 1, 5, 2, 6, 5, 3, 5];
const pst = new PersistentSegmentTree(pstArr);

// 查詢 [2, 6] 的第 3 小（子陣列 [1, 4, 1, 5, 2]）
console.log(pst.query(2, 6, 3)); // 輸出：2

// 查詢 [1, 10] 的第 5 小（全陣列第 5 小）
console.log(pst.query(1, 10, 5)); // 輸出：3

// 查詢 [3, 7] 的第 1 小（子陣列 [4, 1, 5, 2, 6]）
console.log(pst.query(3, 7, 1)); // 輸出：1

// ─── 持久化 Treap ─────────────────────────────────────────

class TreapNode {
  left: TreapNode | null = null;
  right: TreapNode | null = null;
  key: number;
  priority: number;
  size: number = 1;

  constructor(key: number) {
    this.key = key;
    this.priority = Math.random(); // 隨機優先級
  }
}

class PersistentTreap {
  private roots: (TreapNode | null)[] = [null]; // 版本 0 為空樹

  private getSize(node: TreapNode | null): number {
    return node?.size ?? 0;
  }

  private updateSize(node: TreapNode): void {
    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);
  }

  // 複製節點（路徑複製的基礎）
  private clone(node: TreapNode): TreapNode {
    const newNode = new TreapNode(node.key);
    newNode.left = node.left;
    newNode.right = node.right;
    newNode.priority = node.priority;
    newNode.size = node.size;
    return newNode;
  }

  // 分裂：將樹分成 key ≤ k 和 key > k 兩棵（持久化版本）
  private split(
    node: TreapNode | null, k: number
  ): [TreapNode | null, TreapNode | null] {
    if (!node) return [null, null];

    const cur = this.clone(node); // 路徑複製

    if (cur.key <= k) {
      const [l, r] = this.split(cur.right, k);
      cur.right = l;
      this.updateSize(cur);
      return [cur, r];
    } else {
      const [l, r] = this.split(cur.left, k);
      cur.left = r;
      this.updateSize(cur);
      return [l, cur];
    }
  }

  // 合併兩棵 Treap（持久化版本）
  private merge(
    left: TreapNode | null, right: TreapNode | null
  ): TreapNode | null {
    if (!left) return right;
    if (!right) return left;

    if (left.priority > right.priority) {
      const cur = this.clone(left); // 路徑複製
      cur.right = this.merge(cur.right, right);
      this.updateSize(cur);
      return cur;
    } else {
      const cur = this.clone(right); // 路徑複製
      cur.left = this.merge(left, cur.left);
      this.updateSize(cur);
      return cur;
    }
  }

  // 在指定版本插入值，回傳新版本號
  insert(version: number, key: number): number {
    const root = this.roots[version];
    const [l, r] = this.split(root, key);
    const node = new TreapNode(key);
    const merged = this.merge(this.merge(l, node), r);
    this.roots.push(merged);
    return this.roots.length - 1;
  }

  // 在指定版本刪除值，回傳新版本號
  remove(version: number, key: number): number {
    const root = this.roots[version];
    const [l, mr] = this.split(root, key - 1);
    const [_, r] = this.split(mr, key); // _ 就是 key 節點（被丟棄）
    const merged = this.merge(l, r);
    this.roots.push(merged);
    return this.roots.length - 1;
  }

  // 查詢指定版本中第 k 小的值
  kth(version: number, k: number): number | undefined {
    return this.kthNode(this.roots[version], k);
  }

  private kthNode(node: TreapNode | null, k: number): number | undefined {
    if (!node) return undefined;
    const leftSize = this.getSize(node.left);
    if (k <= leftSize) return this.kthNode(node.left, k);
    if (k === leftSize + 1) return node.key;
    return this.kthNode(node.right, k - leftSize - 1);
  }

  // 取得指定版本的樹大小
  size(version: number): number {
    return this.getSize(this.roots[version]);
  }
}

// ─── 使用範例 ──────────────────────────────────────────────

const treap = new PersistentTreap();
const tv1 = treap.insert(0, 5); // 版本 1：{5}
const tv2 = treap.insert(tv1, 3); // 版本 2：{3, 5}
const tv3 = treap.insert(tv2, 7); // 版本 3：{3, 5, 7}
const tv4 = treap.insert(tv1, 1); // 版本 4：從版本 1 分支 {1, 5}

console.log(treap.kth(tv3, 2)); // 輸出：5（版本 3 第 2 小）
console.log(treap.kth(tv4, 1)); // 輸出：1（版本 4 第 1 小）
console.log(treap.size(tv3));   // 輸出：3
console.log(treap.size(tv4));   // 輸出：2

// ─── 通用版本管理系統 ─────────────────────────────────────

interface Snapshot<T> {
  id: number;
  parentId: number | null;
  timestamp: number;
  label: string;
  data: T;
}

class VersionManager<T> {
  private snapshots: Map<number, Snapshot<T>> = new Map();
  private nextId: number = 0;
  private currentId: number = -1;

  // 建立初始版本
  init(data: T, label: string = "initial"): number {
    const id = this.nextId++;
    this.snapshots.set(id, {
      id, parentId: null,
      timestamp: Date.now(), label, data
    });
    this.currentId = id;
    return id;
  }

  // 從指定版本建立新版本
  commit(
    parentId: number,
    data: T,
    label: string
  ): number {
    if (!this.snapshots.has(parentId)) {
      throw new Error(`版本 ${parentId} 不存在`);
    }
    const id = this.nextId++;
    this.snapshots.set(id, {
      id, parentId,
      timestamp: Date.now(), label, data
    });
    this.currentId = id;
    return id;
  }

  // 查詢指定版本的資料
  checkout(versionId: number): T {
    const snap = this.snapshots.get(versionId);
    if (!snap) throw new Error(`版本 ${versionId} 不存在`);
    this.currentId = versionId;
    return snap.data;
  }

  // 取得版本歷史（從指定版本回溯到初始版本）
  getHistory(versionId: number): Snapshot<T>[] {
    const history: Snapshot<T>[] = [];
    let current: number | null = versionId;
    while (current !== null) {
      const snap = this.snapshots.get(current);
      if (!snap) break;
      history.push(snap);
      current = snap.parentId;
    }
    return history.reverse();
  }

  // 取得所有版本 ID
  getAllVersions(): number[] {
    return [...this.snapshots.keys()];
  }

  getCurrentId(): number {
    return this.currentId;
  }
}

// ─── 使用範例 ──────────────────────────────────────────────

const vm = new VersionManager<string[]>();
const vid0 = vm.init(["main.ts", "utils.ts"], "專案初始化");
const vid1 = vm.commit(vid0, ["main.ts", "utils.ts", "api.ts"], "新增 API 模組");
const vid2 = vm.commit(vid1, ["main.ts", "utils.ts", "api.ts", "test.ts"], "新增測試");

// 從版本 0 分支（模擬 git branch）
const vid3 = vm.commit(vid0, ["main.ts", "utils.ts", "config.ts"], "新增設定檔");

console.log(vm.checkout(vid2));
// 輸出：["main.ts", "utils.ts", "api.ts", "test.ts"]

console.log(vm.checkout(vid3));
// 輸出：["main.ts", "utils.ts", "config.ts"]

console.log(vm.getHistory(vid2).map(s => s.label));
// 輸出：["專案初始化", "新增 API 模組", "新增測試"]

console.log(vm.getHistory(vid3).map(s => s.label));
// 輸出：["專案初始化", "新增設定檔"]

#include <bits/stdc++.h>
using namespace std;

// 靜態記憶體池：避免動態記憶體分配
const int MAXNODES = 20000005;

struct Node {
    int left, right, cnt;
} tree[MAXNODES];

int tot = 0; // 全域節點計數器

// 建立新節點（路徑複製）
int newNode(int node) {
    tree[++tot] = tree[node]; // 複製舊節點的所有欄位
    return tot;
}

// 更新：在值域 [lo, hi] 的位置 pos 計數 +1
int update(int node, int lo, int hi, int pos) {
    int cur = newNode(node); // 路徑複製
    tree[cur].cnt++;
    if (lo == hi) return cur;

    int mid = (lo + hi) / 2;
    if (pos <= mid)
        tree[cur].left = update(tree[node].left, lo, mid, pos);
    else
        tree[cur].right = update(tree[node].right, mid + 1, hi, pos);
    return cur;
}

// 在差值線段樹上查詢第 k 小
int kth(int lNode, int rNode, int lo, int hi, int k) {
    if (lo == hi) return lo;

    int mid = (lo + hi) / 2;
    int leftCnt = tree[tree[rNode].left].cnt
                - tree[tree[lNode].left].cnt;

    if (k <= leftCnt)
        return kth(tree[lNode].left, tree[rNode].left,
                   lo, mid, k);
    else
        return kth(tree[lNode].right, tree[rNode].right,
                   mid + 1, hi, k - leftCnt);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    vector<int> sorted_a;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sorted_a.push_back(a[i]);
    }

    // 離散化
    sort(sorted_a.begin(), sorted_a.end());
    sorted_a.erase(
        unique(sorted_a.begin(), sorted_a.end()),
        sorted_a.end()
    );
    int m = sorted_a.size();

    auto compress = [&](int x) {
        return lower_bound(
            sorted_a.begin(), sorted_a.end(), x
        ) - sorted_a.begin();
    };

    // 建立 n+1 個版本
    vector<int> roots(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        roots[i] = update(roots[i - 1], 0, m - 1,
                          compress(a[i]));
    }

    // 處理查詢
    while (q--) {
        int l, r, k;
        cin >> l >> r >> k;
        int idx = kth(roots[l - 1], roots[r], 0, m - 1, k);
        cout << sorted_a[idx] << "\n";
    }

    return 0;
}

// ─── 持久化並查集（概念骨架）────────────────────────────────

class PersistentUnionFind {
  private parentArr: PersistentArray;
  private rankArr: PersistentArray;

  constructor(n: number) {
    // 初始化：每個元素的 parent 指向自己，rank 為 0
    const parents = Array.from({ length: n }, (_, i) => i);
    const ranks = new Array(n).fill(0);
    this.parentArr = new PersistentArray(parents);
    this.rankArr = new PersistentArray(ranks);
  }

  // 在指定版本上查找根（不做路徑壓縮）
  find(version: number, x: number): number {
    let parent = this.parentArr.query(version, x);
    while (parent !== x) {
      x = parent;
      parent = this.parentArr.query(version, x);
    }
    return x;
  }

  // 在指定版本上合併兩個集合，回傳新版本號
  union(version: number, x: number, y: number): number {
    const rootX = this.find(version, x);
    const rootY = this.find(version, y);
    if (rootX === rootY) return version; // 同一集合，不需合併

    const rankX = this.rankArr.query(version, rootX);
    const rankY = this.rankArr.query(version, rootY);

    let newVersion: number;
    if (rankX < rankY) {
      newVersion = this.parentArr.update(version, rootX, rootY);
    } else if (rankX > rankY) {
      newVersion = this.parentArr.update(version, rootY, rootX);
    } else {
      newVersion = this.parentArr.update(version, rootY, rootX);
      // 注意：這裡需要在新版本上更新 rank
      // 實際實作中需要讓 parentArr 和 rankArr 共用版本號
      // 此處為概念示意
    }
    return newVersion;
  }
}

// 線段樹實作（持久化線段樹的基礎）
class NumArray {
  private tree: number[];
  private n: number;

  constructor(nums: number[]) {
    this.n = nums.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.build(nums, 1, 0, this.n - 1);
  }

  private build(
    nums: number[], node: number, lo: number, hi: number
  ): void {
    if (lo === hi) {
      this.tree[node] = nums[lo];
      return;
    }
    const mid = (lo + hi) >> 1;
    this.build(nums, 2 * node, lo, mid);
    this.build(nums, 2 * node + 1, mid + 1, hi);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }

  update(index: number, val: number): void {
    this.updateHelper(1, 0, this.n - 1, index, val);
  }

  private updateHelper(
    node: number, lo: number, hi: number,
    pos: number, val: number
  ): void {
    if (lo === hi) {
      this.tree[node] = val;
      return;
    }
    const mid = (lo + hi) >> 1;
    if (pos <= mid)
      this.updateHelper(2 * node, lo, mid, pos, val);
    else
      this.updateHelper(2 * node + 1, mid + 1, hi, pos, val);
    this.tree[node] = this.tree[2 * node] + this.tree[2 * node + 1];
  }

  sumRange(left: number, right: number): number {
    return this.queryHelper(1, 0, this.n - 1, left, right);
  }

  private queryHelper(
    node: number, lo: number, hi: number,
    l: number, r: number
  ): number {
    if (r < lo || hi < l) return 0;
    if (l <= lo && hi <= r) return this.tree[node];
    const mid = (lo + hi) >> 1;
    return this.queryHelper(2 * node, lo, mid, l, r) +
           this.queryHelper(2 * node + 1, mid + 1, hi, l, r);
  }
}

// 核心思路：值域線段樹 + 從右往左建版本
function countSmaller(nums: number[]): number[] {
  const sorted = [...new Set(nums)].sort((a, b) => a - b);
  const m = sorted.length;
  const compress = (v: number) => {
    let lo = 0, hi = sorted.length - 1;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (sorted[mid] < v) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  };

  // 使用 BIT（樹狀陣列）更簡潔
  const bit = new Array(m + 2).fill(0);
  const bitUpdate = (i: number) => {
    for (i++; i <= m; i += i & (-i)) bit[i]++;
  };
  const bitQuery = (i: number) => {
    let s = 0;
    for (i++; i > 0; i -= i & (-i)) s += bit[i];
    return s;
  };

  const result = new Array(nums.length);
  for (let i = nums.length - 1; i >= 0; i--) {
    const idx = compress(nums[i]);
    result[i] = bitQuery(idx - 1);
    bitUpdate(idx);
  }
  return result;
}

console.log(countSmaller([5, 2, 6, 1]));
// 輸出：[2, 1, 1, 0]