可持久化线段树⚓︎

可持久化线段树是一种支持版本管理的线段树数据结构，允许在进行更新操作时，保留之前的版本，从而可以随时访问和查询历史版本的数据。每次更新操作都会创建一个新的版本，而旧版本的数据仍然可以被访问。

可持久化数组⚓︎

维护这样的一个长度为 $N$ 的数组，支持如下两种操作：

在某个历史版本上修改某一个位置上的值。
访问某个历史版本上的某一位置的值。

此外，每进行一次操作，就会生成一个新的版本。版本编号即为当前操作的编号（从 $1$ 开始编号，版本 $0$ 表示初始状态数组）。

可持久化数组可以用于实现可持久化并查集等数据结构。

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  int64_t left;   // 左子节点编号
  int64_t right;  // 右子节点编号
  int64_t value;  // 叶子节点存储值, 非叶子节点可不存储
};

vector<node> nodes;  // 所有节点

struct p_array {
  explicit p_array() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  int64_t build(int64_t left, int64_t right, const vector<int64_t> &nums) {
    int64_t i = nodes.size();  // 新节点编号
    nodes.emplace_back(node{});
    if (left == right) {  // 叶子节点
      nodes[i].value = nums[left];
      return i;
    }
    int64_t mid    = left + ((right - left) / 2);
    nodes[i].left  = build(left, mid, nums);
    nodes[i].right = build(mid + 1, right, nums);
    return i;
  }

  static int64_t clone(int64_t i) {
    int64_t new_node = nodes.size();  // 新节点编号
    nodes.emplace_back(nodes[i]);     // 克隆当前节点
    return new_node;
  }

  // 修改节点的值, 返回新版本的根节点
  // update(x, val, root, 1, n) 表示将版本v中下标x的值修改为val, root为版本v的根节点
  int64_t update(int64_t index, int64_t val, int64_t i, int64_t l, int64_t r) {
    int64_t new_node = clone(i);  // 克隆当前节点
    if (l == r) {                 // 叶子节点
      nodes[new_node].value = val;
      return new_node;
    }
    int64_t mid = l + ((r - l) / 2);
    if (index <= mid) {
      nodes[new_node].left = update(index, val, nodes[i].left, l, mid);
    } else {
      nodes[new_node].right = update(index, val, nodes[i].right, mid + 1, r);
    }
    return new_node;
  }

  // 查询某个版本的某个下标的值
  // query(x, root, 1, n) 表示查询版本v中下标x的值, root为版本v的根节点
  int64_t query(int64_t index, int64_t i, int64_t l, int64_t r) {
    if (l == r) { return nodes[i].value; }
    int64_t mid = l + ((r - l) / 2);
    if (index <= mid) { return query(index, nodes[i].left, l, mid); }
    return query(index, nodes[i].right, mid + 1, r);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;

  nodes.reserve(70 * n + 20 * m);  // 经验值
  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  p_array tree;

  vector<int64_t> root(m + 1);
  root[0] = tree.build(1, n, nums);  // 构建初始版本0

  int64_t v, op;
  for (int64_t i = 1; i <= m; i++) {
    cin >> v >> op;
    if (op == 1) {  // 修改
      int64_t p, c;
      cin >> p >> c;
      root[i] = tree.update(p, c, root[v], 1, n);
    } else if (op == 2) {  // 查询
      int64_t p;
      cin >> p;
      cout << tree.query(p, root[v], 1, n) << "\n";
      root[i] = root[v];  // 新版本和旧版本相同
    }
  }
  return 0;
}

可持久化权值线段树⚓︎

可持久化权值线段树可以用于解决区间第 $k$ 小数、区间元素出现次数等问题。

【模板】可持久化线段树 2

Hint

通过离散化将元素值映射到一个较小的范围内，方便在线段树中进行处理。
构建一个初始版本的线段树，表示空数组。
对于每个元素，基于前一个版本的线段树，更新该元素所在位置的值，生成一个新的版本。
查询时，利用两个版本的线段树（区间的左右端点对应的版本）进行差分，计算出区间内每个子区间的元素数量，从而定位第 $k$ 小的元素。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  int64_t left;
  int64_t right;
  int64_t size;  // 记录该节点区间内有多少个元素
};

vector<node> nodes;  // 所有节点

struct p_segment_tree {
  p_segment_tree() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  // 更新当前节点的出现次数
  void push_up(int64_t i) {
    nodes[i].size = nodes[nodes[i].left].size + nodes[nodes[i].right].size;
  }

  // 构建线段树, 返回根节点编号
  int64_t build(int64_t left, int64_t right) {
    int64_t i = nodes.size();    // 新节点编号
    nodes.emplace_back(node{});  // 创建新节点
    if (left == right) {         // 叶子节点
      nodes[i].size = 0;         // 初始化为0
      return i;
    }
    int64_t mid    = left + ((right - left) / 2);
    nodes[i].left  = build(left, mid);
    nodes[i].right = build(mid + 1, right);
    push_up(i);
    return i;
  }

  static int64_t clone(int64_t i) {
    int64_t new_node = nodes.size();  // 新节点编号
    nodes.emplace_back(nodes[i]);     // 克隆当前节点
    return new_node;
  }

  // 修改节点的值, 返回新版本的根节点
  int64_t update(int64_t index, int64_t i, int64_t l, int64_t r) {
    int64_t new_node = clone(i);  // 克隆当前节点
    if (l == r) {
      nodes[new_node].size += 1;
      return new_node;
    }
    int64_t mid = l + ((r - l) / 2);
    if (index <= mid) {
      nodes[new_node].left = update(index, nodes[i].left, l, mid);
    } else {
      nodes[new_node].right = update(index, nodes[i].right, mid + 1, r);
    }
    push_up(new_node);
    return new_node;
  }

  // 查询第k小元素, root_u为版本u的根节点, root_v为版本v的根节点
  int64_t query(int64_t k, int64_t root_u, int64_t root_v, int64_t l, int64_t r) {
    if (l == r) { return l; }
    int64_t mid = l + ((r - l) / 2);
    // 计算左子树中元素的数量
    int64_t left_count = nodes[nodes[root_v].left].size - nodes[nodes[root_u].left].size;
    // 如果k小于等于左子树中的元素数量, 则第k小元素在左子树中, 否则在右子树中
    if (k <= left_count) { return query(k, nodes[root_u].left, nodes[root_v].left, l, mid); }
    return query(k - left_count, nodes[root_u].right, nodes[root_v].right, mid + 1, r);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;

  nodes.reserve(70 * n + 20 * m);  // 经验值
  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  vector<int64_t> sorted_nums = nums;
  sort(sorted_nums.begin() + 1, sorted_nums.end());

  vector<int64_t> roots(n + 1);
  p_segment_tree seg;
  roots[0]      = seg.build(1, n);  // 构建初始版本0

  auto get_rank = [&](int64_t x) {  // 离散化, 映射到1~n
    return lower_bound(sorted_nums.begin() + 1, sorted_nums.end(), x) - sorted_nums.begin();
  };
  for (int64_t i = 1; i <= n; i++) {
    int64_t index = get_rank(nums[i]);  // 获得nums[i]的排名
    roots[i]      = seg.update(index, roots[i - 1], 1, n);
  }
  for (int64_t i = 0; i < m; i++) {
    int64_t l, r, k;
    cin >> l >> r >> k;
    int64_t index = seg.query(k, roots[l - 1], roots[r], 1, n);
    cout << sorted_nums[index] << "\n";  // 映射回原值
  }
  return 0;
}

Buratsuta 3

查询区间内所有出现次数超过三分之一（ $\lfloor \frac{r - l + 1}{3} \rfloor$ ）的元素。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct node {
  int64_t left;
  int64_t right;
  int64_t size;  // 记录该节点区间内有多少个元素
};

vector<node> nodes;

struct p_segment_tree {
  explicit p_segment_tree() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  // 更新当前节点的出现次数
  void push_up(int64_t i) {
    nodes[i].size = nodes[nodes[i].left].size + nodes[nodes[i].right].size;
  }

  // 构建0号版本的线段树, 没有任何元素
  int64_t build(int64_t left, int64_t right) {
    int64_t i = nodes.size();  // 新节点编号
    nodes.emplace_back(node{});
    if (left == right) { return i; }
    int64_t mid    = left + ((right - left) / 2);
    nodes[i].left  = build(left, mid);
    nodes[i].right = build(mid + 1, right);
    push_up(i);
    return i;
  }

  static int64_t clone(int64_t i) {
    int64_t new_node = nodes.size();  // 新节点编号
    nodes.emplace_back(nodes[i]);     // 克隆当前节点
    return new_node;
  }

  // 记录值出现一次, 返回新版本的根节点
  int64_t update(int64_t index, int64_t i, int64_t l, int64_t r) {
    int64_t new_node = clone(i);  // 克隆当前节点
    if (l == r) {                 // 叶子节点
      nodes[new_node].size += 1;  // 该节点出现次数加1
      return new_node;
    }
    int64_t mid = l + ((r - l) / 2);
    if (index <= mid) {
      nodes[new_node].left = update(index, nodes[i].left, l, mid);
    } else {
      nodes[new_node].right = update(index, nodes[i].right, mid + 1, r);
    }
    push_up(new_node);
    return new_node;
  }

  // 查询出现次数大于k的元素
  void query(int64_t k, int64_t root_u, int64_t root_v, int64_t l, int64_t r,
             vector<int64_t> &ans) {
    if (nodes[root_v].size - nodes[root_u].size <= k) { return; }  // 区间内元素总数不超过k
    if (l == r) {                                                  // 叶子节点, 出现次数大于k
      ans.push_back(l);
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    query(k, nodes[root_u].left, nodes[root_v].left, l, mid, ans);
    query(k, nodes[root_u].right, nodes[root_v].right, mid + 1, r, ans);
  }
};

int solve() {
  int64_t n, q;
  cin >> n >> q;
  nodes.reserve(n * 40);  // 预分配空间
  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  vector<int64_t> sorted_nums = nums;
  sort(sorted_nums.begin() + 1, sorted_nums.end());

  auto get_rank = [&](int64_t v) {  // 获取值的排名, 从1开始
    return lower_bound(sorted_nums.begin() + 1, sorted_nums.end(), v) - sorted_nums.begin();
  };

  vector<int64_t> roots(n + 1);
  p_segment_tree seg_tree;
  roots[0] = seg_tree.build(1, n);
  for (int64_t i = 1; i <= n; i++) {  // 构建每个版本的线段树, 记录前i个元素
    int64_t rank = get_rank(nums[i]);
    roots[i]     = seg_tree.update(rank, roots[i - 1], 1, n);
  }
  for (int64_t i = 0; i < q; i++) {
    int64_t l, r;
    cin >> l >> r;
    int64_t k = (r - l + 1) / 3;
    vector<int64_t> ans;
    seg_tree.query(k, roots[l - 1], roots[r], 1, n, ans);
    for (int64_t x : ans) { cout << sorted_nums[x] << " "; }
    if (ans.empty()) { cout << "-1"; }
    cout << "\n";
  }

  return 0;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t t = 1;
  cin >> t;
  while ((t--) != 0) { solve(); }
  return 0;
}

标记永久化⚓︎

标记永久化通过将更新操作的标记永久化，可以避免在查询时进行复杂的标记传播，从而提高查询效率。它本身不是持久化数据结构，但常作为范围修改可持久化线段树的实现技巧之一。

【模板】线段树 1

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

struct tag_p_tree {
  vector<int64_t> sum;      // 区间和
  vector<int64_t> tag_add;  // 加法标记

  explicit tag_p_tree(int64_t n) : sum(n * 4), tag_add(n * 4) {}

  void build(int64_t i, int64_t left, int64_t right, const vector<int64_t> &nums) {
    if (left == right) {  // 叶子节点，初始化为数组中对应值
      sum[i] = nums[left];
      return;
    }
    int64_t mid = left + ((right - left) / 2);
    build(2 * i, left, mid, nums);
    build(2 * i + 1, mid + 1, right, nums);
    // 根据子树更新
    sum[i] = sum[2 * i] + sum[2 * i + 1];
  }

  // 区间加法
  void range_add(int64_t ql, int64_t qr, int64_t val, int64_t i, int64_t l, int64_t r) {
    sum[i] += val * (min(qr, r) - max(ql, l) + 1);
    if (ql <= l && r <= qr) {  // 区间覆盖, 直接更新
      tag_add[i] += val;
      return;
    }
    int64_t mid = l + ((r - l) / 2);
    if (ql <= mid) { range_add(ql, qr, val, 2 * i, l, mid); }
    if (qr > mid) { range_add(ql, qr, val, 2 * i + 1, mid + 1, r); }
  }

  // 查询区间和
  int64_t range_sum(int64_t ql, int64_t qr, int64_t added, int64_t i, int64_t l, int64_t r) {
    // 区间覆盖，直接返回
    if (ql <= l && r <= qr) { return sum[i] + added * (r - l + 1); }
    int64_t mid = l + ((r - l) / 2);
    // 汇总结果
    int64_t res = 0;
    if (ql <= mid) { res += range_sum(ql, qr, added + tag_add[i], 2 * i, l, mid); }
    if (qr > mid) { res += range_sum(ql, qr, added + tag_add[i], 2 * i + 1, mid + 1, r); }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;
  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  tag_p_tree seg(n);
  seg.build(1, 1, n, nums);
  for (int64_t i = 0; i < m; i++) {
    int64_t op;
    cin >> op;
    if (op == 1) {
      int64_t l, r, val;
      cin >> l >> r >> val;
      seg.range_add(l, r, val, 1, 1, n);
    } else {
      int64_t l, r;
      cin >> l >> r;
      cout << seg.range_sum(l, r, 0, 1, 1, n) << '\n';
    }
  }
  return 0;
}

范围修改可持久⚓︎

范围修改可持久化线段树是一种结合了可持久化和范围更新的线段树数据结构，允许在进行范围更新操作时，保留之前的版本，从而可以随时访问和查询历史版本的数据。每次更新操作都会创建一个新的版本，而旧版本的数据仍然可以被访问。

TTM - To the moon

克隆标记标记永久化

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct node {
  int64_t left;
  int64_t right;
  int64_t sum;      // 区间和
  int64_t tag_add;  // 懒惰标记
};

vector<node> nodes;  // 所有节点

struct p_segment_tree {
  p_segment_tree() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  static void push_up(int64_t root) {
    nodes[root].sum = nodes[nodes[root].left].sum + nodes[nodes[root].right].sum;
  }

  // 构建0版本线段树, 返回根节点编号
  int64_t build(int64_t left, int64_t right, const vector<int64_t> &nums) {
    int64_t i = nodes.size();  // 新节点编号
    nodes.emplace_back(node{});   // 创建新节点
    if (left == right) {          // 叶子节点
      nodes[i].sum = nums[left];
      return i;
    }
    int64_t mid       = left + ((right - left) / 2);
    nodes[i].left  = build(left, mid, nums);
    nodes[i].right = build(mid + 1, right, nums);
    // 更新当前节点的区间和
    push_up(i);
    return i;
  }

  static void lazy_add(int64_t i, int64_t val, int64_t count) {
    nodes[i].sum     += count * val;
    nodes[i].tag_add += val;
  }

  static int64_t clone(int64_t i) {
    int64_t new_node = nodes.size();  // 新节点编号
    nodes.emplace_back(nodes[i]);     // 克隆当前节点
    return new_node;
  }

  // 向下传递懒惰标记
  static void push_down(int64_t i, int64_t left_count, int64_t right_count) {
    if (nodes[i].tag_add != 0) {               // 处理加法
      nodes[i].left  = clone(nodes[i].left);   // 克隆左子节点
      nodes[i].right = clone(nodes[i].right);  // 克隆右子节点
      // 子节点各自加上更新值
      lazy_add(nodes[i].left, nodes[i].tag_add, left_count);
      lazy_add(nodes[i].right, nodes[i].tag_add, right_count);
      nodes[i].tag_add = 0;  // 清空根节点加法标记
    }
  }

  int64_t range_add(int64_t ql, int64_t qr, int64_t val, int64_t i, int64_t l, int64_t r) {
    int64_t new_node = clone(i);
    if (ql <= l && r <= qr) {  // 区间覆盖
      lazy_add(new_node, val, r - l + 1);
      return new_node;
    }
    int64_t mid = l + ((r - l) / 2);
    push_down(new_node, mid - l + 1, r - mid);
    if (ql <= mid) { nodes[new_node].left = range_add(ql, qr, val, nodes[new_node].left, l, mid); }
    if (qr > mid) {
      nodes[new_node].right = range_add(ql, qr, val, nodes[new_node].right, mid + 1, r);
    }
    push_up(new_node);
    return new_node;
  }

  // 查询区间和
  int64_t range_sum(int64_t ql, int64_t qr, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) { return nodes[i].sum; }
    int64_t mid = l + ((r - l) / 2);
    push_down(i, mid - l + 1, r - mid);
    // 汇总结果
    int64_t res = 0;
    if (ql <= mid) { res += range_sum(ql, qr, nodes[i].left, l, mid); }
    if (qr > mid) { res += range_sum(ql, qr, nodes[i].right, mid + 1, r); }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;

  nodes.reserve(70 * n + 20 * m);  // 经验值
  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  p_segment_tree tree;

  vector<int64_t> roots(m + 1);  // 各个版本的根节点
  roots[0]  = tree.build(1, n, nums);
  int64_t t = 0;
  for (int64_t i = 0; i < m; i++) {
    string op;
    cin >> op;
    if (op == "C") {
      int64_t l, r, val;
      cin >> l >> r >> val;
      int64_t new_root = tree.range_add(l, r, val, roots[t], 1, n);
      roots[++t]       = new_root;
    } else if (op == "Q") {
      int64_t l, r;
      cin >> l >> r;
      cout << tree.range_sum(l, r, roots[t], 1, n) << "\n";
    } else if (op == "H") {
      int64_t l, r, version;
      cin >> l >> r >> version;
      cout << tree.range_sum(l, r, roots[version], 1, n) << "\n";
    } else {  // op == "B"
      int64_t version;
      cin >> version;
      t = version;
    }
  }
  return 0;
}

Tip

通过标记永久化可以减少范围修改可持久线段树的占用空间，因为每次更新只需要克隆受影响的节点，而不需要克隆整个路径上的所有节点，从而节省了空间。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct node {
  int64_t left;
  int64_t right;
  int64_t sum;      // 区间和
  int64_t tag_add;  // 懒惰标记
};

vector<node> nodes;  // 所有节点

struct tag_p_segment_tree {
  tag_p_segment_tree() {
    nodes.clear();               // 清空节点
    nodes.emplace_back(node{});  // 占位, 节点编号从1开始
  }

  // 构建0版本线段树, 返回根节点编号
  int64_t build(int64_t left, int64_t right, const vector<int64_t> &nums) {
    int64_t root = nodes.size();  // 新节点编号
    nodes.emplace_back(node{});   // 创建新节点
    if (left == right) {          // 叶子节点
      nodes[root].sum = nums[left];
      return root;
    }
    int64_t mid       = left + ((right - left) / 2);
    nodes[root].left  = build(left, mid, nums);
    nodes[root].right = build(mid + 1, right, nums);
    nodes[root].sum   = nodes[nodes[root].left].sum + nodes[nodes[root].right].sum;
    return root;
  }

  static int64_t clone(int64_t i) {
    int64_t new_root = nodes.size();  // 新节点编号
    nodes.push_back(nodes[i]);        // 克隆当前节点
    return new_root;
  }

  int64_t range_add(int64_t ql, int64_t qr, int64_t val, int64_t i, int64_t l, int64_t r) {
    int64_t new_node     = clone(i);
    nodes[new_node].sum += val * (min(qr, r) - max(ql, l) + 1);
    if (ql <= l && r <= qr) {  // 区间覆盖
      nodes[new_node].tag_add += val;
      return new_node;
    }
    int64_t mid = l + ((r - l) / 2);
    if (ql <= mid) { nodes[new_node].left = range_add(ql, qr, val, nodes[new_node].left, l, mid); }
    if (qr > mid) {
      nodes[new_node].right = range_add(ql, qr, val, nodes[new_node].right, mid + 1, r);
    }
    return new_node;
  }

  // 查询区间和, total_add为从根节点到当前节点路径上所有懒惰标记的和
  int64_t range_sum(int64_t ql, int64_t qr, int64_t added, int64_t i, int64_t l, int64_t r) {
    if (ql <= l && r <= qr) { return nodes[i].sum + added * (r - l + 1); }
    int64_t mid = l + ((r - l) / 2);
    // 汇总结果
    int64_t res = 0;
    if (ql <= mid) {
      res += range_sum(ql, qr, added + nodes[i].tag_add, nodes[i].left, l, mid);
    }
    if (qr > mid) {
      res += range_sum(ql, qr, added + nodes[i].tag_add, nodes[i].right, mid + 1, r);
    }
    return res;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int64_t n, m;
  cin >> n >> m;

  nodes.reserve(70 * n + 20 * m);  // 经验值
  vector<int64_t> nums(n + 1);
  for (int64_t i = 1; i <= n; i++) { cin >> nums[i]; }
  tag_p_segment_tree tree;

  vector<int64_t> roots(m + 1);  // 各个版本的根节点
  roots[0]  = tree.build(1, n, nums);
  int64_t t = 0;
  for (int64_t i = 0; i < m; i++) {
    string op;
    cin >> op;
    if (op == "C") {
      int64_t l, r, val;
      cin >> l >> r >> val;
      int64_t new_root = tree.range_add(l, r, val, roots[t], 1, n);
      roots[++t]       = new_root;
    } else if (op == "Q") {
      int64_t l, r;
      cin >> l >> r;
      cout << tree.range_sum(l, r, 0, roots[t], 1, n) << "\n";
    } else if (op == "H") {
      int64_t l, r, version;
      cin >> l >> r >> version;
      cout << tree.range_sum(l, r, 0, roots[version], 1, n) << "\n";
    } else {  // op == "B"
      int64_t version;
      cin >> version;
      t = version;
    }
  }
  return 0;
}