การประยุกต์ใช้ quicksum

จาก quicksum ก็จะเห็นได้ถึงแนวคิดในการใช้ quicksum หาผลรวมของข้อมูลบน array เป็นช่วงแล้ว
แต่ quicksum ยังสามารถนำไปประยุกต์ใช้ได้อีกมากมาย และแนวคิดเหล่านี้ก็จะถูกนำมาใช้ใน Fenwick tree ด้วย

การหาผลคูณเป็นช่วง

การบวกเลขเพิ่มเป็นช่วงบน array และหาค่าทีละช่อง (เพิ่มเป็นช่วง ถามช่องเดียว)

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

วิธีการคือ สมมุติเราต้องการจะเพิ่ม $v$ บวกเข้าไปช่องทุกช่องในช่วง $[a,b]$
เราก็บวก v เพิ่มเฉพาะในช่อง $A[a]$ และไปลบ $v$ จากช่อง $A[b + 1]$
เกิดอะไรขึ้น ? เมื่อมีการทำ quicksum (ซึ่งก็คือการถามว่าผลบวกจากช่อง $1$ ถึงช่องนั้นๆมีค่าเท่าไหร่)
$A[a]$ ถึง $A[b]$ จะมีค่าเป็น $v$ หมด ส่วน $A[b + 1]$ เป็นต้นไปจะมีค่าเป็น $0$ !!!

การตรวจสอบว่ามีข้อมูลในช่วงๆหนึ่งหมดทุกช่องหรือไม่

ใน array นั้น เราอาจจะใช้ค่า $1$ แทนการมีข้อมูล และ $0$ แทนการไม่มีข้อมูล
เมื่อจะตรวจสอบว่าทุกช่องในช่วง $[a,b]$ มีข้อมูลหมด นั่นคือดูที่ผลบวกจาก $A[a]$ ถึง $A[b]$
ซึ่งหากผลบวกจาก $A[a]$ ถึง $A[b] = b - a + 1$ นั่นคือในช่วงนี้มีข้อมูลหมดทุกช่อง

อ่านเพิ่มเติม

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License