30.3 segment tree

Fenwick tree ตอบผลรวมได้เพราะลบส่วนที่เกินออกได้ แต่ค่าต่ำสุดของช่วงลบกันไม่ได้ ถ้ารู้ค่าต่ำสุดของ 8 ช่องแรกกับ 3 ช่องแรก ก็ยังไม่รู้ค่าต่ำสุดของช่อง 4 ถึง 8 อยู่ดี หน้านี้สอน segment tree ต้นไม้ที่แต่ละโหนดเก็บคำตอบของช่วงหนึ่ง ใช้ได้กับค่าต่ำสุด ค่าสูงสุด ผลรวม และการรวมแบบอื่นอีกหลายแบบ ทั้งปรับค่าช่องเดียวและถามช่วงเป็น O(log N) โจทย์ที่เจอบ่อยคือ ข้อมูลเปลี่ยนไปเรื่อยๆ แล้วถามค่าต่ำสุดหรือสูงสุดของช่วง หรือถามว่าช่องแรกที่มีค่าถึงเกณฑ์อยู่ตรงไหน

ต้นไม้ของช่วง

สถานีวัดอุณหภูมิ 8 สถานีเรียงตามแนวเขา อุณหภูมิตอนนี้คือ 5 3 8 6 1 9 4 7 สร้างต้นไม้แบบนี้

รากคือโหนด 1 ดูแลช่วง 1 ถึง 8 ทั้งหมด
โหนดที่ดูแลช่วง l ถึง r แบ่งตรงกลาง mid = (l + r) / 2 ลูกซ้ายดูแล l ถึง mid ลูกขวาดูแล mid + 1 ถึง r
แบ่งไปจนเหลือช่วงยาวหนึ่งช่อง ซึ่งเป็นใบ
ทุกโหนดเก็บค่าต่ำสุดของช่วงที่มันดูแล ซึ่งก็คือค่าต่ำสุดของลูกสองตัว
เก็บในอาเรย์แบบ binary heap ในหน้า 26.5 ลูกของโหนด k คือ 2k กับ 2k + 1 ไม่ต้องมี pointer

ต้นไม้นี้ลึก log₂ N ชั้น เพราะช่วงสั้นลงครึ่งหนึ่งทุกชั้น ภาพระบายโหนดที่ใช้ตอบคำถาม "ค่าต่ำสุดของสถานี 2 ถึง 6" ช่วง 2 ถึง 6 ประกอบจากโหนด 9 ที่ดูแลช่อง 2 โหนด 5 ที่ดูแลช่อง 3 ถึง 4 และโหนด 6 ที่ดูแลช่อง 5 ถึง 6 คำตอบคือค่าต่ำสุดของสามโหนดนี้ คือ min(3, 6, 1) = 1

ถามช่วงด้วย recursion

ฟังก์ชันถามเริ่มที่ราก แล้วแยกตามว่าช่วงของโหนด [left, right] กับช่วงที่ถาม [from, to] ซ้อนกันแบบไหน

ไม่ซ้อนกันเลย โหนดนี้ไม่เกี่ยว คืนค่าที่ไม่มีผลกับ min คือ INT_MAX
อยู่ในช่วงที่ถามทั้งก้อน คืนค่าที่เก็บไว้ได้ทันที ไม่ต้องลงไปดูลูก
ซ้อนกันบางส่วน ถามลูกทั้งสองข้าง แล้วเอาค่าต่ำสุดของสองคำตอบ

โปรแกรมนี้พิมพ์ทุกโหนดที่ฟังก์ชันถามเดินผ่าน เพื่อให้เห็นว่าเดินแค่ไหน

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> temperature, tree;
int visited = 0;

void build(int node, int left, int right)
{
    if (left == right) {
        tree[node] = temperature[left];
        return;
    }
    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int left, int right, int from, int to)
{
    visited++;
    if (to < left || right < from) {
        cout << "node " << node << " [" << left << "," << right << "] outside\n";
        return INT_MAX;
    }
    if (from <= left && right <= to) {
        cout << "node " << node << " [" << left << "," << right << "] inside, min " << tree[node] << '\n';
        return tree[node];
    }
    cout << "node " << node << " [" << left << "," << right << "] split\n";
    int mid = (left + right) / 2;
    int left_min = query(2 * node, left, mid, from, to);
    int right_min = query(2 * node + 1, mid + 1, right, from, to);
    return min(left_min, right_min);
}

int main()
{
    cin >> n;
    temperature.assign(n + 1, 0);
    tree.assign(4 * n, 0);
    for (int i = 1; i <= n; i++) {
        cin >> temperature[i];
    }
    build(1, 1, n);
    int from, to;
    cin >> from >> to;
    int answer = query(1, 1, n, from, to);
    cout << "min of " << from << ".." << to << " = " << answer << ", visited " << visited << " nodes\n";
    return 0;
}

8
5 3 8 6 1 9 4 7
2 6

node 1 [1,8] split
node 2 [1,4] split
node 4 [1,2] split
node 8 [1,1] outside
node 9 [2,2] inside, min 3
node 5 [3,4] inside, min 6
node 3 [5,8] split
node 6 [5,6] inside, min 1
node 7 [7,8] outside
min of 2..6 = 1, visited 9 nodes

โหนดที่ต้องแบ่งต่อมีแค่โหนดที่ช่วงคร่อมขอบซ้ายหรือขอบขวาของคำถาม แต่ละชั้นของต้นไม้มีโหนดที่คร่อมขอบได้ไม่เกินสองโหนด คือฝั่งขอบซ้ายหนึ่งกับฝั่งขอบขวาหนึ่ง โหนดที่ฟังก์ชันเดินผ่านจึงไม่เกินราวสี่โหนดต่อชั้น รวมเป็น O(log N) ตัวอย่างนี้เดินผ่าน 9 โหนดจาก 15 โหนด ถ้า N เป็นแสน ต้นไม้ลึกราว 17 ชั้น คำถามหนึ่งข้อเดินผ่านไม่เกินราวเจ็ดสิบโหนด แทนที่จะไล่ดูแสนช่อง

บรรทัดที่ 33 ถึง 35 ถามลูกซ้ายก่อนแล้วเก็บไว้ในตัวแปร ไม่ได้เขียน min(query(...), query(...)) ในบรรทัดเดียว เพราะ C++ ไม่ได้กำหนดว่าต้องคำนวณอาร์กิวเมนต์ตัวไหนก่อน ถ้าเขียนบรรทัดเดียว บนเครื่องที่เขียนเอกสารนี้ทั้งแบบ Code::Blocks และแบบ -O2 ถามลูกขวาก่อน บรรทัดที่สองที่พิมพ์ออกมาจึงเป็นโหนด 3 คำตอบยังถูก แต่อ่านตามยาก

ปรับค่าช่องเดียว

ถ้าสถานี i รายงานค่าใหม่ ใบของช่อง i เปลี่ยน และทุกโหนดที่ดูแลช่วงที่มีช่อง i อยู่ข้างในต้องคำนวณใหม่ ซึ่งคือบรรพบุรุษของใบนั้นตลอดทางขึ้นไปถึงราก มีหนึ่งโหนดต่อชั้น ฟังก์ชันปรับค่าเดินลงไปหาใบตามฝั่งที่ช่อง i อยู่ แก้ใบ แล้วตอนเดินกลับขึ้นก็คำนวณค่าของแต่ละโหนดใหม่จากลูกสองตัว ใช้ O(log N)

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> temperature, tree;

void build(int node, int left, int right) // (1)!
{
    if (left == right) {
        tree[node] = temperature[left];
        return;
    }
    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

void update(int node, int left, int right, int pos, int value)
{
    if (left == right) {
        tree[node] = value;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) {
        update(2 * node, left, mid, pos, value);
    } else {
        update(2 * node + 1, mid + 1, right, pos, value);
    }
    tree[node] = min(tree[2 * node], tree[2 * node + 1]); // (2)!
}

int query(int node, int left, int right, int from, int to)
{
    if (to < left || right < from) {
        return INT_MAX; // (3)!
    }
    if (from <= left && right <= to) {
        return tree[node];
    }
    int mid = (left + right) / 2;
    int left_min = query(2 * node, left, mid, from, to);
    int right_min = query(2 * node + 1, mid + 1, right, from, to);
    return min(left_min, right_min);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    temperature.assign(n + 1, 0);
    tree.assign(4 * n, 0); // (4)!
    for (int i = 1; i <= n; i++) {
        cin >> temperature[i];
    }
    build(1, 1, n);
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            update(1, 1, n, a, b);
        } else {
            cout << "min " << a << ".." << b << " = " << query(1, 1, n, a, b) << '\n';
        }
    }
    return 0;
}

สร้างครั้งแรกจากล่างขึ้นบน ทุกโหนดถูกคำนวณครั้งเดียว ต้นไม้มีไม่ถึง 2N โหนด จึงเป็น O(N)
ลูกฝั่งหนึ่งเปลี่ยนแล้ว ต้องคำนวณโหนดนี้ใหม่ บรรทัดนี้คือหัวใจของการปรับค่า
ค่าที่ไม่มีผลกับ min ห้ามใช้ 0 ดูในส่วนลองทำให้พัง
จอง 4N ช่อง เหตุผลอยู่ในหัวข้อถัดไป

8 6
5 3 8 6 1 9 4 7
2 2 6
2 6 8
1 5 10
2 2 6
1 3 2
2 1 8

min 2..6 = 1
min 6..8 = 4
min 2..6 = 3
min 1..8 = 2

สถานี 5 ซึ่งเคยหนาวที่สุดรายงาน 10 องศา ค่าต่ำสุดของสถานี 2 ถึง 6 จึงกลายเป็น 3 ของสถานี 2 จากนั้นสถานี 3 ลดเหลือ 2 องศา ค่าต่ำสุดของทั้งแนวจึงเป็น 2

ทำไมต้องจอง 4N ช่อง

ถ้า N เป็นกำลังของสอง ต้นไม้เต็มทุกชั้นพอดี ใช้โหนด 1 ถึง 2N - 1 แต่ N อื่นๆ ต้นไม้ไม่สมดุลพอดี ฝั่งซ้ายได้ช่วงยาวกว่าฝั่งขวาหนึ่งช่องอยู่เรื่อย เลขโหนดลึกๆ ทางซ้ายจึงกระโดดไปไกลกว่า 2N ได้ โปรแกรมนี้เดินทั้งต้นไม้แล้วหาเลขโหนดที่มากที่สุด

#include <bits/stdc++.h>
using namespace std;

int largest = 0;

void walk(int node, int left, int right)
{
    largest = max(largest, node);
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    walk(2 * node, left, mid);
    walk(2 * node + 1, mid + 1, right);
}

int main()
{
    int sizes[] = {4, 5, 6, 8, 9, 17, 100000};
    for (int n : sizes) {
        largest = 0;
        walk(1, 1, n);
        cout << "n = " << n << "  largest node = " << largest << "  2n = " << 2 * n << "  4n = " << 4 * n << '\n';
    }
    return 0;
}

n = 4  largest node = 7  2n = 8  4n = 16
n = 5  largest node = 9  2n = 10  4n = 20
n = 6  largest node = 13  2n = 12  4n = 24
n = 8  largest node = 15  2n = 16  4n = 32
n = 9  largest node = 17  2n = 18  4n = 36
n = 17  largest node = 33  2n = 34  4n = 68
n = 100000  largest node = 262141  2n = 200000  4n = 400000

N = 6 ใช้ถึงโหนด 13 เกิน 2N = 12 แล้ว และ N = 100000 ใช้ถึงโหนด 262141 ถ้าจองแค่ 2N ช่อง การเขียนโหนดเหล่านี้คือเขียนนอก vector ซึ่งอาจพังหรือทับข้อมูลอื่นเงียบๆ แบบหน้า 5.5 เลขโหนดมากที่สุดไม่เกิน 4N เสมอ จึงจอง 4N ช่องไว้ให้สบายใจ ต้นไม้ของแสนช่องเป็น int สี่แสนตัว ราว 1.6 MB ประกาศใน vector จึงไม่มีปัญหาเรื่องขนาด

เปลี่ยนการรวม

โครงของ segment tree ไม่ได้ผูกกับ min เปลี่ยนสองจุดก็ได้ต้นไม้แบบอื่น คือวิธีรวมคำตอบของลูกสองตัว กับค่าที่คืนเมื่อโหนดไม่เกี่ยว

ต้องการ	รวมลูกด้วย	โหนดไม่เกี่ยวคืน
ค่าต่ำสุด	`min(a, b)`	`INT_MAX`
ค่าสูงสุด	`max(a, b)`	`INT_MIN`
ผลรวม	`a + b`	`0`

ค่าที่คืนเมื่อโหนดไม่เกี่ยวต้องเป็นค่าที่รวมกับอะไรแล้วได้สิ่งนั้นกลับมาเหมือนเดิม เช่น บวก 0 ได้ค่าเดิม min กับ INT_MAX ได้ค่าเดิม งานผลรวมอย่างเดียวใช้ Fenwick tree ที่สั้นกว่าได้ segment tree เหมาะกับงานที่ Fenwick tree ทำไม่ได้ ต้นไม้ค่าสูงสุดยังเดินลงหา "ช่องแรกที่มีค่าอย่างน้อย x" ได้ใน O(log N) ด้วย โดยเลือกเดินลงฝั่งซ้ายเมื่อลูกซ้ายมีค่าถึง x คล้ายรอยต่อของ binary search ในหน้า 19.1 ลองทำในแบบฝึกหัด

lazy propagation

หน้านี้ปรับค่าได้ทีละช่อง ถ้าโจทย์ให้ปรับทั้งช่วง เช่น บวก 5 ให้ทุกช่องตั้งแต่ l ถึง r สลับกับถามค่าต่ำสุดของช่วง การปรับทีละช่องจะช้าเป็น O(N log N) ต่อครั้ง มีเทคนิคต่อยอดชื่อ lazy propagation ที่จดงานค้างไว้ที่โหนดแล้วค่อยส่งลงไปให้ลูกเมื่อจำเป็น ทำให้ปรับทั้งช่วงได้ใน O(log N) เทคนิคนี้อยู่นอกขอบเขตของเว็บนี้ ถ้าจะแข่ง TOI ต่อ ให้รู้ไว้ว่ามีอยู่และหาอ่านต่อได้

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาคือปรับค่าในอาเรย์ตรงๆ แล้วไล่หาค่าต่ำสุดทุกครั้งที่ถาม ปรับเป็น O(1) แต่ถามเป็น O(N) รวม O(NQ) วัดบนเครื่องเดียวกับหน้า 18.2 แบบ -O2 อุณหภูมิสุ่ม มี Q = N เหตุการณ์ ครึ่งหนึ่งปรับค่า อีกครึ่งถามช่วงสุ่ม รันแต่ละแบบ 5 รอบ ตารางเป็นค่ากลาง

วิธี	N = Q = 100000	N = Q = 200000
ไล่หาค่าต่ำสุดทุกคำถาม O(NQ)	1.18 วินาที	4.48 วินาที
segment tree O(N + Q log N)	0.057 วินาที	0.097 วินาที

ข้อมูลเพิ่มสองเท่า วิธีไล่ช้าลงเกือบสี่เท่าตาม N × Q ส่วน segment tree ช้าลงไม่ถึงสองเท่า สังเกตว่าที่ N = Q = 200000 การไล่หาค่าต่ำสุดใช้ 4.48 วินาที แต่การไล่บวกในหน้า 30.2 ใช้ 1.61 วินาที ทั้งที่เป็น O(NQ) เหมือนกัน วิธีที่ดูเหมือนงานเท่ากันอาจใช้เวลาต่างกันหลายเท่า ต้องวัดจริงทุกครั้ง

ลองทำให้พัง

แบบที่ 1 โหนดที่ไม่เกี่ยวคืน 0

ในโปรแกรม seg-min เขียนบรรทัดของโหนดที่ไม่เกี่ยวเป็น return 0; เพราะเคยชินกับผลรวม แล้วป้อนอุณหภูมิตอนกลางวันซึ่งเป็นบวกทั้งหมด

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> temperature, tree;

void build(int node, int left, int right)
{
    if (left == right) {
        tree[node] = temperature[left];
        return;
    }
    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

void update(int node, int left, int right, int pos, int value)
{
    if (left == right) {
        tree[node] = value;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) {
        update(2 * node, left, mid, pos, value);
    } else {
        update(2 * node + 1, mid + 1, right, pos, value);
    }
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

int query(int node, int left, int right, int from, int to)
{
    if (to < left || right < from) {
        return 0;
    }
    if (from <= left && right <= to) {
        return tree[node];
    }
    int mid = (left + right) / 2;
    int left_min = query(2 * node, left, mid, from, to);
    int right_min = query(2 * node + 1, mid + 1, right, from, to);
    return min(left_min, right_min);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    temperature.assign(n + 1, 0);
    tree.assign(4 * n, 0);
    for (int i = 1; i <= n; i++) {
        cin >> temperature[i];
    }
    build(1, 1, n);
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            update(1, 1, n, a, b);
        } else {
            cout << "min " << a << ".." << b << " = " << query(1, 1, n, a, b) << '\n';
        }
    }
    return 0;
}

5 2
30 25 28 35 32
2 1 5
2 2 4

min 1..5 = 25
min 2..4 = 0

คำถามแรกถามทั้งแนว รากอยู่ในช่วงทั้งก้อน ไม่มีโหนดไหนไม่เกี่ยว จึงได้ 25 ถูกต้อง แต่คำถามที่สองมีโหนดที่ไม่เกี่ยวคืน 0 กลับขึ้นมา 0 น้อยกว่าทุกค่าจริง คำตอบจึงเป็น 0 ทั้งที่ไม่มีสถานีไหนวัดได้ 0 องศา โปรแกรม seg-min ที่ใช้ INT_MAX ตอบ 25 กับข้อมูลชุดเดียวกัน ถ้าทดสอบด้วยข้อมูลที่มีค่าติดลบจะไม่เห็นความผิดนี้ เพราะ 0 ไม่ใช่ค่าต่ำสุดอยู่แล้ว ต้องทดสอบด้วยข้อมูลที่เป็นบวกทั้งหมดด้วย

แบบที่ 2 ลืมคำนวณโหนดพ่อหลังปรับค่า

ลบบรรทัด tree[node] = min(tree[2 * node], tree[2 * node + 1]); ท้ายฟังก์ชัน update ออก คิดว่าแก้ใบแล้วก็พอ

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> temperature, tree;

void build(int node, int left, int right)
{
    if (left == right) {
        tree[node] = temperature[left];
        return;
    }
    int mid = (left + right) / 2;
    build(2 * node, left, mid);
    build(2 * node + 1, mid + 1, right);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

void update(int node, int left, int right, int pos, int value)
{
    if (left == right) {
        tree[node] = value;
        return;
    }
    int mid = (left + right) / 2;
    if (pos <= mid) {
        update(2 * node, left, mid, pos, value);
    } else {
        update(2 * node + 1, mid + 1, right, pos, value);
    }
}

int query(int node, int left, int right, int from, int to)
{
    if (to < left || right < from) {
        return INT_MAX;
    }
    if (from <= left && right <= to) {
        return tree[node];
    }
    int mid = (left + right) / 2;
    int left_min = query(2 * node, left, mid, from, to);
    int right_min = query(2 * node + 1, mid + 1, right, from, to);
    return min(left_min, right_min);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    temperature.assign(n + 1, 0);
    tree.assign(4 * n, 0);
    for (int i = 1; i <= n; i++) {
        cin >> temperature[i];
    }
    build(1, 1, n);
    for (int k = 0; k < q; k++) {
        int type, a, b;
        cin >> type >> a >> b;
        if (type == 1) {
            update(1, 1, n, a, b);
        } else {
            cout << "min " << a << ".." << b << " = " << query(1, 1, n, a, b) << '\n';
        }
    }
    return 0;
}

8 6
5 3 8 6 1 9 4 7
2 2 6
2 6 8
1 5 10
2 2 6
1 3 2
2 1 8

min 2..6 = 1
min 6..8 = 4
min 2..6 = 1
min 1..8 = 1

สองคำถามแรกยังไม่มีการปรับค่า จึงตรงกับโปรแกรม seg-min ทุกบรรทัด แต่หลังจากสถานี 5 เปลี่ยนเป็น 10 องศา คำถามที่สามยังได้ 1 ซึ่งเป็นค่าเก่า เพราะโหนด 6 ยังจำค่าต่ำสุดเดิมไว้ และคำถามสุดท้ายควรได้ 2 แต่ได้ 1 จากโหนด 1 ที่ไม่เคยถูกคำนวณใหม่ ใบถูกแก้แล้วแต่ไม่มีใครอ่านใบโดยตรง เพราะคำถามหยุดที่โหนดบนๆ ที่อยู่ในช่วงทั้งก้อน

สรุป

โหนด k ดูแลช่วงหนึ่ง ลูกคือ 2k กับ 2k + 1 แบ่งช่วงที่จุดกลาง เก็บคำตอบของช่วงนั้น จองอาเรย์ 4N ช่อง
ถามช่วงแยกสามกรณี ไม่เกี่ยวคืนค่ากลาง อยู่ทั้งก้อนคืนค่าที่เก็บไว้ ซ้อนบางส่วนถามลูกทั้งสอง เดินไม่เกินราวสี่โหนดต่อชั้น เป็น O(log N)
ปรับค่าเดินลงไปแก้ใบ แล้วคำนวณทุกโหนดบนทางกลับขึ้นใหม่ O(log N)
เปลี่ยนวิธีรวมกับค่ากลางได้ต้นไม้ค่าต่ำสุด ค่าสูงสุด หรือผลรวม ค่ากลางต้องรวมแล้วไม่เปลี่ยนคำตอบ
ปรับค่าทั้งช่วงต้องใช้ lazy propagation ซึ่งอยู่นอกขอบเขตของเว็บนี้