0Pricing
Competitive Programming Academy · บทเรียน

การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง

เลื่อนการอัปเดตของช่วงทั้งหมดออกไปก่อน

การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน

ปัญหาการอัปเดตช่วง

ถ้าการสอบถามบอกให้เพิ่ม 5 ให้สมาชิกทุกตัวตั้งแต่ l ถึง r จะเป็นอย่างไร การแตะใบแต่ละใบใช้เวลา O(n) ต่อการอัปเดต ซึ่งช้าเกินไปเมื่อมีการอัปเดตช่วงจำนวนมาก 😰

แนวคิดการเลื่อนการทำงาน

การส่งต่อแบบขี้เกียจทำให้โหนดจดจำการเปลี่ยนแปลงที่รอดำเนินการไว้ได้ โดยยังไม่ต้องส่งการเปลี่ยนแปลงนั้นไปยังโหนดลูก งานจะถูกเลื่อนไปจนกว่าคุณจะต้องใช้โหนดลูกจริง ๆ

อาร์เรย์ที่สองสำหรับงานที่รอดำเนินการ

เราจะเก็บอาร์เรย์รอส่งต่อไว้ข้างต้นไม้ด้วย lazy[node] จะเก็บการอัปเดตที่ใช้กับช่วงทั้งหมดของโหนดนั้น แต่ยังไม่ได้ส่งต่อไปยังโหนดลูก

lazy = [0] * (4 * n)

ใช้กับโหนดทั้งโหนด

เมื่อการอัปเดตครอบคลุมโหนดทั้งหมด ให้ปรับค่าที่เก็บไว้และสะสมการเปลี่ยนแปลงไว้ในค่ารอส่งต่อ จากนั้นหยุดได้เลย ไม่จำเป็นต้องลงไปยังโหนดลูก

seg[node] += (r - l + 1) * val
lazy[node] += val

ส่งต่อลงก่อนลงไปยังโหนดลูก

ก่อนเข้าถึงโหนดลูก ให้ส่งค่ารอค้างลงไปยังโหนดลูกทั้งสอง โหนดลูกจึงมีค่าถูกต้องพอดีเมื่อคุณอ่านค่า

def push_down(node, l, r):
    if lazy[node]:
        apply(2*node, l, mid)
        apply(2*node+1, mid+1, r)
        lazy[node] = 0

สามกรณีสำหรับแต่ละโหนด

ที่แต่ละโหนด ช่วงที่สอบถามอาจไม่ทับซ้อน ครอบคลุมทั้งหมด หรือครอบคลุมเพียงบางส่วน ให้ข้าม ใช้การส่งต่อแบบขี้เกียจ หรือเรียกซ้ำเข้าไปในทั้งสองครึ่งตามลำดับ

การอัปเดตแบบขี้เกียจยังคงเป็นลอการิทึม

การอัปเดตช่วงจะแตะเพียง O(log n) โหนด เพราะโหนดที่ถูกครอบคลุมทั้งหมดจะหยุดแต่เนิ่น ๆ นี่คือผลประโยชน์หลักของการใช้วิธีแบบขี้เกียจ ⚡

คิวรีต้องส่งค่าลงด้วย

คิวรีช่วงต้อง ส่งค่าค้างลง ก่อนเรียกซ้ำด้วย เพื่อให้คิวรีอ่านค่าของโหนดลูกล่าสุด การลืมทำเช่นนี้เป็นข้อผิดพลาดคลาสสิกของการอัปเดตแบบหน่วงเวลา

ดึงค่าขึ้นหลังเรียกซ้ำ

หลังจากอัปเดตโหนดลูกแล้ว ให้ รวมค่าใหม่ ของโหนดแม่จากโหนดลูก การดึงค่าขึ้นนี้ทำให้โหนดภายในทุกโหนดสอดคล้องกับต้นไม้ย่อยของตนเสมอ

seg[node] = seg[2*node] + seg[2*node+1]

การกำหนดค่าเทียบกับการบวก

การอัปเดตแบบหน่วงเวลาใช้ได้กับการดำเนินการหลายแบบ แต่ การกำหนดค่า กับการบวกผสานกันต่างวิธี โปรดตัดสินใจก่อนเขียนโค้ดว่าการอัปเดตที่รอดำเนินการสองรายการจะรวมกันอย่างไร

เมื่อใดจึงควรใช้การส่งต่อแบบหน่วงเวลา

ใช้การส่งต่อแบบหน่วงเวลาเมื่อจำเป็นต้องทำ การอัปเดตช่วง อย่างแท้จริงเท่านั้น หากมีเพียงการอัปเดตจุด ต้นไม้เซกเมนต์แบบธรรมดาจะเรียบง่ายกว่าและเพียงพอแล้ว

ตรวจสอบความเข้าใจ

ก่อนเรียกซ้ำเข้าไปยังโหนดลูก ต้องทำสิ่งใด

ทบทวน: การอัปเดตแบบเลื่อนการทำงาน

คุณได้เรียนรู้ การส่งต่อแบบหน่วงเวลา: เก็บการเปลี่ยนแปลงที่รอดำเนินการ ส่งค่าลงก่อนลงไปยังโหนดลูก ดึงค่าขึ้นหลังจากนั้น และทำการอัปเดตช่วงได้ในเวลา O(log n) 🎉

คำถามที่พบบ่อย

บทเรียน “การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง”

เลื่อนการอัปเดตของช่วงทั้งหมดออกไปก่อน คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน

บทเรียน “การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม

ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า
  2. อินเวอร์ชันด้วย BIT
  3. ต้นไม้เซกเมนต์: สร้างและสอบถาม
  4. การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง
← กลับไปที่ Competitive Programming Academy