Intro
Segment tree เป็นโครงสร้างข้อมูลที่รองรับการดำเนินการ 2 อย่างคือการคำนวณการสอบถามเป็นช่วงและการ update ค่าใน array
Segment tree สามารถรองรับ sum queries, minimum queries และ maximum queries และการสอบถามอื่นๆ ใช้เวลาในการทำงาน O(logn)
เมื่อเทียบกับ Binary indexed tree ข้อได้เปรียบของ Segment tree คือมันเป็นโครงสร้างข้อมูลที่ general กว่า ขณะที่ Binary indexed tree นั้นรองรับเพียง sum queries แต่ Segment tree รองรับการสอบถามอย่างอื่นด้วย แต่ต้องใช้หน่วยความจำมากกว่าและสร้างยากกว่า (แต่ผมว่าสร้างง่ายกว่า)
โครงสร้าง
โครงสร้างของ Segment tree นั้นคือ binary tree ที่ node ในชั้นล่างสุดของ tree เป็นสมาชิกใน array ส่วน node ในชั้นอื่นๆ จะเก็บข้อมูลที่จำเป็นสำหรับการประมวลผลแบบช่วง
เราจะสมมติว่าขนาดของ array มีค่าเป็นยกกำลังของสองและเริ่มต้นใช้ช่องแรกที่ index 0 ถ้าหากขนาดของ array ไม่เท่ากับยกกำลังของสองก็เพียงขยายขนาด array
เราจะเริ่มต้นด้วย Segment tree ที่รองรับ sum queries ให้พิจารณา array ต่อไปนี้
จะได้ Segment tree ดังนี้
แต่ละ internal node สอดคล้องกับช่วงของ array ซึ่งมีขนาดเป็นยกกำลังของสอง ในตัวอย่าง tree ค่าของ internal node คือผลรวมของ array ที่สอดคล้อง และมันถูกคำนวณได้จากผลรวมของค่าจาก nodeลูกทางซ้ายและ nodeลูกลูกทางขวา
การทำเช่นนี้ทำให้ได้ว่า ช่วง [a,b] ใดๆ สามารถแบ่งได้เป็น O(logn) ช่วงซึ่งค่าถูกเก็บใน node ใน tree
พิจารณช่วง [2,7] จะได้ว่า sum(2,7) =7+1+2+9+2+6=27
nodeใน tree สอง nodeสอดคล้องกับช่วงดังกล่าวซึ่งได้ค่า 8+19=27
เมื่อผลรวมถูกคำนวณโดยใช้ nodeที่อยู่ในชั้นสูงที่สุดเท่าที่จะเป็นไปได้ใน tree พบว่าไม่เกินสอง nodeในแต่ละชั้นของ tree ที่จะถูกใช้ ดังนั้นจำนวนของ nodeทั้งหมดคือ O(logn)
หลังจาก array ถูก update เราจะต้อง update ทุก nodeที่ค่าของมันขึ้นกับค่าที่ update ด้วย ซึ่งทำได้โดย traverse ไปตาม path จากค่าที่ update ใน array ไปยัง nodeบนสุดและ update nodeตาม path นี้
รูปต่อไปแสดง tree หากมีการ update ค่า 9
path จาก nodeล่างสุดไป nodeบนสุดจะประกอบด้วย O(logn) node ดังนั้นการ update แต่ละครั้งเปลี่ยน O(logn) node ใน tree
การ Implement
ก่อนหน้านี้เราเคยสร้าง Binary tree โดยใช้ array เช่นในตอนที่เราสร้าง Heap เราจะใช้หลักการเดียวกันในการสร้าง Segment tree นั่นคือเราจะเก็บ Segment tree เป็น array ขนาด 2n เมื่อ n เป็นขนาดของ array ต้นฉบับและมีค่าเป็นยกกำลังของสอง
nodeใน tree จะถูกเก็บจากบนลงล่าง นั่นคือ tree[1] เป็น nodeบนสุด tree[2] และ tree[3] เป็นลูกของมัน ไปเรื่อยๆ
สุดท้ายค่าจาก tree[n] ถึง tree[2n-1] จะเป็นค่าของ array ต้นฉบับซึ่งเป็นชั้นล่างสุดของ tree
Segment tree จะถูกเก็บดังนี้
จากการเก็บแบบนี้เราพบว่า parent ของ tree[k] คือ tree[⌊k/2⌋] และลูกของมันคือ tree[2k] และ tree[2k+1] สังเกตว่าเลขคู่เป็นลูกทางซ้าย
ต่อไปเป็น sum(a,b)
ฟังก์ชันเก็บช่วงที่เริ่มต้น [a+n, b+n] หลังจากนั้นแต่ละ step ช่วงจะถูกย้ายขึ้นไป 1 level ใน tree และก่อนนั้น ค่าของ nodeที่ไม่ได้เป็นของช่วงที่สูงขึ้นจะถูกรวมเข้ากับ sum
เริ่มต้นฟังก์ชันจะ update ค่าที่ level ล่างสุดของ tree หลังจากนั้น ฟังก์ชันจะ update ค่าของทุกๆ internal nodes จนกระทั่งถึง nodeบนสุด
ทั้งสองฟังก์ชันทำงานใน O(logn) เพราะว่า Segment tree ของ n ตัวประกอบด้วย O(logn) ชั้น และฟังก์ชันในแต่ละรอบจะย้ายไปทำงานยัง level ที่สูงขึ้น
Reference
https://cses.fi/book.html