BZOJ 1146 [CTSC2008] 網絡管理：樹上帶修改 K 大查詢 - 兩種經典解法對比

題目大意

給定一棵樹，每個節點有權值。支持兩種操作：

1. 修改某節點權值。
2. 查詢路徑 u-v 上第 k 大權值。

節點數 N ≤ 80000，操作數 Q ≤ 80000。

解法一：樹鏈剖分 + 線段樹套平衡樹 + 二分答案

核心思想

• 樹鏈剖分將樹路徑分解為 O(log N) 段連續區間。
• 線段樹維護區間，每個節點掛一棵平衡樹（如 Splay/Treap）存儲該區間所有權值。
• 查詢第 k 大：二分答案值 mid，統計路徑上 ≤ mid 的數量，利用線段樹套平衡樹單次查詢 O(log² N)。
• 修改：在 O(log N) 個線段樹節點的平衡樹中刪除舊值、插入新值，各 O(log N)。

複雜度

• 預處理：O(N log² N)
• 單次查詢/修改：O(log³ N)（二分 × 線段樹 × 平衡樹）

解法二：DFS 序 + 主席樹（可持久化線段樹）+ 樹狀數組維護修改

核心思想

• DFS 序將子樹映射為連續區間 [L[u], R[u]]。
• 構建主席樹版本 root[u] 表示根到 u 路徑上的權值多集。查詢路徑 u-v 轉化為 root[u] + root[v] - 2*root[lca] + val[lca]。
• 帶修改：修改節點 u 權值從 a 變 b，影響其子樹內所有節點的主席樹。利用 DFS 序區間 [L[u], R[u]]，在樹狀數組上做區間增減：L[u] +1, R[u]+1 -1（針對值 b），L[u] -1, R[u]+1 +1（針對值 a）。
• 查詢時，將主席樹初始版本與樹狀數組中所有相關修改版本合併，進行區間 K 大查詢。

複雜度

• 預處理：O(N log N)
• 單次查詢/修改：O(log² N)（主席樹查詢 log N × 樹狀數組 log N）

代碼結構對比（關鍵片段）

解法一關鍵：線段樹套 Splay

// Splay 節點結構
struct Node { int ch[2], fa, val, sz, cnt; } t[NN];
// 線段樹節點掛 Splay 根
int root_seg[4*N], lc[4*N], rc[4*N];
// 操作：insert/del/splay/rotate/query_kth 等

解法二關鍵：主席樹 + BIT

// 主席樹節點
struct PSTNode { int lc, rc, sum; } pst[NN];
int root[N]; // 版本根
// BIT 維护修改
int bit[N];
void bit_add(int idx, int val_version) { for(; idx<=N; idx+=lowbit(idx)) bit[idx] = merge(bit[idx], val_version); }
// 查詢合併版本進行 K 大

總結與選型建議

本題兩種解法均屬經典高級數據結構應用，掌握其中任一即可解決樹上帶修改 K 大問題。