อินเวอร์ชันด้วย BIT
นับคู่ที่อยู่ผิดลำดับอย่างมีประสิทธิภาพ
อินเวอร์ชันด้วย BIT เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
การผกผันของลำดับคืออะไร
การผกผันของลำดับคือคู่ i < j ที่ a[i] > a[j] ซึ่งเป็นคู่เดียวที่เรียงผิดลำดับ และจำนวนคู่ดังกล่าวใช้วัดว่าอาร์เรย์เรียงไม่เป็นระเบียบมากเพียงใด
เหตุใดการผกผันจึงสำคัญ
จำนวนการผกผันเท่ากับจำนวนครั้งที่การเรียงลำดับแบบฟองจะสลับค่า โจทย์การแข่งขันมักซ่อนแนวคิดนี้ไว้ในคำถามเกี่ยวกับอันดับและความไม่เป็นระเบียบ
การนับแบบตรงไปตรงมาช้าเกินไป
การตรวจสอบทุกคู่ใช้เวลา O(n^2) หาก n มีค่าประมาณ 100000 จะต้องตรวจสอบถึงหนึ่งหมื่นล้านครั้ง ซึ่งเกินขีดจำกัดเวลาไปมาก เราจึงต้องใช้วิธีที่ฉลาดกว่านี้ 🐢
แนวคิดของ BIT
ไล่ดูอาร์เรย์จากซ้ายไปขวา แล้วถามว่า ก่อนหน้าค่าปัจจุบันมีสมาชิกกี่ตัวที่มากกว่ามัน ต้นไม้ Fenwick จะตอบคำถามนี้ไปพร้อมกับการไล่ดู
นับด้วยความถี่
BIT เก็บตารางความถี่ของค่าต่าง ๆ การอัปเดต(v, 1) บันทึกว่าค่า v ปรากฏแล้วในการไล่ดูจนถึงตอนนี้
update(v, 1)ค่าที่มากกว่าคือส่วนท้าย
จำนวนค่าก่อนหน้าที่มากกว่า v เท่ากับจำนวนค่าที่พบแล้ว ลบด้วยจำนวนค่าที่ไม่เกิน v ดังนั้นสำหรับสมาชิกที่ i จึงเป็น i ลบการสอบถาม(v)
inv += i - query(v)การบีบอัดพิกัด
หากค่ามีขนาดใหญ่หรือติดลบ ให้แปลงค่าเหล่านั้นเป็นอันดับ 1..n ก่อน การบีบอัดนี้ทำให้ BIT มีขนาดเล็กลงโดยไม่เปลี่ยนลำดับใด ๆ
rank = {v: i for i, v in enumerate(sorted(set(a)), 1)}การไล่ดูทั้งหมด
วนดูอาร์เรย์ เพิ่มจำนวนค่าที่มากกว่าแต่ละค่าลงในผลรวม แล้วจึงแทรกค่าปัจจุบัน ผลรวมสะสมคือจำนวนการผกผันของลำดับ
for i, v in enumerate(a):
inv += i - query(rank[v])
update(rank[v], 1)ทำงานในเวลา n log n
สมาชิกแต่ละตัวทำให้เกิดการสอบถามหนึ่งครั้งและการอัปเดตหนึ่งครั้ง ซึ่งทั้งสองอย่างใช้เวลา O(log n) การนับทั้งหมดจึงเสร็จในเวลา O(n log n) 🚀
การเรียงแบบผสานเป็นญาติใกล้เคียง
การเรียงแบบผสานก็นับการผกผันของลำดับได้ในเวลา O(n log n) ระหว่างขั้นตอนผสานเช่นกัน แต่เวอร์ชันที่ใช้ BIT มักเขียนได้สั้นกว่าเมื่ออยู่ภายใต้แรงกดดัน
ระวังจำนวนล้น
จำนวนการผกผันอาจมีค่าประมาณ n ยกกำลังสองหารด้วยสอง ซึ่งใหญ่ได้มาก จำนวนเต็มของ Python ไม่จำกัดขนาด แต่ภาษาอื่นอาจต้องใช้ชนิดข้อมูล 64 บิต
ตรวจสอบอย่างรวดเร็ว
ทดสอบความเข้าใจของคุณเกี่ยวกับต้นทุนของการไล่ดู
ทบทวน: การนับความไม่เป็นระเบียบ
คุณนับการผกผันของลำดับในเวลา O(n log n) ได้ด้วยการไล่จากซ้ายไปขวาและถาม BIT ว่ามีค่าที่มากกว่าอยู่ก่อนหน้ากี่ค่า หากจำเป็นให้บีบอัดค่าเสียก่อน ✅
คำถามที่พบบ่อย
บทเรียน “อินเวอร์ชันด้วย BIT” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “อินเวอร์ชันด้วย BIT” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “อินเวอร์ชันด้วย BIT”
นับคู่ที่อยู่ผิดลำดับอย่างมีประสิทธิภาพ คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “อินเวอร์ชันด้วย BIT” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า
- อินเวอร์ชันด้วย BIT
- ต้นไม้เซกเมนต์: สร้างและสอบถาม
- การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง