首页 > 其他分享 >重链剖分学习笔记

重链剖分学习笔记

时间：2022-12-13 21:00:13浏览次数：73  
标签：剖分 fa int top 笔记 seg dep dfn 重链

最近在机房自习复习了一下这些东西，主要给自己看的。
参考文献：

  • OI Wiki

  • 《算法竞赛》（罗勇军，郭卫斌 著）

1 重链剖分简介

1.1 重链剖分基本性质

树链剖分，就是把树分成若干条链，然后通过这些链来进行各种操作。同时树链剖分分为重链剖分和长链剖分，一般情况下，我们所说的树链剖分就是重链剖分。

重链的定义：

  • 一个节点子树大小最大的点被称为这个节点的重子节点（又名重儿子，可能不存在），这个点到它重子节点的边被称之为重边。

  • 若干个首尾相连的重边就是重链。

  • 不是重子节点的点就是轻子节点，不是重边就是轻边。

重链的性质：

  • 是一条链，且链中所有点的 LCA 是深度最浅的那个端点。也就是链上的点深度互不相同。

  • 一棵树的链不超过 \(O(\log\ n)\) 条。

  • 每一个点都在且仅在一条重链当中（也就是说，单独一个点也可以是一条重链）。

想要写出完整的重链剖分，你需要维护以下东西：

  • \(siz(x),son(x),fa(x),dep(x)\)，分别表示当前节点的子树大小，重儿子是谁，以及父亲节点是谁，其深度。

  • \(top(x)\) 其所在重链为的深度最浅的节点。

  • \(dfn(x),rnk(x)\)，分别表示 \(x\) 号点在重子节点优先遍历中的搜索序和搜索序为 \(x\) 的节点是谁。

例如以下就是一个合法重链剖分方案：

1.2 实现重链剖分

int n, son[N], dfn[N], rnk[N], top[N], siz[N], dep[N], fa[N], idx;

void dfs1(int x, int f) { // 维护 siz(x),dep(x),fa(x),son(x)。
  siz[x] = 1, dep[x] = dep[f] + 1, fa[x] = f;
  son[x] = -1;
  for (int i : v[x]) {
    if (i == f) {
      continue;
    }
    dfs1(i, x);
    siz[x] += siz[i];
    if (son[x] == -1 || siz[i] > siz[son[x]]) {
      son[x] = i;
    }
  }
}

void dfs2(int x, int tp) { // 实现重链剖分。
  top[x] = tp;
  dfn[x] = ++idx, rnk[idx] = x;
  if (son[x] == -1) {
    return;
  }
  dfs2(son[x], tp); // 优先便利重子节点，这样才能保证重链的连续性。
  for (int i : v[x]) {
    if (i == fa[x] || i == son[x]) {
      continue;
    }
    dfs2(i, i);
  }
}

2 重链剖分的常见应用

2.1 最近公共祖先

对于两个点，不断跳到这一条重链之上，当两点位于同一条重链时，深度小者为两点最近公共祖先。

时间复杂度 \(O(\log\ n)\)，常数较优。

int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      x = fa[top[x]];
    } else {
      y = fa[top[y]];
    }
  }
  return dep[x] < dep[y] ? x : y;
}

2.2 维护两点间路径权值和（查询+修改）

首先，我们都知道一条重链中，他们的 \(dfn\) 是连续的，因此我们可以用一些数据结构来维护（包括但不限于线段树、树状数组…）。对于，我们每次将深度大的点往上跳，并加上当前链的权值和。对于修改也是大同小异，具体看代码。

时间复杂度为 \(O((\log\ n)^2)\)，常数较优。

// seg 是线段树所在结构体的部分，读者请自行实现支持区间查询、区间修改的数据结构。
void modify_add(int x, int y, int z) { // 修改操作。
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      seg.modify(1, z, dfn[top[x]], dfn[x]); // 将 [dfn[top[x]], top[x]] 加上 z。
      x = fa[top[x]];
    } else {
      seg.modify(1, z, dfn[top[y]], dfn[y]);
      y = fa[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    seg.modify(1, z, dfn[x], dfn[y]);
  } else {
    seg.modify(1, z, dfn[y], dfn[x]);
  }
}

int query_sum(int x, int y) { // 查询部分。
  int res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      (res += seg.query(1, dfn[top[x]], dfn[x])) %= p; // 查询 [dfn[top[x]], dfn[x]] 的权值和。
      x = fa[top[x]];
    } else {
      (res += seg.query(1, dfn[top[y]], dfn[y])) %= p;
      y = fa[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    (res += seg.query(1, dfn[x], dfn[y])) %= p;
  } else {
    (res += seg.query(1, dfn[y], dfn[x])) %= p;
  }
  return res;
}

其实按照同样的方法可以实现求极值，读者可以尝试自行实现。（参考 洛谷 P2590 [ZJOI2008]树的统计）

2.3 维护某点子树权值（查询+修改）

不难发现，一个以 \(x\) 为根的子树内的 \(dfn\) 也是连续的，并且其值是 \(dfn(x)\) 到 \(dfn(x)+siz(x)-1\)。

时间复杂度 \(O(\log\ n)\)。

seg.modify(1, z, dfn[x], dfn[x] + siz[x] - 1); // 修改。
seg.query(1, dfn[x], dfn[x] + siz[x] - 1) % p; // 查询。

2.4 其它的东西

讲些实践中的细节。

  • 对于维护的是边权而非点权，可以先将边权下传成为点权。但是注意，操作间点的 LCA 的权值需要无视。（参考 洛谷 P3038 [USACO11DEC]Grass Planting G）

  • 注意修改 \(x\) 的子树是 \(dfn(x)\)（线段树上改），修改两点间的距离就是 \(x,y\)（直接在树上改）。

3 习题

3.1 习题1

洛谷 P3384 【模板】轻重链剖分/树链剖分

题目大意：

已知一棵包含 \(N\) 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

  • 1 x y z，表示将树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值都加上 \(z\)。

  • 2 x y，表示求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和。

  • 3 x z，表示将以 \(x\) 为根节点的子树内所有节点值都加上 \(z\)。

  • 4 x 表示求以 \(x\) 为根节点的子树内所有节点值之和

思路：

没什么好解释的，写个线段树再将前文所示的代码缝合一下即可。

参考代码（部分）：

const int N = 1e5 + 5;
int n, m, s, p, w[N], son[N], dfn[N], rnk[N], top[N], siz[N], dep[N], fa[N], idx;
vector<int> v[N];
struct SegmentTree { // 线段树模板，不解释。
  struct Tree {
    int l, r, x, add;
  } tr[N << 2];
  void pushup(int u) {
    tr[u].x = tr[u << 1].x + tr[u << 1 | 1].x;
  }
  void pushdown(int u) {
    Tree &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
      (left.add += root.add) %= p;
      (left.x += (left.r - left.l + 1) * root.add) %= p;
      (right.add += root.add) %= p;
      (right.x += (right.r - right.l + 1) * root.add) %= p;
      root.add = 0;
    }
  }
  void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].add = 0;
    if (l == r) {
      tr[u].x = w[rnk[l]];
      return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
  int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].x;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1, res = 0;
    if (mid >= l) (res += query(u << 1, l, r)) %= p;
    if (mid < r) (res += query(u << 1 | 1, l, r)) %= p;
    return res;
  }
  void modify(int u, int d, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
      (tr[u].x += (tr[u].r - tr[u].l + 1) * d) %= p;
      (tr[u].add += d) %= p;
    } else {
      pushdown(u);
      int mid = tr[u].l + tr[u].r >> 1;
      if (l <= mid) modify(u << 1, d, l, r);
      if (r > mid) modify(u << 1 | 1, d, l, r);
      pushup(u);
    }
  }
} seg;

void dfs1(int x, int f) { // 树链剖分预处理部分。
  siz[x] = 1, dep[x] = dep[f] + 1, fa[x] = f;
  son[x] = -1;
  for (int i : v[x]) {
    if (i == f) continue;
    dfs1(i, x);
    siz[x] += siz[i];
    if (son[x] == -1 || siz[i] > siz[son[x]]) son[x] = i;
  }
}

void dfs2(int x, int tp) {
  top[x] = tp;
  dfn[x] = ++idx, rnk[idx] = x;
  if (son[x] == -1) return;
  dfs2(son[x], tp);
  for (int i : v[x]) {
    if (i == fa[x] || i == son[x]) continue;
    dfs2(i, i);
  }
}

void modify_add(int x, int y, int z) { // 实现修改权值。
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      seg.modify(1, z, dfn[top[x]], dfn[x]);
      x = fa[top[x]];
    } else {
      seg.modify(1, z, dfn[top[y]], dfn[y]);
      y = fa[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    seg.modify(1, z, dfn[x], dfn[y]);
  } else {
    seg.modify(1, z, dfn[y], dfn[x]);
  }
}

int query_sum(int x, int y) { // 实现查询。
  int res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      (res += seg.query(1, dfn[top[x]], dfn[x])) %= p;
      x = fa[top[x]];
    } else {
      (res += seg.query(1, dfn[top[y]], dfn[y])) %= p;
      y = fa[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    (res += seg.query(1, dfn[x], dfn[y])) %= p;
  } else {
    (res += seg.query(1, dfn[y], dfn[x])) %= p;
  }
  return res;
}

signed main() {
  read(n, m, s, p);
  for (int i = 1; i <= n; i++) {
    read(w[i]);
  }
  for (int i = 1, x, y; i < n; i++) {
    read(x, y);
    v[x].pb(y), v[y].pb(x);
  }
  dfs1(s, N - 1);
  dfs2(s, s);
  seg.build(1, 1, n);
  while (m--) {
    int op, x, y, z;
    read(op);
    if (op == 1) {
      read(x, y, z);
      modify_add(x, y, z);
    } else if (op == 2) {
      read(x, y);
      printl(query_sum(x, y) % p);
    } else if (op == 3) {
      read(x, z);
      seg.modify(1, z, dfn[x], dfn[x] + siz[x] - 1);
    } else {
      read(x);
      printl(seg.query(1, dfn[x], dfn[x] + siz[x] - 1) % p);
    }
  }
  return 0;
}

3.2 习题2

洛谷 P2146 [NOI2015] 软件包管理器

题目大意：

给定一个树形结构，初始所有节点权值都为 0。接下来进行若干次操作，若将 \(x\) 值改为 1，则需要将根至 \(x\) 的权值都改为 1。若改为 0，则其子树都将变为 0。求问每次操作会有多少个点权值发生变化。

思路：

还是模板，记录一下原来的权值，再与修改之后的权值对比即可。

参考代码（部分）：

const int N = 1e5 + 5, p = 1e9 + 7;
int n, m, son[N], dfn[N], rnk[N], top[N], siz[N], dep[N], fa[N], idx;
vector<int> v[N];
struct SegmentTree {
  struct Tree {
    int l, r, x, add;
  } tr[N << 2];
  void pushup(int u) {
    tr[u].x = tr[u << 1].x + tr[u << 1 | 1].x;
  }
  void pushdown(int u) {
    Tree &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (~root.add) {
      (left.add = root.add) %= p;
      (left.x = (left.r - left.l + 1) * root.add) %= p;
      (right.add = root.add) %= p;
      (right.x = (right.r - right.l + 1) * root.add) %= p;
      root.add = -1;
    }
  }
  void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r, tr[u].add = 0;
    if (l == r) {
      tr[u].x = 0;
      return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }
  int query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].x;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1, res = 0;
    if (mid >= l) (res += query(u << 1, l, r)) %= p;
    if (mid < r) (res += query(u << 1 | 1, l, r)) %= p;
    return res;
  }
  void modify(int u, int d, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) {
      (tr[u].x = (tr[u].r - tr[u].l + 1) * d) %= p;
      (tr[u].add = d) %= p;
    } else {
      pushdown(u);
      int mid = tr[u].l + tr[u].r >> 1;
      if (l <= mid) modify(u << 1, d, l, r);
      if (r > mid) modify(u << 1 | 1, d, l, r);
      pushup(u);
    }
  }
} seg;
void dfs1(int x, int f) {
  siz[x] = 1, dep[x] = dep[f] + 1, fa[x] = f;
  son[x] = -1;
  for (int i : v[x]) {
    if (i == f) continue;
    dfs1(i, x);
    siz[x] += siz[i];
    if (son[x] == -1 || siz[i] > siz[son[x]]) son[x] = i;
  }
}
void dfs2(int x, int tp) {
  top[x] = tp;
  dfn[x] = ++idx, rnk[idx] = x;
  if (son[x] == -1) return;
  dfs2(son[x], tp);
  for (int i : v[x]) {
    if (i == fa[x] || i == son[x]) continue;
    dfs2(i, i);
  }
}
void modify_set(int x, int y, int z) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      seg.modify(1, z, dfn[top[x]], dfn[x]);
      x = fa[top[x]];
    } else {
      seg.modify(1, z, dfn[top[y]], dfn[y]);
      y = fa[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    seg.modify(1, z, dfn[x], dfn[y]);
  } else {
    seg.modify(1, z, dfn[y], dfn[x]);
  }
}
int query_sum(int x, int y) {
  int res = 0;
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]]) {
      (res += seg.query(1, dfn[top[x]], dfn[x])) %= p;
      x = fa[top[x]];
    } else {
      (res += seg.query(1, dfn[top[y]], dfn[y])) %= p;
      y = fa[top[y]];
    }
  }
  if (dep[x] < dep[y]) {
    (res += seg.query(1, dfn[x], dfn[y])) %= p;
  } else {
    (res += seg.query(1, dfn[y], dfn[x])) %= p;
  }
  return res;
}
signed main() {
  read(n);
  for (int i = 1, x; i < n; i++) {
    read(x);
    v[i + 1].pb(x + 1), v[x + 1].pb(i + 1);
  }
  dfs1(1, N - 1);
  dfs2(1, 1);
  seg.build(1, 1, n + 1);
  read(m);
  while (m--) {
    string s;
    int x;
    read(s), read(x);
    if (s[0] == 'i') {
      int oldsum = query_sum(1, x + 1);
      modify_set(1, x + 1, 1);
      printl(query_sum(1, x + 1) - oldsum);
    } else {
      int oldsum = seg.query(1, dfn[x + 1], dfn[x + 1] + siz[x + 1] - 1);
      seg.modify(1, 0, dfn[x + 1], dfn[x + 1] + siz[x + 1] - 1);
      printl(oldsum);
    }
  }
  return 0;
}

3.3 其它习题

洛谷 P3178 [HAOI2015]树上操作

无所谓，反正我认为是双倍经验。

洛谷 P3258 [JLOI2014]松鼠的新家

尝试使用树剖实现。

洛谷 P2486 [SDOI2011]染色

相比于模板要多维护几个值域，转换有一定思维难度。

洛谷 P4592 [TJOI2018]异或

The End

树剖感觉和线段树离不开，玩来玩去核心思路还是不变的。有问题请指出，谢谢。

Thanks

暂无

标签：剖分,fa,int,top,笔记,seg,dep,dfn,重链
From： https://www.cnblogs.com/Pretharp/p/16980612.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99