ต้นไม้ช่วงถูกกำหนดให้เป็นโครงสร้างข้อมูลต้นไม้ที่ได้รับคำสั่งเพื่อเก็บรายการจุด อนุญาตให้ดึงข้อมูลทุกจุดภายในช่วงที่กำหนดได้อย่างมีประสิทธิภาพ และโดยทั่วไปจะใช้ในมิติสองมิติขึ้นไป มันเหมือนกับ kd-tree ยกเว้นว่ามีเวลาสืบค้นเร็วขึ้นของ O(log d n + k) แต่การจัดเก็บ O(n log d-1 n) โดย d ระบุขนาดของช่องว่าง n ระบุจำนวนจุดในต้นไม้ และ k ระบุจำนวนจุดที่ดึงมาสำหรับข้อความค้นหาที่กำหนด ต้นไม้ช่วงอาจสร้างความแตกต่างด้วยต้นไม้ช่วงเวลา:แทนที่จะเก็บคะแนนและอนุญาตให้ดึงจุดในช่วงที่กำหนดได้อย่างมีประสิทธิภาพ ต้นไม้ช่วงเวลาจะเก็บช่วงเวลาและอนุญาตให้ดึงช่วงเวลาที่มีจุดที่กำหนดอย่างมีประสิทธิภาพ
โครงสร้างข้อมูล
ตัวอย่างต้นไม้ช่วง 1 มิติ แต่ละโหนดที่ไม่ใช่ลีฟเก็บค่าสูงสุดไว้ในทรีย่อยด้านซ้าย
ต้นไม้ช่วงบนชุดของจุด 1 มิติจะถือเป็นแผนผังการค้นหาไบนารีที่สมดุลบนจุดเหล่านั้น จุดที่เก็บไว้ในต้นไม้จะถูกเก็บไว้ในใบของต้นไม้ แต่ละโหนดภายในเก็บค่าสูงสุดที่มีอยู่ในทรีย่อยด้านซ้าย ต้นไม้ช่วงบนชุดของจุดในมิติ d เป็นแผนผังการค้นหาแบบไบนารีหลายระดับที่กำหนดแบบเรียกซ้ำ โครงสร้างข้อมูลแต่ละระดับถือเป็นโครงสร้างการค้นหาแบบไบนารีในมิติ d ใดมิติหนึ่ง ระดับแรกเป็นแผนผังการค้นหาแบบไบนารีบนพิกัด d แรก แต่ละจุดยอด v ของต้นไม้นี้ประกอบด้วยโครงสร้างที่เกี่ยวข้องซึ่งเป็นต้นไม้ช่วงมิติ (d-1) บน (d-1) จุดสุดท้ายที่จัดเก็บไว้ในทรีย่อยของ v
ปฏิบัติการ
การก่อสร้าง
ต้นไม้ช่วง 1 มิติบนชุดของจุด n จุดเป็นแผนผังการค้นหาแบบไบนารี ซึ่งสามารถสร้างขึ้นในเวลา O(n บันทึก n) ต้นไม้พิสัยในมิติที่สูงกว่าจะถูกสร้างขึ้นแบบเรียกซ้ำโดยการสร้างแผนผังการค้นหาแบบไบนารีที่สมดุลบนพิกัดแรกของจุด และหลังจากนั้น สำหรับแต่ละจุดยอด v ในต้นไม้นี้ การสร้างต้นไม้ช่วงมิติ (d-1) บนจุดที่มีอยู่ ในทรีย่อยของ v การสร้างแผนภูมิต้นไม้ด้วยวิธีนี้จะต้องใช้ O(n log d น) เวลา.
