线段树分治⚓︎

线段树分治是一种结合了线段树和分治思想的数据结构与算法设计方法。

对于一些动态修改和查询的问题，传统的数据结构可能无法高效处理频繁的修改操作。而线段树分治通过将时间维度引入线段树结构中，实现对动态操作的高效管理。

解决问题时，可以把每条操作分配一个时间点，建立时间轴线段树。每种修改操作，拥有若干个有效时间段，对应着线段树上的若干区间。每条查询操作对应在某个时间点上相关的状态信息。

线段树分治的过程：

先把所有操作记录分类，每种修改操作整理出若干个有效时间段
根据每个有效时间段，把任务分配到线段树的区间上
遍历整棵线段树，来到某个线段树的区间时执行相应的任务，离开区间时撤销相应的任务
线段树的叶节点对应着单个时间点，如果有查询操作需要记录查询的答案

这种"加操作-递归-撤销操作"结构使得数据结构只需支持「增量修改 + 撤销」，不需要真正的可持久化结构。所有修改都是"分治有效"的。

线段树分治用于处理带撤销操作的动态问题，通常是：

在线上加入/删除操作
查询只依赖于当前已加入的操作
无法直接使用可持久化结构
查询可以离线化（提前知道所有操作和查询）

线段树分治的时间复杂度：

操作的数量为 $m$ ，每个有效时间段会分解成 $\log m$ 个线段树的区间
每个线段树区间都留有这个操作的任务，那么任务总数为 $m * \log m$
执行任务和撤销任务时，常见做法是使用可撤销并查集；其单次操作代价取决于具体实现，通常可视为近似常数或按不带路径压缩的并查集复杂度分析

因此总复杂度通常写作 $O(m \log m \cdot T)$ ，其中 $T$ 为底层可撤销数据结构的单次操作代价；若使用常见的可撤销并查集，通常可近似看作 $O(m \log m)$ 。

动态图连通性

维护一张无向简单图。你被要求加入删除一条边及查询两个点是否连通。

0：加入一条边。保证它不存在。 1：删除一条边。保证它存在。 2：查询两个点是否连通。

Hint

建立时间轴线段树，使用可撤销并查集维护连通性。建立线段树时按边和时间排序，方便统计每条边的有效时间段。

C++

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

struct query {
  int64_t u, v, t, op;

  query() : u(0), v(0), t(0), op(0) {}

  query(int64_t _u, int64_t _v, int64_t _t, int64_t _op) : u(_u), v(_v), t(_t), op(_op) {}

  // 按边与时间排序
  bool operator<(const query &other) const {
    if (u != other.u) { return u < other.u; }
    if (v != other.v) { return v < other.v; }
    return t < other.t;
  }

  // 根据u和v判断是否为同一条边
  bool operator==(const query &other) const { return u == other.u && v == other.v; }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int64_t n, m;
  cin >> n >> m;

  vector<query> queries(m + 1);
  for (int64_t i = 1; i <= m; ++i) {
    int64_t op, u, v;
    cin >> op >> u >> v;
    queries[i] = {min(u, v), max(u, v), i, op};
  }

  // 根据时间轴建立线段树
  vector<vector<pair<int64_t, int64_t>>> interval(4 * m);
  auto add = [&](auto &self, int64_t ql, int64_t qr, int64_t qx, int64_t qy, int64_t i, int64_t l,
                 int64_t r) -> void {
    if (ql <= l && r <= qr) {
      interval[i].emplace_back(qx, qy);
      return;
    }
    int64_t mid = (l + r) >> 1;
    if (ql <= mid) { self(self, ql, qr, qx, qy, 2 * i, l, mid); }
    if (qr > mid) { self(self, ql, qr, qx, qy, 2 * i + 1, mid + 1, r); }
  };
  // 处理所有边的添加和删除操作，构建线段树
  vector<int64_t> index(m + 1, 0);
  iota(index.begin(), index.end(), 0);
  sort(index.begin() + 1, index.end(),
       [&](int64_t a, int64_t b) { return queries[a] < queries[b]; });
  for (int64_t i = 1, j = 1; i <= m; i = j) {
    int64_t u = queries[index[i]].u, v = queries[index[i]].v;
    while (j <= m && queries[index[i]] == queries[index[j]]) { ++j; }  // 按边分组
    int64_t last_add = 0;
    for (int64_t k = i; k < j; ++k) {
      if (queries[index[k]].op == 0) {  // 添加边
        last_add = k;
      }
      if (queries[index[k]].op == 1) {  // 删除边
        int64_t start = queries[index[last_add]].t;
        int64_t end   = queries[index[k]].t - 1;
        add(add, start, end, u, v, 1, 1, m);
        last_add = 0;
      }
    }
    if (last_add != 0) {  // 最后一条添加的边没有被删除, 则一直持续到最后
      int64_t start = queries[index[last_add]].t;
      int64_t end   = m;
      add(add, start, end, u, v, 1, 1, m);
    }
  }
  // 并查集，支持回滚
  vector<int64_t> root(n + 1);
  vector<int64_t> size(n + 1, 1);
  vector<pair<int64_t, int64_t>> rollback;
  iota(root.begin(), root.end(), 0);
  auto find = [&](int64_t x) {
    while (root[x] != x) { x = root[x]; }
    return x;
  };
  auto union_set = [&](int64_t x, int64_t y) {
    int64_t fx = find(x);
    int64_t fy = find(y);
    if (fx == fy) { return 0; }
    if (size[fx] < size[fy]) { swap(fx, fy); }
    root[fy]  = fx;
    size[fx] += size[fy];
    rollback.emplace_back(fy, fx);
    return 1;
  };
  auto union_rollback = [&]() {
    if (rollback.empty()) { return; }
    auto [fy, fx] = rollback.back();
    rollback.pop_back();
    root[fy]  = fy;
    size[fx] -= size[fy];
  };

  // 深度优先遍历线段树，处理每个时间点的查询
  vector<bool> results(m + 1);  // 存储查询结果
  auto dfs = [&](auto &self, int64_t i, int64_t l, int64_t r) -> void {
    int64_t union_count = 0;
    // 添加当前区间的所有边
    for (auto &[u, v] : interval[i]) { union_count += union_set(u, v); }
    if (l == r) {
      if (queries[l].op == 2) {  // 处理查询操作
        int64_t u  = queries[l].u;
        int64_t v  = queries[l].v;
        results[l] = (find(u) == find(v));
      }
    } else {
      int64_t mid = (l + r) >> 1;
      self(self, 2 * i, l, mid);
      self(self, 2 * i + 1, mid + 1, r);
    }
    // 回滚到之前的状态
    for (int64_t k = 0; k < union_count; ++k) { union_rollback(); }
  };
  dfs(dfs, 1, 1, m);
  for (int64_t i = 1; i <= m; ++i) {
    if (queries[i].op == 2) { cout << (results[i] ? "Y" : "N") << "\n"; }
  }
  return 0;
}

最小mex生成树

给定一个带权无向图，边的权值为非负整数。定义一棵生成树的 $\text{MEX}$ 为不在生成树边权值中的最小非负整数。求所有生成树中 $\text{MEX}$ 最小的生成树对应的 $\text{MEX}$ 值。

Hint

在 $\text{MEX}$ 为 $w$ 的生成树中，边的权值不能为 $w$ 。因此可以将权值为 $w$ 的边，添加到权值轴线段树上，区间为 $[0, w-1]$ 和 $[w+1, \text{max\_w} + 1]$ 。使用可撤销并查集维护连通性，查询时判断是否连通。

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m;
  cin >> n >> m;

  using TIII = tuple<int, int, int>;

  vector<TIII> queries(m + 1);
  int max_w = 0;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    queries[i] = {u, v, w};
    max_w      = max(max_w, w);
  }
  max_w++;  // 有可能所有从0到max_w的权值都存在, 结果为 max_w+1

  // 根据权值轴建立线段树
  vector<vector<pair<int, int>>> interval(4 * max_w);
  auto add = [&](auto &self, int ql, int qr, int qx, int qy, int i, int l, int r) -> void {
    if (ql <= l && r <= qr) {
      interval[i].emplace_back(qx, qy);
      return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) { self(self, ql, qr, qx, qy, 2 * i, l, mid); }
    if (qr > mid) { self(self, ql, qr, qx, qy, 2 * i + 1, mid + 1, r); }
  };
  // 权值为w的边，在[0, w-1]和[w+1, max_w]区间内存在
  for (auto [u, v, w] : queries) {
    if (w > 0) { add(add, 0, w - 1, u, v, 1, 0, max_w); }
    add(add, w + 1, max_w, u, v, 1, 0, max_w);
  }
  // 并查集，支持回滚
  int part = n;  // 连通块数量
  vector<int> root(n + 1);
  vector<int> size(n + 1, 1);
  vector<pair<int, int>> rollback;
  iota(root.begin(), root.end(), 0);
  auto find = [&](int x) {
    while (root[x] != x) { x = root[x]; }
    return x;
  };
  auto union_set = [&](int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) { return 0; }
    if (size[fx] < size[fy]) { swap(fx, fy); }
    root[fy]  = fx;
    size[fx] += size[fy];
    rollback.emplace_back(fy, fx);
    part--;  // 连通块数量减少
    return 1;
  };
  auto union_rollback = [&]() {
    if (rollback.empty()) { return; }
    auto [fy, fx] = rollback.back();
    rollback.pop_back();
    root[fy]  = fy;
    size[fx] -= size[fy];
    part++;  // 连通块数量增加
  };

  auto dfs = [&](auto &self, int i, int l, int r) -> int {
    int union_count = 0;
    for (auto &[u, v] : interval[i]) { union_count += union_set(u, v); }
    int res = -1;
    if (l == r) {
      if (part == 1) { res = l; } // 连通块数量为1，形成一棵生成树
    } else {
      int mid = (l + r) >> 1;
      res     = self(self, 2 * i, l, mid); // 先搜索左子树, 如果没找到再搜索右子树
      if (res == -1) { res = self(self, 2 * i + 1, mid + 1, r); }
    }
    for (int k = 0; k < union_count; ++k) { union_rollback(); }
    return res;
  };
  cout << dfs(dfs, 1, 0, max_w) << "\n";

  return 0;
}

线段树分治⚓︎

评论