แผนการเรียน
/

Practice Session
Range Query Problems

Day 09 Afternoon: ลงมือแก้โจทย์โครงสร้างข้อมูลขั้นสูงและเทคนิคการประมวลผลช่วง

เป้าหมายการปฏิบัติ

1
ฝึกการ Implement Fenwick Tree และ Segment Tree ให้แม่นยำ
2
ประยุกต์ใช้โครงสร้างข้อมูลกับโจทย์ Range Minimum Query (RMQ)
3
แก้โจทย์ที่มีการ Update แบบช่วงด้วย Lazy Propagation

แหล่งอ้างอิง: https://cses.fi/problemset/list/

Static Range Sum Queries

ภารกิจ:

มีอาเรย์ขนาด ( n ) และคำถาม ( q ) ข้อ ให้หาผลรวมในช่วง ( [a, b] ) โดยที่ข้อมูลไม่มีการเปลี่ยนแปลง

  • เทคนิค: ใช้ Prefix Sum Array
  • ความซับซ้อน: สร้าง ( O(n) ), ตอบคำถาม ( O(1) ) ต่อข้อ
  • สูตร: ( sumq(a, b) = P[b] - P[a-1] )

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Dynamic Range Sum Queries

ภารกิจ:

เหมือนข้อที่แล้ว แต่มีการ Update ค่าในตำแหน่ง ( i ) ระหว่างการ Query

  • ทางเลือก: Fenwick Tree หรือ Segment Tree
  • ประสิทธิภาพ: ( O(\log n) ) ทั้งการ Update และ Query
  • จุดเน้น: ฝึกเขียนฟังก์ชัน `update(i, val)` และ `query(a, b)` ให้รวดเร็ว

แหล่งอ้างอิง: https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

Range Minimum Query

ความท้าทาย:

หาค่าน้อยที่สุดในช่วง ( [a, b] ) พร้อมรองรับการ Update ค่า

tree[k] = min(tree[2*k], tree[2*k+1]);
  • ใช้ Segment Tree เท่านั้น (Fenwick Tree ไม่รองรับ Min/Max โดยตรง)
  • ระวังค่า Neutral Value สำหรับ Min คือ ( \infty )

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

เมื่อพิกัดใหญ่เกินไป (Coordinate Compression)

โจทย์: ตำแหน่งในอาเรย์มีค่าได้ถึง ( 10^9 ) แต่มีข้อมูลเพียง ( 10^5 ) ตัว

  1. เก็บพิกัดทั้งหมดที่สนใจลงใน Vector
  2. `sort` และใช้ `unique` เพื่อลดตัวซ้ำ
  3. ใช้ `lower_bound` เพื่อเปลี่ยนพิกัดจริงเป็น "ลำดับที่ (Rank)" ในอาเรย์ใหม่
  4. ใช้ค่า Rank นี้เป็น Index ใน Segment Tree/BIT

แหล่งอ้างอิง: https://usaco.guide/general/coords-comp

Counting Inversions

Inversion คือคู่ ( (i, j) ) ที่ ( i < j ) แต่ ( A[i] > A[j] )

  • ใช้ Fenwick Tree เพื่อนับจำนวนตัวเลขที่ "เคยเจอมาแล้ว" และมีค่ามากกว่าตัวปัจจุบัน
  • ขั้นตอน: วนลูปจากขวาไปซ้าย (หรือซ้ายไปขวาด้วยการประยุกต์) แล้ว Query จำนวนตัวที่น้อยกว่า/มากกว่าใน BIT
  • ความซับซ้อน: ( O(n \log n) )

แหล่งอ้างอิง: https://www.geeksforgeeks.org/inversion-count-in-array-using-bit/

Lazy Propagation Practice

ภารกิจ:

เพิ่มค่า ( x ) ให้กับทุกตำแหน่งในช่วง ( [a, b] ) และหาผลรวมในช่วง

  • ฝึกการสร้าง `lazy[]` array เพื่อเก็บค่าที่รอการส่งต่อ (Propagate)
  • เขียนฟังก์ชัน `push()` เพื่อส่งต่อค่าจาก Parent ลงไปยัง Children
  • ทดสอบกับโจทย์ "Range Update Queries" ในระบบ Grader

แหล่งอ้างอิง: https://cp-algorithms.com/data_structures/segment_tree.html#lazy-propagation

Range Queries on Trees

ต้องการหาผลรวมของโหนดใน Subtree ของโหนด ( u )

  • ใช้ DFS เพื่อบันทึกเวลาเข้า (entry) และเวลาออก (exit) ของแต่ละโหนด (Euler Tour)
  • แต่ละ Subtree จะกลายเป็นช่วงที่ต่อเนื่องกันใน Array ลำดับ DFS
  • ใช้ Segment Tree/BIT บน Array นี้เพื่อตอบคำถามใน ( O(\log n) )

แหล่งอ้างอิง: https://usaco.guide/graphs/subtree-queries

Recommended Problems

Static Range Sum Queries Easy
Dynamic Range Minimum Queries Medium
Range Update Queries (Lazy) Hard
Distinct Values Queries (Mo's Algorithm) Advanced

"Choose your challenge and start coding!"

End of Session

สรุปหัวใจสำคัญของวันนี้:

  • การเลือกโครงสร้างข้อมูลให้เหมาะกับ Operation (BIT vs Segment Tree)
  • การวิเคราะห์ความซับซ้อน \( O(n \log n) \) เป็นเกณฑ์มาตรฐานในโจทย์ระดับชาติ
  • ความแม่นยำในการ Implement (การคำนวณ Index และ Base Case)
Good luck with your code!