หาผลรวมช่วงใด ๆ ด้วยการลบ

การสร้างอาร์เรย์ผลรวมคำนำหน้าเป็นเพียงการเตรียมการ ต่อไปคือจุดสำคัญ: ตอบผลรวมของช่วงใด ๆ ด้วย การลบเพียงครั้งเดียว ⚡

ผลรวมของช่วงคือผลรวมขนาดใหญ่หนึ่งค่าลบด้วยผลรวมขนาดเล็กอีกค่าหนึ่ง การ ลบค่าผลรวมคำนำหน้าสองค่าจะตัดทุกสิ่งที่อยู่นอกช่วงของคุณออกได้อย่างพอดี

หากต้องการหาผลรวมของสมาชิกตั้งแต่ l ถึง r ให้ใช้ prefix[r + 1] ลบด้วย prefix[l] สูตรเดียวนี้ใช้ได้กับทุกช่วง

prefix[r + 1] เก็บค่าทั้งหมดตั้งแต่ต้นจนถึง r ส่วน prefix[l] เก็บค่าทั้งหมดก่อนถึง l เมื่อหาผลต่างจึงเหลือเฉพาะส่วนตรงกลางพอดี

สำหรับ [3, 1, 4] ค่า prefix คือ [0, 3, 4, 8] หากต้องการหาผลรวมของดัชนี 1 ถึง 2 ให้คำนวณ 8 ลบ 3 ได้ 5 ซึ่งตรงกับ 1 บวกกับ 4

การสอบถามแต่ละครั้งมีเพียงการลบหนึ่งครั้ง จึงทำงานในเวลา O(1) การสอบถามหนึ่งพันครั้งใช้เวลาเท่ากันต่อครั้งกับการสอบถามเพียงครั้งเดียว

ข้อผิดพลาดที่พบบ่อยที่สุดคือการใช้ดัชนีด้านบน หากมีเลขศูนย์นำหน้า คุณต้องใช้ prefix[r + 1] ไม่ใช่ prefix[r] ควรตรวจสอบขอบเขตนี้ให้ดี

ตัดสินใจตั้งแต่ต้นว่าให้รวม r หรือไม่ สูตรนี้ถือว่าช่วงรวมทั้ง l และ r ซึ่งเป็นรูปแบบที่โจทย์การแข่งขันส่วนใหญ่คาดหวัง

ตัวช่วยขนาดเล็กทำให้ตรรกะอ่านง่ายและรวมการจัดการดัชนีไว้ในที่เดียว ให้ใช้ตัวช่วยนี้แทนการเขียนการคำนวณแทรกไว้โดยตรง

หากต้องการหาผลรวมของทั้งอาร์เรย์ ให้กำหนด l เท่ากับ 0 และ r เท่ากับ n ลบ 1 สูตรจะให้ค่า prefix[n] ซึ่งเป็นผลรวมทั้งหมด

เมื่อโจทย์มีคำถามผลรวมช่วงจำนวนมากบนอาร์เรย์คงที่ ผลรวมสะสมจะเปลี่ยนการวนลูป O(n) ต่อการสอบถามให้กลายเป็นคำตอบที่ได้ทันที

คุณต้องการหาผลรวมของดัชนีตั้งแต่ l ถึง r โดยรวมปลายทั้งสองด้าน

ตอนนี้คุณสามารถตอบการสอบถามผลรวมของช่วงใด ๆ ได้ในเวลา O(1) ด้วย prefix[r + 1] ลบด้วย prefix[l] ระวังออฟเซ็ตจากเลขศูนย์นำหน้า แล้วโค้ดของคุณจะไม่มีข้อผิดพลาด ✅