POJ 3468 Splay 树实现区间加与区间和查询

POJ 3468 Splay 树实现区间加与区间和查询

題目大意

給定 N 個整數序列，支援兩種操作（Q ≤ 100,000）：

• C a b c：區間 [a, b] 每個數加上 c。
• Q a b：查詢區間 [a, b] 的和。

數值範圍大，需 64 位整數。本文使用 Splay 树（伸展树）維護序列，利用中序遍歷有序性實現區間操作。

核心資料結構

const int MAXN = 100000 + 100;
LL add[MAXN], sum[MAXN];   // 懶標記、子樹和
int ch[MAXN][2], siz[MAXN]; // 左右子、子樹大小
int key[MAXN], pre[MAXN];   // 節點值、父節點
int A[MAXN];                // 初始值陣列
int root, tot;              // 根節點、節點總數

關鍵操作實作

1. 建樹：遞歸建立平衡 Splay，並在首尾各加一個虛擬節點，方便區間提取（避免邊界討論）。
2. 下推標記 push_down：將當前節點的 add 標記傳遞給左右子，更新子節點的 key、sum、add。
3. 上推更新 push_up：根據左右子更新 siz、sum。
4. 旋轉 Rotate：支援左/右旋，旋轉前先 push_down 父子節點，旋轉後先 push_up 子再父。
5. 伸展 Splay(x, goal)：將節點 x 伸展到 goal 之下（goal=0 為根），使用 Zig-Zig / Zig-Zag 雙旋優化。
6. 第 k 大查找 Get_kth：利用左子樹大小定位序列中第 k 個節點。

區間操作流程

對於區間 [l, r]：

Splay(Get_kth(root, l), 0);           // 將 l 伸展到根
Splay(Get_kth(root, r+2), root);      // 將 r+2 伸展到根的右子
// 此時目標區間正是 root->right->left 子樹
int target = ch[ch[root][1]][0];

• 查詢：直接輸出 sum[target]。
• 修改：對 target 調用 Modify(target, c)，再 push_up 祖先節點。

完整代碼

// 完整代碼見原文，包含：newnode, built, Init, Rotate, Splay, Get_kth, Modify, push_up, push_down, main
// 主迴圈讀取指令，根據 'Q'/'C' 分派處理，輸出查詢結果。

複雜度與心得

• 單次操作均攤 O(log N)，總複雜度 O((N+Q) log N)。
• Splay 树雖代碼量大，但理解其中序遍歷即序列順序、虛擬節點技巧、懶標記下推時機，是掌握進階資料結構的關鍵。
• 本題亦可用線段樹解決，Splay 树提供了另一種視角。