คู่มือโอลิมปิกคอมพิวเตอร์

Computer Olympiad Guide for Thai High School Students

← กลับสู่หน้าหลัก (Back to Home)

Advanced Data Structures

บทนี้สรุปจากการสอนค่าย สสวท. (IOI Training Camp) เดือนตุลาคม 2024 สำหรับผู้ที่ผ่าน สอวน. และ TOI มาแล้ว จึงถือว่าเขียน segment tree, DFS บน tree และ binary search ได้คล่อง

ควรมองโครงสร้างข้อมูลขั้นสูงจากสองมุม

  1. คิดขึ้นมาได้อย่างไร: โครงสร้างแต่ละแบบแก้จุดช้าของแบบที่ง่ายกว่า เช่น LCA แบบเดินทีละขั้นช้า จึงกระโดดทีละ 2^{j}

  2. ใช้เป็นชิ้นส่วนอย่างไร: โจทย์ระดับนี้ไม่ค่อยถามโครงสร้างตรง ๆ แต่ต้องแปลงโจทย์ให้เหลือ “update ช่วง / query ช่วง” หรือ “query บนเส้นทางใน tree” ก่อน

Lowest Common Ancestor (LCA)

LCA ของ u และ v ใน rooted tree คือ vertex ที่ลึกที่สุดที่เป็นบรรพบุรุษของทั้งคู่

วิธีตรงไปตรงมาคือยก vertex ที่ลึกกว่าขึ้นจนลึกเท่ากัน แล้วยกทั้งคู่ขึ้นทีละขั้นจนเจอกัน ซึ่งใช้ O(n) ต่อคำถาม

Binary lifting เก็บ up[j][v] = บรรพบุรุษลำดับที่ 2^{j} ของ v เพราะ 2^{j} = 2^{j - 1} + 2^{j - 1} จึงคำนวณได้จาก up[j][v] = up[j-1][up[j-1][v]] ทำให้กระโดดระยะใดก็ได้ใน O\left( \log n \right) ขั้น ตามบิตของระยะนั้น

const int LOG = 18;  // 2^18 > 2e5
int up[LOG][N], dep[N];

void dfs(int u, int p) {
  up[0][u] = p;
  for (int v : adj[u]) {
    if (v == p) continue;
    dep[v] = dep[u] + 1;
    dfs(v, u);
  }
}

void build(int root, int n) {
  dfs(root, root);  // พ่อของ root คือตัวเอง จะได้ไม่กระโดดออกนอก tree
  for (int j = 1; j < LOG; j++)
    for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
}

int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  int diff = dep[a] - dep[b];
  for (int j = 0; j < LOG; j++)
    if (diff >> j & 1) a = up[j][a];
  if (a == b) return a;
  for (int j = LOG - 1; j >= 0; j--) {
    if (up[j][a] != up[j][b]) {  // ยังไม่เจอกัน กระโดดได้อย่างปลอดภัย
      a = up[j][a];
      b = up[j][b];
    }
  }
  return up[0][a];
}

ระยะทางระหว่าง u กับ v คือ dep[u] + dep[v] - 2 * dep[lca(u, v)]

Fenwick Tree (Binary Indexed Tree)

ถ้าต้องการแค่ point update กับ prefix sum, Fenwick tree สั้นกว่า segment tree มาก ช่อง bit[i] เก็บผลรวมช่วงยาว i & -i (บิตต่ำสุดของ i) ที่จบที่ i

long long bit[N];  // 1-indexed

void add(int i, long long x) {
  for (; i < N; i += i & -i) bit[i] += x;
}

long long prefix(int i) {  // a[1] + ... + a[i]
  long long s = 0;
  for (; i > 0; i -= i & -i) s += bit[i];
  return s;
}
// sum ของ [l, r] = prefix(r) - prefix(l - 1)

ซ้อนลูปสองชั้นจะได้ 2D Fenwick tree สำหรับผลรวมสี่เหลี่ยม ใช้ O\left( \log^{2}n \right) ต่อคำสั่ง

Lazy: เลื่อนงานไปทำทีหลัง

แนวคิด lazy คือ ไม่ทำงานจนกว่าจะจำเป็น แล้วจดไว้ว่าค้างอะไรอยู่

Lazy deletion ใน heap

priority_queue ลบสมาชิกที่ไม่ใช่ top ไม่ได้ วิธีแก้คือเก็บอีก heap หนึ่งไว้จดว่า “ลบแล้ว” และค่อยทิ้งตอนมันขึ้นมาเป็น top

priority_queue<int> pq, removed;

void erase(int x) { removed.push(x); }

int top() {
  while (!removed.empty() && pq.top() == removed.top()) {
    pq.pop();
    removed.pop();
  }
  return pq.top();
}
Lazy propagation ใน segment tree

ถ้าบวก x ทั้งช่วง \lbrack l,r\rbrack โดย update ทีละตัวจะใช้ O\left( n\log n \right) แทนที่จะเป็นอย่างนั้น เมื่อ node ครอบช่วงทั้งหมดก็หยุดลงไปแล้วจดค่า lz ไว้ที่ node นั้น พอต้องลงไปที่ลูกครั้งถัดไปจึง push ค่าที่ค้างลงไป

ฟังก์ชันที่ต้องคิดให้ครบมีสี่ตัว: build, update, query และ push (pushdown)

long long t[4 * N], lz[4 * N];  // range add, range sum

void apply(int v, int len, long long x) {
  t[v] += x * len;
  lz[v] += x;
}

void push(int v, int tl, int tr) {
  if (lz[v] == 0) return;
  int tm = (tl + tr) / 2;
  apply(2 * v, tm - tl + 1, lz[v]);
  apply(2 * v + 1, tr - tm, lz[v]);
  lz[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, long long x) {
  if (r < tl || tr < l) return;
  if (l <= tl && tr <= r) {
    apply(v, tr - tl + 1, x);
    return;
  }
  push(v, tl, tr);
  int tm = (tl + tr) / 2;
  update(2 * v, tl, tm, l, r, x);
  update(2 * v + 1, tm + 1, tr, l, r, x);
  t[v] = t[2 * v] + t[2 * v + 1];
}

long long query(int v, int tl, int tr, int l, int r) {
  if (r < tl || tr < l) return 0;
  if (l <= tl && tr <= r) return t[v];
  push(v, tl, tr);
  int tm = (tl + tr) / 2;
  return query(2 * v, tl, tm, l, r) + query(2 * v + 1, tm + 1, tr, l, r);
}

ถ้ามี update หลายแบบ เช่น set และ add ให้เก็บ lazy แยกกัน (lzSet, lzAdd) และคิดให้ดีว่าเมื่อซ้อนกันต้องทำอะไรก่อน เช่น set ล้าง add ที่ค้างอยู่ทั้งหมด

Persistent Segment Tree

Persistent data structure เก็บ ทุกเวอร์ชัน หลังการ update แต่ละครั้ง และ query เวอร์ชันเก่าได้

สังเกตว่า point update เปลี่ยนแค่ node บนเส้นทางจาก root ถึง leaf ซึ่งมี O\left( \log n \right) node จึงสร้าง node ใหม่เฉพาะเส้นทางนั้น แล้วชี้ไปที่ลูกเดิมสำหรับส่วนที่ไม่เปลี่ยน แต่ละเวอร์ชันจำแค่ root ของตัวเอง

struct Node { long long sum; int l, r; };
vector<Node> nodes = {{0, 0, 0}};  // node 0 คือ tree ว่าง ลูกชี้กลับมาที่ตัวเอง

int update(int v, int tl, int tr, int pos, long long val) {
  Node copy = nodes[v];  // copy node เดิม
  int u = nodes.size();
  nodes.push_back(copy);
  if (tl == tr) {
    nodes[u].sum = val;
    return u;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm) {
    int child = update(nodes[v].l, tl, tm, pos, val);
    nodes[u].l = child;  // เก็บใส่ตัวแปรก่อน: push_back ใน update อาจย้าย memory ของ nodes
  } else {
    int child = update(nodes[v].r, tm + 1, tr, pos, val);
    nodes[u].r = child;
  }
  nodes[u].sum = nodes[nodes[u].l].sum + nodes[nodes[u].r].sum;
  return u;
}

long long query(int v, int tl, int tr, int l, int r) {
  if (v == 0 || r < tl || tr < l) return 0;
  if (l <= tl && tr <= r) return nodes[v].sum;
  int tm = (tl + tr) / 2;
  return query(nodes[v].l, tl, tm, l, r) + query(nodes[v].r, tm + 1, tr, l, r);
}
// roots[k] = update(roots[k - 1], 0, n - 1, pos, val);

หน่วยความจำรวม O\left( n + q\log n \right) ต่างจากการ copy ทั้ง tree ทุกครั้งซึ่งใช้ O(nq)

Heavy-Light Decomposition (HLD)

HLD ใช้ตอบ query บน เส้นทาง ใน tree เช่น “ค่ามากสุดบนเส้นทาง u ถึง v” พร้อม update ค่าใน vertex

  • Heavy child ของ v คือลูกที่ subtree ใหญ่ที่สุด ลูกที่เหลือเป็น light child

  • ต่อ heavy edge กันได้เป็น heavy path และแต่ละ vertex อยู่ใน heavy path เดียว

  • ทุกครั้งที่เดินผ่าน light edge ขึ้นไป ขนาด subtree อย่างน้อยเท่าตัว ดังนั้นเส้นทางใด ๆ ผ่าน light edge ไม่เกิน O\left( \log n \right) ครั้ง

ถ้า DFS โดยไปที่ heavy child ก่อนเสมอ แต่ละ heavy path จะได้ลำดับ in[] ที่ติดกัน จึงใช้ segment tree ตัวเดียวบน in[] ได้ เส้นทางหนึ่งแตกเป็น O\left( \log n \right) ช่วง แต่ละช่วงใช้ O\left( \log n \right) รวม O\left( \log^{2}n \right)

// g[v] คือรายชื่อลูก (rooted tree ที่ root = 0) หลัง dfs_sz ลูกตัวแรกคือ heavy child
int sz[N], par[N], dep[N], in[N], out[N], nxt[N], timer = 0;

void dfs_sz(int v) {
  sz[v] = 1;
  for (int &u : g[v]) {
    par[u] = v;
    dep[u] = dep[v] + 1;
    dfs_sz(u);
    sz[v] += sz[u];
    if (sz[u] > sz[g[v][0]]) swap(u, g[v][0]);
  }
}

void dfs_hld(int v) {
  in[v] = timer++;
  for (int u : g[v]) {
    nxt[u] = (u == g[v][0] ? nxt[v] : u);  // nxt = หัวของ heavy path
    dfs_hld(u);
  }
  out[v] = timer;  // subtree ของ v คือช่วง [in[v], out[v])
}

int path_max(int a, int b) {  // seg_max(l, r) = max ของ segment tree บนช่วง [l, r]
  int res = INT_MIN;
  while (nxt[a] != nxt[b]) {
    if (dep[nxt[a]] < dep[nxt[b]]) swap(a, b);
    res = max(res, seg_max(in[nxt[a]], in[a]));
    a = par[nxt[a]];
  }
  if (dep[a] > dep[b]) swap(a, b);
  return max(res, seg_max(in[a], in[b]));
}
// เริ่มด้วย dfs_sz(0); nxt[0] = 0; dfs_hld(0);

ข้อดีของการเรียงแบบนี้คือได้ทั้ง path query และ subtree query (ช่วง [in[v], out[v])) ในโครงสร้างเดียว

Treap (ไม่ออกสอบ)

Treap คือ binary search tree ที่แต่ละ node มี priority แบบสุ่ม และเรียงเป็น heap ตาม priority ทำให้ความสูงเฉลี่ย O\left( \log n \right) รุ่นที่ใช้บ่อยคือ implicit treap ซึ่ง split/merge ตามตำแหน่ง ใช้ตัด แปะ หรือกลับด้านช่วงของ array ได้ใน O\left( \log n \right)

อ่านเพิ่ม: Treap (CP-Algorithms), Treaps (USACO Guide), วิดีโอ Treap

โจทย์ฝึกฝน (Practice Problems)

LCA

Fenwick tree และ lazy segment tree

Persistent และ HLD

อ่านเพิ่ม