ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า
อัปเดตจุดและสอบถามคำนำหน้าใน log n
ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดอาร์เรย์ผลรวมคำนำหน้าจึงใช้ไม่ได้
อาร์เรย์ผลรวมคำนำหน้าแบบธรรมดาตอบผลรวมในช่วงได้ทันที แต่การอัปเดตเพียงครั้งเดียวก็ทำให้ต้องสร้างอาร์เรย์ใหม่ทั้งหมด เมื่อมีการอัปเดตจำนวนมาก วิธีนี้จะช้าลง ⏱️
พบกับต้นไม้ Fenwick
ต้นไม้ Fenwick หรือ BIT รองรับทั้งการอัปเดตจุดและการสอบถามผลรวมคำนำหน้าในเวลา O(log n) จึงเหมาะสำหรับผลรวมสะสมที่เปลี่ยนแปลงได้
เริ่มนับดัชนีจากหนึ่งตามการออกแบบ
ต้นไม้ Fenwick อยู่ในอาร์เรย์ที่เริ่มนับดัชนีจาก 1 เราใช้ดัชนี 0 เป็นตัวแทนว่าง ดังนั้นข้อมูลจริงทั้งหมดจึงเริ่มที่ตำแหน่ง 1
tree = [0] * (n + 1)ความมหัศจรรย์ของบิต 1 ที่ต่ำสุด
แต่ละดัชนีครอบคลุมกลุ่มค่ากลุ่มหนึ่ง ขนาดของกลุ่มเท่ากับ i & -i ซึ่งคือบิต 1 ที่อยู่ต่ำสุดของ i เคล็ดลับเดียวนี้เป็นพลังขับเคลื่อนของต้นไม้ทั้งต้น
lowbit = i & -iอัปเดตจุดเดียว
หากต้องการเพิ่มค่าที่ตำแหน่ง i ให้ขยับไปข้างหน้าทีละบิตต่ำสุดที่เป็น 1 ในแต่ละขั้น โดยแตะทุกกลุ่มที่มี i อยู่ภายใน
while i <= n:
tree[i] += delta
i += i & -iสอบถามผลรวมคำนำหน้า
หากต้องการหาผลรวมของค่า i ค่าแรก ให้เดินย้อนกลับ โดยลบบิตต่ำสุดที่เป็น 1ออกในแต่ละขั้นจนกว่าจะถึงศูนย์
s = 0
while i > 0:
s += tree[i]
i -= i & -iลูปทั้งสองเป็นลอการิทึม
ลูปแต่ละลูปจะปิดบิตหนึ่งบิตในแต่ละรอบ จึงทำงานไม่เกิน log n ครั้ง นี่คือเหตุผลที่ทั้งการอัปเดตและการสอบถามยังคงรวดเร็ว
หาผลรวมช่วงจากผลรวมคำนำหน้าสองค่า
ต้องการผลรวมตั้งแต่ l ถึง r หรือไม่ ให้ใช้ผลรวมคำนำหน้าที่ r ลบผลรวมคำนำหน้าที่ l-1 เช่นเดียวกับอาร์เรย์ผลรวมคำนำหน้าแบบคงที่ แต่คราวนี้การอัปเดตก็มีต้นทุนต่ำด้วย
range_sum = query(r) - query(l - 1)สร้างต้นไม้
วิธีสร้างที่ง่ายที่สุดคือเรียกการอัปเดตสำหรับค่าเริ่มต้นแต่ละค่า วิธีนี้ใช้เวลา O(n log n) และเร็วเพียงพอสำหรับการแข่งขันส่วนใหญ่
for i, v in enumerate(a, 1):
update(i, v)ใช้หน่วยความจำน้อยมาก
ต้นไม้ Fenwick ต้องการเพียงอาร์เรย์เดียวที่มีขนาด n+1 การใช้หน่วยความจำที่กะทัดรัดนี้เป็นเหตุผลหนึ่งที่ทำให้ต้นไม้ชนิดนี้ได้รับความนิยมในการแข่งขัน 💾
ควรเลือกใช้ BIT เมื่อใด
เลือกใช้ต้นไม้ Fenwick เมื่อคุณสลับระหว่างการอัปเดตจุดกับการสอบถามผลรวมคำนำหน้าหรือผลรวมช่วง โค้ดสั้นและยากที่จะมีวิธีอื่นทำได้ดีกว่า
ตรวจสอบอย่างรวดเร็ว
มาทำความเข้าใจให้แน่นว่าลูปเคลื่อนที่อย่างไร
ทบทวน: พื้นฐาน BIT
คุณได้รู้จักกับต้นไม้ Fenwick ซึ่งเริ่มนับดัชนีจาก 1 ขับเคลื่อนด้วย i & -i และรองรับทั้งการอัปเดตจุดกับการสอบถามผลรวมคำนำหน้าในเวลา O(log n) ต่อไปเราจะใช้ต้นไม้นี้นับการผกผันของลำดับ 🎯
คำถามที่พบบ่อย
บทเรียน “ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า”
อัปเดตจุดและสอบถามคำนำหน้าใน log n คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ต้นไม้ Fenwick สำหรับผลรวมคำนำหน้า
- อินเวอร์ชันด้วย BIT
- ต้นไม้เซกเมนต์: สร้างและสอบถาม
- การเผยแพร่แบบขี้เกียจสำหรับการอัปเดตช่วง