ต้นไม้เซกเมนต์: สร้างและสอบถาม
หาค่าต่ำสุด สูงสุด หรือผลรวมของช่วงใน log n
ต้นไม้เซกเมนต์: สร้างและสอบถาม เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ก้าวไปไกลกว่าต้นไม้ Fenwick
ต้นไม้ Fenwick โดดเด่นสำหรับผลรวม แต่ต้นไม้เซกเมนต์รองรับค่าต่ำสุด ค่าสูงสุด ห.ร.ม. และอื่น ๆ ได้ จึงเป็นเครื่องมืออเนกประสงค์สำหรับการสอบถามช่วง
ต้นไม้เหนือช่วงข้อมูล
แต่ละโหนดเป็นเจ้าของช่วงหนึ่งของอาร์เรย์ รากครอบคลุมข้อมูลทั้งหมด ส่วนโหนดลูกจะแบ่งช่วงออกเป็นครึ่งหนึ่งซ้ำ ๆ จนใบเก็บสมาชิกเพียงตัวเดียว
จัดเก็บด้วยอาร์เรย์
เราเก็บต้นไม้ไว้ในอาร์เรย์แบนที่มีขนาด 2n หรือ 4n โหนดที่ 1 คือราก ส่วนโหนดลูกของโหนด i อยู่ที่ 2i และ 2i+1
seg = [0] * (2 * n)ใบเก็บข้อมูล
ในรูปแบบวนซ้ำ ค่าดั้งเดิมจะอยู่ในครึ่งหลังของอาร์เรย์ ที่ดัชนี n ถึง 2n-1
for i in range(n):
seg[n + i] = a[i]สร้างจากล่างขึ้นบน
แต่ละโหนดภายในเกิดจากการcombineโหนดลูกทั้งสอง เติมค่าจาก n-1 ย้อนลงไปถึง 1 แล้วต้นไม้ทั้งต้นก็พร้อมใช้งาน
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]การดำเนินการ combine
ฟังก์ชัน combine เป็นตัวกำหนดพฤติกรรมของต้นไม้ ใช้การบวกสำหรับผลรวม ใช้ค่าต่ำสุดสำหรับการหาค่าต่ำสุด หรือใช้ค่าสูงสุดสำหรับการหาค่าสูงสุด เปลี่ยนฟังก์ชันนี้เพื่อเปลี่ยนการสอบถาม
def combine(x, y):
return min(x, y)อัปเดตจุดแล้วไต่ขึ้น
หากต้องการเปลี่ยนค่าหนึ่งค่า ให้กำหนดค่าที่ใบ แล้วเดินขึ้นไปยังราก โดยคำนวณใหม่แต่ละโหนดแม่จากโหนดลูกทั้งสองระหว่างทาง
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])สอบถามช่วงแบบเปิดด้านขวา
การสอบถามช่วงจะไล่จากปลายทั้งสองด้านเข้าหากัน แล้วรวมโหนดตามขอบเขตเข้าไปในคำตอบ ช่วงนี้เป็นแบบเปิดด้านขวา คือครอบคลุมตั้งแต่ l จนถึงก่อน r
ลูปสอบถามแบบวนซ้ำ
เลื่อน l และ r เข้าหากัน เมื่อดัชนีเป็นขอบเขตคี่ ให้รวมโหนดนั้นเข้าไปก่อน แล้วจึงขยับตัวชี้
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2เป็นลอการิทึมจากทั้งสองด้าน
การสร้างใช้เวลา O(n) ส่วนการอัปเดตและการสอบถามแต่ละครั้งใช้เวลา O(log n) ความสมดุลนี้เองที่ทำให้ต้นไม้เซกเมนต์ใช้งานได้หลากหลาย
อย่าลืมค่าเอกลักษณ์
เริ่มผลลัพธ์ด้วยค่าเอกลักษณ์ของการดำเนินการนั้น: 0 สำหรับผลรวม อินฟินิตี้สำหรับค่าต่ำสุด และลบอินฟินิตี้สำหรับค่าสูงสุด หากเริ่มต้นผิด คำตอบก็จะผิด
res = float('inf')ตรวจสอบอย่างรวดเร็ว
ข้อมูลดิบอยู่ที่ใดในต้นไม้แบบวนซ้ำ
ทบทวน: ช่วงที่ยืดหยุ่น
คุณสร้างต้นไม้เซกเมนต์ได้แล้ว: ใบอยู่ในครึ่งหลัง โหนดแม่เกิดจากการ combine และรองรับการอัปเดตกับการสอบถามในเวลา O(log n) สำหรับผลรวม ค่าต่ำสุด หรือค่าสูงสุด 🌳
คำถามที่พบบ่อย
บทเรียน “ต้นไม้เซกเมนต์: สร้างและสอบถาม” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ต้นไม้เซกเมนต์: สร้างและสอบถาม” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ต้นไม้เซกเมนต์: สร้างและสอบถาม”
หาค่าต่ำสุด สูงสุด หรือผลรวมของช่วงใน log n คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ต้นไม้เซกเมนต์: สร้างและสอบถาม” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า
- อินเวอร์ชันด้วย BIT
- ต้นไม้เซกเมนต์: สร้างและสอบถาม
- การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง