樹上主席樹

主席樹, 但是維護樹上路徑信息.

由于Defad今天忌離散化, 就不離散化了, 把值域開大點一般沒啥問題.

上次的主席樹有個朋友說沒完全講清楚, 這次先講透了

主席樹, 整體圍繞的是前綴和, 用"批判的繼承"維護前綴和, 然后在前綴和上二分.

為什么主席樹不可修改, 就是因為這個前綴和思想, 所以主席樹要修改需要借助樹狀數組完成 \(\log^{2}{N}\) 的修改.

但是樹套樹等Defad調出來再說, 下篇博客先講莫隊, 應該有幾篇是一系列的莫隊.

void update(int *p, int q, int l, int r, int x, int k) {
  if (*p == 0) {
    *p = ++cntt;
  }
  if (l == r) {
    // 批判的繼承
    tr[*p].val = tr[q].val + k;
    return;
  }
  int m = l + r >> 1;
  if (x <= m) {
    tr[*p].rs = tr[q].rs; // 繼承
    update(&tr[*p].ls, tr[q].ls, l, m);
  } else {
    tr[*p].ls = tr[q].ls; // 繼承
    update(&tr[*p].rs, tr[q].rs, m + 1, r);
  }
  push_up(*p);
}

顯然, 每個批判的繼承的結點都有一個兒子是繼承的, 另一個兒子是批判的繼承的, 這點我們看圖就很顯然.

\(cntt := cntt + 1\), \(rt_{2} := cntt\), 現在第二個權值線段樹的根為 \(8\), 左兒子繼承了 \(rt_{1}\) 的左兒子 \(2\), 右兒子 \(9\) 批判的繼承了 \(rt_{1}\) 的右兒子 \(5\), \(9\) 的右兒子繼承了 \(rt_{1}\) 的右兒子的右兒子 \(7\), 左兒子批判的繼承了 \(rt_{1}\) 的右兒子的左兒子 \(6\).

現在 \(cntt := cntt + 1\), \(rt_{3} := cntt\), 可以手動模擬一下第三個權值線段樹繼承第二個權值線段樹的操作.

那么查詢就是在前綴和上二分了.

先考慮查詢 \(1\) 到 \(x\), 也就是前綴 \(k\) th.

int kth(int p, int l, int r, int k) {
  if (l == r) {
    return l;
  }
  int m = l + r >> 1;
  if (k <= tr[tr[p].ls].val) {
    return kth(tr[p].ls, l, m, k);
  } else if (k <= tr[p].val) {
    k -= tr[tr[p].ls].val;
    return kth(tr[p].rs, m + 1, r, k);
  } else return -1;
}

就是在第 \(x\) 個權值線段樹 \(rt_{x}\) 上找第 \(k\) 個.

那么就可以由維護前綴和之后求區間和是 \(s_{r} - s_{l - 1}\) 得到 區間 \(k\) th 就是二分第 \(l - 1\) 個權值線段樹 \(rt_{l - 1}\) 和 第 \(r\) 個權值線段樹 \(rt_{r}\) 即可.

int kth(int p, int q, int l, int r, int k) {
  if (l == r) {
    return l;
  }
  int m = l + r >> 1;
  if (k <= tr[tr[q].ls].val - tr[tr[p].ls].val) {
    return kth(tr[p].ls, tr[q].ls, l, m, k);
  } else if (k <= tr[q].val - tr[p].val) {
    k -= tr[tr[q].ls].val - tr[tr[p].ls].val;
    return kth(tr[p].rs, tr[q].rs, m + 1, r, k);
  } else return -1;
}

擴展到樹上

剛才我們求的是區間 \(k\) th, 現在求樹上的路徑 \(k\) th.

首先, 樹上前綴和是怎么求路徑和的?

這篇博客只討論從根往下的前綴和.

點權: \(s_{x} + s_{y} - s_{\operatorname{lca}(x, y)} - s_{fa_{\operatorname{lca}(x, y)}}\)

邊權下放點權: \(s_{x} + s_{y} - 2 * s_{\operatorname{lca}(x, y)}\)

為什么是這樣呢?

觀察點權的路徑和.

點權是本來這個點的權值, 所以 \(\operatorname{lca}(x, y)\) 也在 \(x\) 到 \(y\) 的路徑上, 我們需要扣掉 \(s_{\operatorname{lca}(x, y)}\) 和 \(s_{fa_{\operatorname{lca}(x, y)}}\) 就是扣掉了 \(\operatorname{lca}(x, y)\) 上面的而且 \(val_{\operatorname{lca}(x, y)}\) 恰好只算了一次.

但是邊權下放點權則不同.

每個點的權值是"頭頂上"的邊放下來的, 所以路徑并不包括 \(\operatorname{lca}(x, y)\), 因為 \(val_{\operatorname{lca}(x, y)}\) 是 \(\operatorname{lca}(x, y)\) 頭頂上的邊, 所以直接扣掉兩次 \(s_{\operatorname{lca}(x, y)}\) 即可.

那么根據前綴和的思想, 我們每個點的權值線段樹都應該批判的繼承父親的權值線段樹, 然后去二分路徑上最重要的 \(4\) 或 \(3\) 個點所對應的權值線段樹就好了.

例題

VJudge SPOJ LuoGu 雙倍經驗

雙倍經驗有該死的 \(\operatorname{xor}\) 上一個答案, 不這樣我肯定也在線做, 但這就純惡心人了.

就是從根開始 DFS, 所有的點的權值線段樹批判的繼承父親的權值線段樹, 然后去二分 \(rt_{x}\) 和 \(rt_{y}\) 和 \(rt_{\operatorname{lca}(x, y)}\) 和 \(rt_{fa_{\operatorname{lca}(x, y)}}\) 這 \(4\) 個權值線段樹即可.

最后瞎說一通

為什么我們稱 Algorithm 為算法?

為什么我們稱 Data Structure 為人類智慧?

因為數據結構就是人類智慧的閃耀!!!