แผนผังกลุ่มในโครงสร้างข้อมูล

ในส่วนนี้เราจะมาดูกันว่าต้นไม้ส่วนคืออะไร ก่อนจะพูดถึงเรื่องนั้น มาดูปัญหากันก่อน

สมมติว่าเรามีอาร์เรย์ arr[0,…,n-1] เราสามารถดำเนินการต่อไปนี้ได้ -

• ค้นหาผลรวมขององค์ประกอบจากดัชนี l ถึง r โดยที่ 0 ≤ l ≤ r ≤ n-1

• เปลี่ยนค่าขององค์ประกอบที่ระบุของอาร์เรย์เป็นค่าใหม่ x เราต้องทำ arr[i] =x ผมอยู่ในช่วง 0 ถึง n – 1.

เราสามารถแก้ปัญหานี้ได้โดยใช้แผนผังกลุ่ม แผนผังเซ็กเมนต์ช่วยให้เราได้รับผลรวมและคิวรีในเวลา O(log n) มาดูวิธีการแสดงสิ่งนี้กัน −

• Leaf nodes เป็นองค์ประกอบของอาร์เรย์ที่กำหนด

• โหนดภายในแต่ละโหนดแสดงถึงการรวมโหนดลีฟบางส่วน การรวมอาจแตกต่างกันในบางกรณี การรวมเข้าด้วยกันเป็นผลรวมของใบไม้ใต้โหนด

สมมติว่าเรามีอาร์เรย์เช่น [1, 3, 5, 7, 9, 11] ต้นไม้ส่วนจะเป็น