全局平衡二叉樹

引入

前置知識：樹鏈剖分

由於樹鏈剖分的時間複雜度為 \(O(n\log^2 n)\)，而我們熟知的 LCT 雖然時間複雜度為 \(O(n\log n)\)，但常數較大，可能比樹鏈剖分還慢。那麼有什麼既是 \(O(n\log n)\) 的，常數又相對較小的方法呢？這個時候全局平衡二叉樹就出現了。

全局平衡二叉樹實際上是一顆二叉樹森林，其中的每顆二叉樹維護一條重鏈。但是這個森林裏的二叉樹又互有聯繫，其中每個二叉樹的根連向這個重鏈鏈頭的父親，就像 LCT 中一樣。但全局平衡二叉樹是靜態樹，區別於 LCT，建成後樹的形態不變。

全局平衡二叉樹是一種可以處理樹上鍊修改/查詢的數據結構，可以做到：

• \(O(\log n)\) 一條鏈整體修改。
• \(O(\log n)\) 一條鏈整體查詢。
• \(O(\log n)\) 求最近公共祖先，子樹修改，子樹查詢等，這些複雜度和重鏈剖分是一樣的。

主要性質

1. 全局平衡二叉樹由很多棵二叉樹通過輕邊連起來組成，每一棵二叉樹維護了原樹的一條重鏈，其中序遍歷的順序就是這條重鏈深度單調遞增的順序。每個節點都僅出現在一棵二叉樹中。
2. 邊分為重邊和輕邊，重邊是包含在二叉樹中的邊，維護的時候就像正常維護二叉樹一樣，記錄左右兒子和父節點。輕邊從一顆二叉樹的根節點指向它所對應的重鏈頂端節點的父節點。輕邊維護的時候 "認父不認子"，即只能從子節點訪問到父節點，不能反過來。注意，全局平衡二叉樹中的邊和原樹中的邊沒有對應關係。
3. 算上重邊和輕邊，全局平衡二叉樹的高度是 \(O(\log n)\) 級別的。這條是保證全局平衡二叉樹時間複雜度的性質。

下面是一個全局平衡二叉樹建樹的例子。第一張圖是原樹，以節點 1 為根節點。實線是重邊。

第二張圖是建出來的全局平衡二叉樹，其中虛線是輕邊，實線是重邊，每一棵二叉樹用紅圈表示。

建樹

首先是像普通重鏈剖分一樣，一次 DFS 求出每個節點的重兒子。然後從根開始，找到根節點所在的重鏈，對於這些點的輕兒子遞歸建樹，並連上輕邊。然後我們需要給重鏈上的點建一棵二叉樹。我們先把重鏈上的點存到數組裏，求出每個點輕兒子的子樹大小之和加一（即該點本身所貢獻的 size）。然後我們按照這個求出這條重鏈的加權中點，把它作為二叉樹的根，兩邊遞歸建樹，並連上重邊。

代碼如下：

實現

std::vector<int> G[N];
int n, fa[N], son[N], sz[N];

void dfsS(int u) {
  sz[u] = 1;
  for (int v : G[u]) {
    dfsS(v);
    sz[u] += sz[v];
    if (sz[v] > sz[son[u]]) son[u] = v;
  }
}

int b[N], bs[N], l[N], r[N], f[N], ss[N];

// 給b中[bl,br)內的點建二叉樹，返回二叉樹的根
int cbuild(int bl, int br) {
  int x = bl, y = br;
  while (y - x > 1) {
    int mid = (x + y) >> 1;
    if (2 * (bs[mid] - bs[bl]) <= bs[br] - bs[bl])
      x = mid;
    else
      y = mid;
  }
  // 二分求出按bs加權的中點
  y = b[x];
  ss[y] = br - bl;  // ss：二叉樹中重子樹的大小
  if (bl < x) {
    l[y] = cbuild(bl, x);
    f[l[y]] = y;
  }
  if (x + 1 < br) {
    r[y] = cbuild(x + 1, br);
    f[r[y]] = y;
  }
  return y;
}

int build(int x) {
  int y = x;
  do
    for (int v : G[y])
      if (v != son[y])
        f[build(v)] =
            y;  // 遞歸建樹並連輕邊，注意要從二叉樹的根連邊，不是從兒子連邊
  while (y = son[y]);
  y = 0;
  do {
    b[y++] = x;                              // 存放重鏈中的點
    bs[y] = bs[y - 1] + sz[x] - sz[son[x]];  // bs：輕兒子size和+1，求前綴和
  } while (x = son[x]);
  return cbuild(0, y);
}

由代碼可以看出建樹的時間複雜度是 \(O(n\log n)\)。接下來我們可以證明樹高是 \(O(\log n)\) 的：考慮從任意一個點跳父節點到根。跳輕邊就相當於在原樹中跳到另一條重鏈，由重鏈剖分的性質可得跳輕邊最多 \(O(\log n)\) 條；因為建二叉樹的時候根節點找的是算輕兒子的加權中點，那麼跳一次重邊算上輕兒子的 size 至少翻倍，所以跳重邊最多也是 \(O(\log n)\) 條。整體樹高就是 \(O(\log n)\) 的。

查詢

以上就是關於全局平衡二叉樹的部分。剩下關於鏈修改和鏈查詢的操作方法相對簡單，只需要從要操作的點出發，一直跳躍到根節點。要操作某個點所在的重鏈上比它深度小的所有點，本質上等同於在這條重鏈的二叉樹中操作目標節點左側的所有節點。這些操作可以分解成一系列子樹操作，與普通二叉樹的維護方法類似，其中涉及到維護子樹和以及打子樹標記。在這一過程中，使用的是標記永久化。也可以用 pushdown 來打標記，用 pushup 維護子樹和，不過這種方式可能相對複雜，因為通常情況下，處理二叉樹是自上而下進行操作，但在這裏，需要首先確定跳躍路徑，然後再從上到下進行 pushdown，可能導致常數較大。

代碼如下：

實現

// a：子樹加標記
// s：子樹和（不算加標記的）
int a[N], s[N];

void add(int x) {
  bool t = true;
  int z = 0;
  while (x) {
    s[x] += z;
    if (t) {
      a[x]++;
      if (r[x]) a[r[x]]--;
      z += 1 + ss[l[x]];
      s[x] -= ss[r[x]];
    }
    t = (x != l[f[x]]);
    if (t && x != r[f[x]]) z = 0;  // 跳過輕邊要清空
    x = f[x];
  }
}

int query(int x) {
  int ret = 0;
  bool t = true;
  int z = 0;
  while (x) {
    if (t) {
      ret += s[x] - s[r[x]];
      ret -= 1ll * ss[r[x]] * a[r[x]];
      z += 1 + ss[l[x]];
    }
    ret += 1ll * z * a[x];
    t = (x != l[f[x]]);
    if (t && x != r[f[x]]) z = 0;  // 跳過輕邊要清空
    x = f[x];
  }
  return ret;
}

此外，對於子樹操作，就是要考慮輕兒子的，需要再維護一個包括輕兒子的子樹和、子樹標記，可以去做 "P3384【模板】輕重鏈剖分"。

例題

P4751【模板】"動態 DP"& 動態樹分治（加強版）

#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 1000000
#define MAXM 3000000
#define INF 0x3FFFFFFF
using namespace std;

struct edge {
  int to;
  edge *nxt;
} edges[MAXN * 2 + 5];

edge *ncnt = &edges[0], *Adj[MAXN + 5];
int n, m;

struct Matrix {
  int M[2][2];

  Matrix operator*(const Matrix &B) {
    static Matrix ret;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        ret.M[i][j] = -INF;
        for (int k = 0; k < 2; k++)
          ret.M[i][j] = max(ret.M[i][j], M[i][k] + B.M[k][j]);
      }
    return ret;
  }
} matr1[MAXN + 5], matr2[MAXN + 5];  // 每個點維護兩個矩陣

int root;
int w[MAXN + 5], dep[MAXN + 5], son[MAXN + 5], siz[MAXN + 5], lsiz[MAXN + 5];
int g[MAXN + 5][2], f[MAXN + 5][2], trfa[MAXN + 5], bstch[MAXN + 5][2];
int stk[MAXN + 5], tp;
bool vis[MAXN + 5];

void AddEdge(int u, int v) {
  edge *p = ++ncnt;
  p->to = v;
  p->nxt = Adj[u];
  Adj[u] = p;

  edge *q = ++ncnt;
  q->to = u;
  q->nxt = Adj[v];
  Adj[v] = q;
}

void DFS(int u, int fa) {
  siz[u] = 1;
  for (edge *p = Adj[u]; p != NULL; p = p->nxt) {
    int v = p->to;
    if (v == fa) continue;
    dep[v] = dep[u] + 1;
    DFS(v, u);
    siz[u] += siz[v];
    if (!son[u] || siz[son[u]] < siz[v]) son[u] = v;
  }
  lsiz[u] = siz[u] - siz[son[u]];  // 輕兒子的siz和+1
}

void DFS2(int u, int fa) {
  f[u][1] = w[u], f[u][0] = 0;
  g[u][1] = w[u], g[u][0] = 0;
  if (son[u]) {
    DFS2(son[u], u);
    f[u][0] += max(f[son[u]][0], f[son[u]][1]);
    f[u][1] += f[son[u]][0];
  }
  for (edge *p = Adj[u]; p != NULL; p = p->nxt) {
    int v = p->to;
    if (v == fa || v == son[u]) continue;
    DFS2(v, u);
    f[u][0] += max(f[v][0], f[v][1]);  // f[][]就是正常的DP數組
    f[u][1] += f[v][0];
    g[u][0] += max(f[v][0], f[v][1]);  // g[][]數組只統計了自己和輕兒子的信息
    g[u][1] += f[v][0];
  }
}

void PushUp(int u) {
  matr2[u] = matr1[u];  // matr1是單點加上輕兒子的信息，matr2是區間信息
  if (bstch[u][0]) matr2[u] = matr2[bstch[u][0]] * matr2[u];
  // 注意轉移的方向，但是如果我們的矩乘定義不同，可能方向也會不同
  if (bstch[u][1]) matr2[u] = matr2[u] * matr2[bstch[u][1]];
}

int getmx2(int u) { return max(matr2[u].M[0][0], matr2[u].M[0][1]); }

int getmx1(int u) { return max(getmx2(u), matr2[u].M[1][0]); }

int SBuild(int l, int r) {
  if (l > r) return 0;
  int tot = 0;
  for (int i = l; i <= r; i++) tot += lsiz[stk[i]];
  for (int i = l, sumn = lsiz[stk[l]]; i <= r; i++, sumn += lsiz[stk[i]])
    if (sumn * 2 >= tot)  // 是重心了
    {
      int lch = SBuild(l, i - 1), rch = SBuild(i + 1, r);
      bstch[stk[i]][0] = lch;
      bstch[stk[i]][1] = rch;
      trfa[lch] = trfa[rch] = stk[i];
      PushUp(stk[i]);  // 將區間的信息統計上來
      return stk[i];
    }
  return 0;
}

int Build(int u) {
  for (int pos = u; pos; pos = son[pos]) vis[pos] = true;
  for (int pos = u; pos; pos = son[pos])
    for (edge *p = Adj[pos]; p != NULL; p = p->nxt)
      if (!vis[p->to])  // 是輕兒子
      {
        int v = p->to, ret = Build(v);
        trfa[ret] = pos;  // 輕兒子的treefa[]接上來
      }
  tp = 0;
  for (int pos = u; pos; pos = son[pos]) stk[++tp] = pos;  // 把重鏈取出來
  int ret = SBuild(1, tp);  // 對重鏈進行單獨的SBuild(我猜是Special Build?)
  return ret;               // 返回當前重鏈的二叉樹的根
}

void Modify(int u, int val) {
  matr1[u].M[1][0] += val - w[u];
  w[u] = val;
  for (int pos = u; pos; pos = trfa[pos])
    if (trfa[pos] && bstch[trfa[pos]][0] != pos && bstch[trfa[pos]][1] != pos) {
      matr1[trfa[pos]].M[0][0] -= getmx1(pos);
      matr1[trfa[pos]].M[0][1] = matr1[trfa[pos]].M[0][0];
      matr1[trfa[pos]].M[1][0] -= getmx2(pos);
      PushUp(pos);
      matr1[trfa[pos]].M[0][0] += getmx1(pos);
      matr1[trfa[pos]].M[0][1] = matr1[trfa[pos]].M[0][0];
      matr1[trfa[pos]].M[1][0] += getmx2(pos);
    } else
      PushUp(pos);
}

int read() {
  int ret = 0, f = 1;
  char c = 0;
  while (c < '0' || c > '9') {
    c = getchar();
    if (c == '-') f = -f;
  }
  ret = 10 * ret + c - '0';
  while (true) {
    c = getchar();
    if (c < '0' || c > '9') break;
    ret = 10 * ret + c - '0';
  }
  return ret * f;
}

void print(int x) {
  if (x == 0) return;
  print(x / 10);
  putchar(x % 10 + '0');
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) w[i] = read();
  int u, v;
  for (int i = 1; i < n; i++) {
    u = read(), v = read();
    AddEdge(u, v);
  }
  DFS(1, -1);
  // 求重兒子
  DFS2(1, -1);
  // 求初始的DP值，也可以在Build()裏面求，但是這樣寫就和樹剖的寫法統一了
  for (int i = 1; i <= n; i++) {
    matr1[i].M[0][0] = matr1[i].M[0][1] = g[i][0];
    matr1[i].M[1][0] = g[i][1], matr1[i].M[1][1] = -INF;  // 初始化矩陣
  }
  root = Build(1);  // root即為根節點所在重鏈的重心
  int lastans = 0;
  for (int i = 1; i <= m; i++) {
    u = read(), v = read();
    u ^= lastans;  // 強制在線
    Modify(u, v);
    lastans = getmx1(root);  // 直接取值
    if (lastans == 0)
      putchar('0');
    else
      print(lastans);
    putchar('\n');
  }
  return 0;
}

參考

P4211 [LNOI2014] LCA | 全局平衡二叉樹

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用