บทที่ 19 binary search และ prefix sum
จบบทนี้ น้องจะเขียน binary search ด้วยลูปได้ถูกทุกขอบ ทั้งตอนที่มีค่าซ้ำและตอนที่ค่าที่ถามไม่มีอยู่ รู้ว่า lower_bound กับ upper_bound ทำอะไรข้างใน และใช้ binary search ค้นหา คำตอบ ของโจทย์แนว "น้อยที่สุดที่ยังทำได้" หรือ "มากที่สุดที่ยังทำได้" ทั้งคำตอบที่เป็นจำนวนเต็มและทศนิยม ฝั่ง prefix sum จะได้ difference array ที่บวกค่าให้ทั้งช่วงหลายครั้งในเวลา O(N + Q) และนับว่ามีกี่ช่วงที่ผลรวมเท่ากับ k สองเรื่องนี้เป็นเครื่องมือที่ใช้บ่อยที่สุดในค่าย 2 และ TOI เพราะเปลี่ยนวิธี O(N2) ให้เหลือ O(N log N) หรือ O(N) ได้ทันทีที่เห็นว่าข้อมูลเรียง หรือคำตอบเป็นทางเดียว
ในบทนี้
| หน้า | ได้อะไร |
|---|---|
| 19.1 binary search แบบวนลูป | หาช่องแรกที่มีค่าอย่างน้อย x ด้วยสัญญาของ lo กับ hi นับค่าที่น้อยกว่า เท่ากับ และไม่เกิน x กับดักลูปไม่จบและ mid ล้น |
| 19.2 lower_bound upper_bound และ equal_range | ข้างในของสามฟังก์ชัน นับค่าในช่วง ค้นวันแรกที่ยอดสะสมถึงเป้า และกับดักลืมเรียงกับอ่านค่าที่ end() |
| 19.3 binary search บนคำตอบ | แบ่งงาน ตัดไม้ ระยะห่างมากสุด สามขั้นก่อนเขียน และวิธีพิสูจน์ว่าเงื่อนไขเป็นทางเดียว |
| 19.4 binary search บนจำนวนจริง | วนจำนวนรอบที่กำหนดแทนการรอ eps ระดับน้ำในแท็งก์ และการพิมพ์ทศนิยมด้วย cout |
| 19.5 difference array และนับช่วงด้วย prefix sum | บวกค่าทั้งช่วงหลายครั้ง prefix xor และนับช่วงที่ผลรวมเท่ากับ k ทั้งแบบค่าแคบและค่ากว้าง |