Advanced Data Structures
Segment Tree & Fenwick Tree

Day 09 Morning: การจัดการข้อมูลในช่วง (Range Queries) อย่างมีประสิทธิภาพ

หัวข้อที่จะเรียนรู้

1

โครงสร้างและหลักการของ Fenwick Tree (Binary Indexed Tree)

2

การออกแบบและใช้งาน Segment Tree สำหรับปัญหาที่หลากหลาย

3

การเปรียบเทียบประสิทธิภาพในการทำ Range Query และ Point Update

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

ข้อจำกัดของวิธี Naive

การหาผลรวมในช่วง ( [a, b] ) ด้วย loop ปกติใช้เวลา ( O(n) ) ต่อ Query
การใช้ Prefix Sum Array ช่วยให้ Query เร็ว ( O(1) ) แต่ถ้ามีการเปลี่ยนค่า (Update) จะใช้เวลา ( O(n) )
ในโจทย์โปรแกรมเชิงแข่งขันที่มี ( q ) Query และ ( n ) ข้อมูลขนาดใหญ่ การใช้ ( O(nq) ) จะทำให้เกิด TLE
เป้าหมาย: ทำให้ทั้ง Query และ Update ทำงานได้ใน ( O(\log n) )

แหล่งอ้างอิง: https://www.geeksforgeeks.org/array-range-queries/

Fenwick Tree คืออะไร?

ถูกเสนอโดย P. M. Fenwick ในปี 1994 เป็นโครงสร้างข้อมูลที่:

จำลองการทำงานของ Prefix Sum Array ในรูปแบบที่สามารถ Update ได้รวดเร็ว
ใช้หน่วยความจำน้อย (เท่ากับ Array เดิม) โดยใช้ Array ขนาด ( n+1 )
มีความเร็วคงที่ (Constant factor) ที่ดีมากเมื่อเทียบกับ Segment Tree ในโจทย์บางประเภท
เหมาะสำหรับงานประเภท Range Sum Query และ Point Update

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

กลไกการทำงานด้วย Bitwise

แต่ละตำแหน่ง ( k ) ใน Fenwick Tree จะเก็บผลรวมของช่วงที่มีความยาว ( p(k) )

p(k) = k & -k

( p(k) ) คือกำลังของ 2 ที่มากที่สุดที่หาร ( k ) ลงตัว
ตัวอย่าง: ( p(6) = p(110_2) = 2 ) (ตำแหน่งที่ 6 เก็บผลรวม 2 ตัวล่าสุด)
ตัวอย่าง: ( p(8) = p(1000_2) = 8 ) (ตำแหน่งที่ 8 เก็บผลรวม 8 ตัวล่าสุด)

แหล่งอ้างอิง: https://dev.to/wengao_ye/fenwick-tree-vs-segment-tree-410k

Query & Update ( O(\log n) )

Prefix Sum จนถึง ( k )

ใช้การเดินย้อนกลับ:

while (k > 0) {
  s += tree[k];
  k -= k & -k;
}

Update ตำแหน่ง ( k )

ใช้การเดินไปข้างหน้า:

while (k <= n) {
  tree[k] += val;
  k += k & -k;
}

แหล่งอ้างอิง: https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

ทำไมต้อง Segment Tree?

ในขณะที่ BIT เด่นเรื่องความง่ายและเร็วในงานผลรวม Segment Tree ให้ความยืดหยุ่นกว่า:

รองรับการ Query ได้หลายรูปแบบ: Min, Max, GCD, Sum
รองรับการทำ Range Update ได้ด้วยเทคนิค Lazy Propagation
โครงสร้างเป็น Binary Tree ที่สมบูรณ์ ทำให้เข้าใจขั้นตอนการแบ่งช่วงข้อมูลได้ง่าย
ใช้เวลา ( O(\log n) ) ต่อหนึ่ง Operation เช่นกัน

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Hierarchy of Ranges

Leaf Nodes: เก็บค่าดั้งเดิมของ Array ในแต่ละตำแหน่ง
Internal Nodes: เก็บผลลัพธ์ของฟังก์ชัน (เช่น ผลรวม) ของลูกซ้ายและลูกขวา
หากข้อมูลมีขนาด ( n ) ต้นไม้จะมีโหนดทั้งหมดประมาณ ( 2n ) (ในทางปฏิบัติมักจอง ( 4n ))
แต่ละชั้นของต้นไม้จะลดขนาดช่วงลงครึ่งหนึ่ง จนถึงโหนดเดี่ยว (Leaf)

แหล่งอ้างอิง: https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

Efficient Range Querying

การ Query ช่วง ( [a, b] ) จะแบ่งโหนดออกเป็น 3 กรณี:

ช่วงของโหนดอยู่นอกช่วงที่ Query: Return ค่าว่าง/Neutral
ช่วงของโหนดอยู่ภายในช่วงที่ Query ทั้งหมด: ใช้ค่าจากโหนดนั้นทันที
ช่วงของโหนดทับซ้อนบางส่วน: แบ่งไป Query ลูกซ้ายและลูกขวา แล้วนำมารวมกัน

ใช้เวลาเพียง ( O(\log n) ) เนื่องจากแต่ละระดับจะเลือกโหนดไม่เกิน 2 โหนด

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Point Update Strategy

เมื่อต้องการเปลี่ยนค่าใน Array ที่ตำแหน่ง ( i ):

เริ่มจาก Update ที่ Leaf Node ที่เก็บค่าตำแหน่ง ( i )
จากนั้น Update Parent ย้อนกลับขึ้นไปจนถึง Root
เนื่องจากความสูงของต้นไม้คือ ( \lceil \log n \rceil ) การแก้ไขจึงใช้เวลาเพียง ( O(\log n) )
ค่าในโหนดพ่อแม่จะถูกคำนวณใหม่จากลูกที่เพิ่งเปลี่ยนค่าไป

แหล่งอ้างอิง: https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

BIT vs Segment Tree

หัวข้อ	Fenwick Tree (BIT)	Segment Tree
ความซับซ้อน	( O(\log n) )	( O(\log n) )
หน่วยความจำ	( n )	( 2n ) ถึง ( 4n )
ความง่ายในการเขียน	ง่ายมาก (กะทัดรัด)	ซับซ้อนกว่าเล็กน้อย
การใช้งาน	Range Sum เป็นหลัก	ยืดหยุ่นสูง (Min/Max/RMQ)

แหล่งอ้างอิง: https://dev.to/wengao_ye/fenwick-tree-vs-segment-tree-410k

การ Update ข้อมูลแบบช่วงใน BIT

เราสามารถใช้ Fenwick Tree จัดการการ Update แบบช่วง (Range Update) และ Query รายตัว (Point Query) ได้ด้วย Difference Array:

สร้าง BIT เพื่อเก็บค่าความต่างระหว่างสมาชิกที่ติดกัน ( (d[i] = a[i] - a[i-1]) )
Range Update: การเพิ่มค่าในช่วง ( [a, b] ) ด้วย ( x ) ทำได้โดยการ Update BIT ที่ตำแหน่ง ( a ) ด้วย ( +x ) และตำแหน่ง ( b+1 ) ด้วย ( -x )
Point Query: ค่าจริงที่ตำแหน่ง ( k ) คือผลรวม Prefix Sum ( sumq(1, k) ) ใน BIT

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Sparse Table: Query ในเวลา ( O(1) )

หากข้อมูลไม่มีการ Update (Static) Sparse Table มีประสิทธิภาพสูงมากสำหรับการหาค่าน้อยสุดในช่วง (RMQ):

Preprocessing: ใช้เวลา ( O(n \log n) ) เพื่อคำนวณคำตอบของทุกช่วงที่มีความยาวเป็นกำลังของ 2
Query: ใช้เวลา ( O(1) ) โดยอาศัยสมบัติ Idempotent ของฟังก์ชัน ( \min(a, a) = a )
สูตรการ Query: ( \min(rmq(a, a+k-1), rmq(b-k+1, b)) ) โดยที่ ( k ) คือกำลังของ 2 ที่ใหญ่ที่สุดที่ไม่เกินความยาวช่วง

แหล่งอ้างอิง: https://www.geeksforgeeks.org/sparse-table/

Top-Down Recursive Implementation

การเขียนแบบ Recursive ช่วยให้จัดการช่วงข้อมูลที่ซับซ้อนได้ง่ายขึ้น:


              int sum(int a, int b, int k, int x, int y) {

                if (b < x || a > y) return 0;

                if (a <= x && y <= b) return tree[k];

                int d = (x+y)/2;

                return sum(a, b, 2*k, x, d) + sum(a, b, 2*k+1, d+1, y);

              }

ฟังก์ชันนี้จะแบ่งช่วง ( [x, y] ) ออกเป็นครึ่งซ้ายและขวา จนกว่าจะพบโหนดที่อยู่ในช่วง ( [a, b] ) พอดี

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

ความท้าทายของการ Update แบบช่วง

หากต้อง Update ทุกโหนดใบ (Leaf) ในช่วง ( [a, b] ) จะใช้เวลา ( O(n \log n) )
ซึ่งไม่มีประสิทธิภาพเพียงพอเมื่อมีการ Update บ่อยๆ
ทางออก: เทคนิค Lazy Propagation
หลักการคือ "เลื่อนการ Update ออกไปจนกว่าจะจำเป็นต้องใช้ข้อมูลในโหนดนั้นจริงๆ"

แหล่งอ้างอิง: https://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/

Lazy Propagation ( O(\log n) )

เมื่อ Update ช่วงที่ตรงกับโหนดพอดี ให้เก็บค่า Update ไว้ใน Lazy Array และ Update ค่าสรุปของโหนดนั้นทันที
ไม่ต้องเดินลงไป Update ลูกจนกว่าจะมีการ Query หรือ Update ครั้งใหม่ผ่านโหนดนั้น
เมื่อต้องเข้าถึงโหนดที่มีค่าค้างอยู่ใน Lazy Array ให้ทำการ Push ค่าลงไปยังลูกซ้ายและขวาก่อนประมวลผล

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

ความยืดหยุ่นของ Segment Tree

เราสามารถประยุกต์ใช้ Segment Tree กับ Operation ใดๆ ที่มีสมบัติการเปลี่ยนกลุ่ม (Associative):

Range GCD: หา ห.ร.ม. ของเลขในช่วง

Range XOR: หาค่า XOR รวมในช่วง

Range Max Subarray Sum: หาผลรวมสูงสุดของ Subarray

Range Bitwise AND/OR: การจัดการระดับบิต

แหล่งอ้างอิง: https://dev.to/wengao_ye/fenwick-tree-vs-segment-tree-410k

Dynamic Segment Tree

ใช้ในกรณีที่ช่วงข้อมูลมีขนาดใหญ่มาก (เช่น ( 0 ) ถึง ( 10^9 )) แต่มีการ Update เพียงไม่กี่ตำแหน่ง

สร้างโหนดเฉพาะเมื่อมีการเข้าถึง (On-demand allocation)
ใช้ Pointers (หรือ Dynamic Array) แทนการใช้ Array ขนาดคงที่ ( 4n )
ประหยัดพื้นที่จาก ( O(n) ) เหลือเพียง ( O(k \log n) ) เมื่อ ( k ) คือจำนวนการ Update

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

การเก็บประวัติด้วย Persistence

เทคนิคการสร้างโครงสร้างข้อมูลที่สามารถ Query ข้อมูลในอดีตได้ (Version Control):

เมื่อมีการ Update ตำแหน่งหนึ่ง เราจะไม่ทับข้อมูลเดิม แต่จะสร้าง เส้นทางใหม่ (New Path) จากโหนดใบขึ้นไปถึง Root ใหม่
โหนดที่ไม่เกี่ยวข้องกับการ Update จะใช้ลูกร่วมกับเวอร์ชันเดิม (Path Copying)
แต่ละการ Update เพิ่มโหนดใหม่เพียง ( O(\log n) )

แหล่งอ้างอิง: https://usaco.guide/adv/persistent-seg-tree

2D Segment Tree: ตาราง 2 มิติ

ใช้จัดการปัญหา Query บนพื้นที่สี่เหลี่ยม (Rectangular Subarray Sum/Min):

เป็นโครงสร้างแบบ Segment Tree ซ้อน Segment Tree
ต้นไม้หลักจัดการช่วงของแถว (Rows) และในแต่ละโหนดของแถวจะเก็บ Segment Tree ของคอลัมน์ (Columns)
ความซับซ้อนในการ Query และ Update คือ ( O(\log n \cdot \log m) )
การ Implement ค่อนข้างซับซ้อนและใช้หน่วยความจำสูง ( (O(nm)) )

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Subtree Queries & Path Queries

การเปลี่ยนโครงสร้างต้นไม้ให้เป็นช่วงของ Array:

Euler Tour / Tree Traversal Array: ใช้ DFS เพื่อบันทึกลำดับการเข้าถึงโหนด
แต่ละ Subtree จะกลายเป็น ช่วง (Range) ที่ต่อเนื่องกันใน Array ใหม่
หลังจากแปลงแล้ว เราสามารถใช้ BIT หรือ Segment Tree ปกติจัดการโจทย์บนต้นไม้ได้ในเวลา ( O(\log n) )

"เกือบทุกปัญหาบนต้นไม้ที่เกี่ยวกับช่วง สามารถแก้ได้ด้วยการ Flatten ต้นไม้ลงมาเป็น Array"

แหล่งอ้างอิง: https://usaco.guide/graphs/subtree-queries

Bottom-Up Implementation

การเขียนแบบ Iterative มักจะเร็วกว่าและใช้หน่วยความจำน้อยกว่าแบบ Recursive:


              int sum(int a, int b) {

                a += n; b += n;

                int s = 0;

                while (a <= b) {

                  if (a % 2 == 1) s += tree[a++];

                  if (b % 2 == 0) s += tree[b--];

                  a /= 2; b /= 2;

                }

                return s;

              }

เทคนิคนี้ใช้การเลื่อนตำแหน่ง (a) และ (b) ขึ้นไปยังโหนดพ่อแม่ใน Array ขนาด ( 2n ) จนกว่าช่วงจะบรรจบกัน

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Square Root Decomposition

หากไม่อยากใช้ Tree เราสามารถแบ่ง Array ออกเป็นบล็อก (Blocks):

แบ่ง Array ขนาด ( n ) ออกเป็นบล็อก บล็อกละ ( \sqrt{n} ) ตัว
แต่ละบล็อกจะเก็บค่าสรุป (เช่น ผลรวม) ของสมาชิกในบล็อกนั้น
การ Update: แก้ไขสมาชิกตัวเดียวและ Update ค่าบล็อก ใช้เวลา ( O(1) )
การ Query: คำนวณจากบล็อกที่อยู่ระหว่างช่วง และบวกเพิ่มสมาชิกที่เหลือที่ขอบ ใช้เวลา ( O(\sqrt{n}) )

แหล่งอ้างอิง: https://www.geeksforgeeks.org/sqrt-decomposition-set-1-introduction/

Mo's Algorithm

ใช้สำหรับปัญหา Range Query ที่ข้อมูล ไม่มีการ Update และสามารถเรียงลำดับการประมวลผล Query ได้ (Offline):

จัดกลุ่ม Query ตามบล็อกของจุดเริ่มต้น (Left endpoint) และเรียงตามจุดจบ (Right endpoint)
เคลื่อนย้ายช่วง (Active Range) ทีละขั้นเพื่อหาคำตอบของ Query ถัดไป
ความซับซ้อนรวมคือ ( O((n+q)\sqrt{n}) )
มีประโยชน์มากในปัญหาที่ Segment Tree แก้ได้ยาก เช่น การนับจำนวนตัวเลขที่แตกต่างกันในช่วง

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Index Compression

แก้ปัญหาเมื่อพิกัดข้อมูลมีค่ามากเกินกว่าที่จะจอง Array (เช่น ( 10^9 )):

รวบรวมค่าพิกัด (Coordinates) ทั้งหมดที่ปรากฏในโจทย์
นำมาเรียงลำดับและกำจัดตัวซ้ำ
แทนที่ค่าจริงด้วย "ลำดับที่ (Rank)" จากการเรียงลำดับ (0, 1, 2, ...)
ทำให้เราสามารถใช้พิกัดเหล่านี้ใน BIT หรือ Segment Tree ขนาด ( O(n) ) ได้

แหล่งอ้างอิง: https://usaco.guide/general/coords-comp

Example: Range XOR Queries

โจทย์: ต้องการหาค่า ( a_L \oplus a_{L+1} \oplus \dots \oplus a_R ) และมีการ Update ค่า

เนื่องจาก XOR มีสมบัติการเปลี่ยนกลุ่ม: ( (x \oplus y) \oplus z = x \oplus (y \oplus z) )
เราสามารถเก็บค่า XOR รวมไว้ในโหนดของ Segment Tree ได้
การรวมผลลัพธ์จากลูกซ้ายและขวา: `tree[k] = tree[2*k] ^ tree[2*k+1]`
ฟังก์ชัน Query และ Update ใช้โครงสร้างเดียวกับ Range Sum ทุกประการ

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

RMQ with Updates

Internal Node: เก็บค่าที่น้อยที่สุดในกลุ่มลูก `min(left_child, right_child)`
Update: เมื่อเปลี่ยนค่าที่ใบ ต้องไล่ Update ค่า ( \min ) ขึ้นไปใหม่
Neutral Value: ในการ Query ให้ใช้ค่า ( \infty ) (Infinity) เป็นค่าเริ่มต้นเพื่อให้ ( \min(x, \infty) = x )
ประสิทธิภาพ: ( O(\log n) ) เหมาะสำหรับโจทย์ที่ BIT ทำได้ลำบาก

แหล่งอ้างอิง: https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

Binary Search on Segment Tree

เราสามารถใช้โครงสร้างของต้นไม้ช่วยทำ Binary Search ได้ในเวลา ( O(\log n) ):

หาก Segment Tree เก็บจำนวนสมาชิกในแต่ละช่วง (Frequency)
เมื่อต้องการหาตัวที่ ( k ): ดูที่ลูกซ้าย ถ้าลูกซ้ายมีสมาชิก ( \ge k ) ตัว ให้เดินลงไปทางซ้าย
ถ้าสมาชิกน้อยกว่า ให้หักจำนวนนั้นออกจาก ( k ) แล้วเดินลงไปทางขวา
เทคนิคนี้นิยมใช้หา Order Statistics ในแบบ Dynamic

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Persistence Concepts

โจทย์บางประเภทต้องการ "ย้อนเวลา" หรือ Query ข้อมูลในอดีต:

Path Copying: แทนที่จะแก้ไขโหนดเดิม เราสร้างโหนดใหม่เฉพาะในเส้นทางจาก Root ถึงใบที่เปลี่ยนไป
โหนดใหม่จะเชื่อมต่อกับลูกของโหนดเดิมในส่วนที่ไม่มีการเปลี่ยนแปลง
ทำให้เราได้ Root ใหม่ที่เป็นตัวแทนของ Version ใหม่ โดยใช้พื้นที่เพิ่มเพียง ( O(\log n) ) ต่อการ Update

แหล่งอ้างอิง: https://usaco.guide/adv/persistent-seg-tree

Implementation Tips

Array Size: สำหรับ Segment Tree จอง ( 4n ) เพื่อป้องกัน Index Out of Bounds ในกรณีทั่วไป
Base Case: ตรวจสอบเงื่อนไขช่วงทับซ้อน (Overlap) ให้แม่นยำเพื่อเลี่ยง Infinite Loop
BIT Index: Fenwick Tree มักใช้ 1-based indexing ดังนั้นต้องระวังการใช้ `index 0`
Data Type: ผลรวมช่วงอาจเกินค่าของ `int` ควรพิจารณาใช้ `long long` ใน C++

แหล่งอ้างอิง: https://dev.to/wengao_ye/fenwick-tree-vs-segment-tree-410k

Morning Session Wrap-up

เราได้เรียนรู้เครื่องมือที่ทรงพลังที่สุดในการจัดการช่วงข้อมูล:

Fenwick Tree (BIT)

Segment Tree

Lazy Propagation

Offline Algorithms

"ช่วงบ่ายเราจะนำโครงสร้างเหล่านี้ไปใช้ร่วมกับ Greedy และ Divide & Conquer เพื่อหาคำตอบที่ดีที่สุด!"

พักกลางวัน: 12.00 - 13.00 น.

Advanced Data Structures Segment Tree & Fenwick Tree

หัวข้อที่จะเรียนรู้

ข้อจำกัดของวิธี Naive

Fenwick Tree คืออะไร?

กลไกการทำงานด้วย Bitwise

Query & Update ( O(\log n) )

Prefix Sum จนถึง ( k )

Update ตำแหน่ง ( k )

ทำไมต้อง Segment Tree?

Hierarchy of Ranges

Efficient Range Querying

Point Update Strategy

BIT vs Segment Tree

การ Update ข้อมูลแบบช่วงใน BIT

Sparse Table: Query ในเวลา ( O(1) )

Top-Down Recursive Implementation

ความท้าทายของการ Update แบบช่วง

Lazy Propagation ( O(\log n) )

ความยืดหยุ่นของ Segment Tree

Dynamic Segment Tree

การเก็บประวัติด้วย Persistence

2D Segment Tree: ตาราง 2 มิติ

Subtree Queries & Path Queries

Bottom-Up Implementation

Square Root Decomposition

Mo's Algorithm

Index Compression

Example: Range XOR Queries

RMQ with Updates

Binary Search on Segment Tree

Persistence Concepts

Implementation Tips

Morning Session Wrap-up

Advanced Data Structures
Segment Tree & Fenwick Tree