อาร์เรย์ผลต่างสำหรับการอัปเดตช่วง

ผลรวมสะสมช่วยตอบการสอบถามช่วงได้อย่างรวดเร็ว ส่วนอาร์เรย์ผลต่างจะพลิกแนวคิดนี้เพื่อใช้การอัปเดตหลายช่วงได้อย่างรวดเร็ว 🔁

การเพิ่มค่าให้สมาชิกทุกตัวในช่วงหนึ่งซ้ำหลายครั้งใช้เวลา O(n) ต่อการอัปเดต เมื่อมีการอัปเดต q ครั้งต้นทุนรวมจะเพิ่มขึ้นอย่างมาก

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

อาร์เรย์ผลต่างเก็บระยะห่างระหว่างสมาชิกแต่ละตัวกับสมาชิกที่อยู่ก่อนหน้า การแก้ไขระยะห่างเพียงค่าเดียวจะเลื่อนค่าของช่วงทั้งหมดที่อยู่ถัดไป

หากต้องการเพิ่ม v ตั้งแต่ l ถึง r ให้เพิ่ม v ที่ดัชนี l และลบ v ที่ดัชนี r + 1 การแก้ไขเพียงสองครั้งครอบคลุมทั้งช่วง

เครื่องหมายบวกที่ l จะเปิดใช้การเปลี่ยนแปลง ส่วนเครื่องหมายลบที่ r + 1 จะปิดการเปลี่ยนแปลงนั้น ทั้งสองอย่างร่วมกันจำกัดการอัปเดตให้อยู่ในช่วงเดียว

การอัปเดตแต่ละครั้งมีเพียงการเขียนลงอาร์เรย์สองครั้ง ดังนั้นการอัปเดต q ครั้งใช้เวลาทั้งหมด O(q) ส่วนงานหนักจะเลื่อนไปทำตอนท้าย

หลังจากทำเครื่องหมายทั้งหมดแล้ว ให้หาผลรวมสะสมของอาร์เรย์ผลต่าง การวนผ่านเพียงครั้งเดียวนี้จะสร้างค่าท้ายสุดของทุกตำแหน่งกลับคืนมา

สร้างอาร์เรย์ให้ยาวขึ้นอีกหนึ่งช่อง เพื่อให้ r + 1 ไม่เกินขอบเขต ช่องป้องกันพิเศษนี้ช่วยหลีกเลี่ยงข้อผิดพลาดของดัชนี

คุณใช้เวลา O(q) ทำเครื่องหมายการอัปเดต และใช้เวลา O(n) อีกหนึ่งรอบเพื่อสร้างอาร์เรย์กลับคืนมาต้นทุนรวมจึงต่ำกว่าวิธีตรงไปตรงมา O(n คูณ q) มาก

อาร์เรย์ผลต่างเหมาะอย่างยิ่งกับการนับการจอง ค่าผ่านทางบนถนน และโจทย์ใด ๆ ที่มีการดำเนินการเพิ่มค่าตลอดช่วงจำนวนมากแล้วอ่านผลเพียงครั้งเดียว

คุณเพิ่ม v ให้สมาชิกทุกตัวตั้งแต่ดัชนี l ถึง r

คุณสามารถรวมการอัปเดตช่วงหลายครั้งด้วยอาร์เรย์ผลต่าง: ทำเครื่องหมายที่ l และ r + 1 จากนั้นหาผลรวมสะสมเพียงครั้งเดียวเพื่อสร้างอาร์เรย์กลับคืนมา อัปเดตได้รวดเร็ว อ่านผลครั้งเดียว ✅