Khóa học CTDL và GT

Bài 30.2: Các thao tác cập nhật và truy vấn trên Segment Tree

Chào mừng trở lại với series về Cấu trúc dữ liệu và Giải thuật! Ở bài trước, chúng ta đã cùng nhau làm quen với Segment Tree - một cấu trúc dữ liệu cây mạnh mẽ được thiết kế để xử lý các bài toán liên quan đến truy vấn trên đoạn (range queries) và cập nhật tại điểm (point updates) một cách hiệu quả.

Xây dựng được cây là bước đầu tiên, nhưng sức mạnh thực sự của Segment Tree nằm ở hai thao tác chính: cập nhật khi có giá trị thay đổi và truy vấn khi cần thông tin về một đoạn con. Hôm nay, chúng ta sẽ đi sâu vào bí mật đằng sau hai thao tác này và thấy tại sao chúng lại nhanh đến kinh ngạc với độ phức tạp chỉ $O(\log N)$!

Hãy chuẩn bị tinh thần để "giải mã" các thao tác cốt lõi này nhé!

1. Thao tác Cập nhật (Update) trên Segment Tree

Khi một giá trị tại một vị trí cụ thể trong mảng gốc thay đổi, chúng ta cần phản ánh sự thay đổi này lên Segment Tree. Thao tác cập nhật phải đảm bảo rằng tất cả các nút trong cây mà phạm vi của chúng bao phủ vị trí bị thay đổi đều được cập nhật đúng.

Ý tưởng

Cập nhật trên Segment Tree là một quá trình từ trên xuống (top-down). Chúng ta bắt đầu từ nút gốc (root) và di chuyển xuống các nút con cho đến khi tìm thấy nút lá (leaf node) tương ứng với vị trí cần cập nhật.

1. Xác định đường đi: Bắt đầu từ nút hiện tại, kiểm tra xem vị trí cần cập nhật có nằm trong phạm vi của nút con bên trái hay nút con bên phải.
2. Đệ quy: Gọi đệ quy thao tác cập nhật trên nút con tương ứng.
3. Cập nhật nút cha: Sau khi nút con đã được cập nhật (hoặc đã đạt đến nút lá), giá trị của nút cha hiện tại cần được tính toán lại dựa trên giá trị mới của các nút con.

Chi tiết thuật toán và C++

Giả sử chúng ta xây dựng Segment Tree để tính tổng các phần tử trên một đoạn. Chúng ta cần hàm update(v, tl, tr, pos, new_val), trong đó:

• v: Chỉ số của nút hiện tại trong mảng lưu cây tree.
• tl, tr: Chỉ số đầu và cuối của đoạn mà nút v đại diện trong mảng gốc.
• pos: Chỉ số của phần tử cần cập nhật trong mảng gốc (0 <= pos < N).
• new_val: Giá trị mới của phần tử tại pos.

#include <vector>
#include <iostream>
#include <numeric> // Cho std::accumulate

const int N = 10; // Kích thước mảng gốc ví dụ
std::vector<int> a(N); // Mảng gốc
std::vector<long long> tree(4 * N); // Mảng lưu Segment Tree (kích thước ~4*N)

// Hàm xây dựng cây (để có cây ban đầu để update/query)
// Giả sử chúng ta đã có hàm này từ bài trước
void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        tree[v] = tree[2 * v] + tree[2 * v + 1]; // Tính tổng
    }
}

// Hàm cập nhật giá trị tại vị trí pos thành new_val
void update(int v, int tl, int tr, int pos, int new_val) {
    // Bước 1: Nếu là nút lá tương ứng với vị trí cần cập nhật
    if (tl == tr) {
        tree[v] = new_val; // Cập nhật giá trị trực tiếp
        a[pos] = new_val; // Cập nhật cả mảng gốc (tùy ý, thường không cần thiết trong các bài thi chỉ dùng tree)
    } else {
        // Bước 2: Tìm nút con chứa vị trí cần cập nhật
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            // Vị trí cần cập nhật nằm trong nửa trái
            update(2 * v, tl, tm, pos, new_val);
        } else {
            // Vị trí cần cập nhật nằm trong nửa phải
            update(2 * v + 1, tm + 1, tr, pos, new_val);
        }
        // Bước 3: Sau khi nút con được cập nhật, cập nhật lại giá trị của nút cha
        tree[v] = tree[2 * v] + tree[2 * v + 1]; // Tính tổng mới từ 2 con
    }
}

// ... (Hàm query sẽ viết bên dưới) ...

Giải thích code update:

• Hàm đệ quy update(v, tl, tr, pos, new_val) xử lý nút v đại diện cho đoạn [tl, tr].
• Trường hợp cơ sở: Nếu tl == tr, tức là nút v là một nút lá, và vì chúng ta đã đi theo đúng đường đến pos, nên nút lá này chính xác là nút đại diện cho phần tử a[pos]. Chúng ta chỉ việc gán tree[v] = new_val.
• Trường hợp đệ quy:
  • Tính điểm giữa tm = (tl + tr) / 2.
  • Kiểm tra xem pos nằm ở nửa trái (pos <= tm) hay nửa phải (pos > tm) của đoạn [tl, tr].
  • Gọi đệ quy hàm update trên nút con tương ứng (2*v cho con trái, 2*v+1 cho con phải) với phạm vi tương ứng ([tl, tm] hoặc [tm+1, tr]).
  • Sau khi lời gọi đệ quy trả về (nghĩa là nhánh con đã được cập nhật xong), chúng ta cập nhật giá trị của nút hiện tại tree[v]. Đối với cây tổng, tree[v] sẽ là tổng của tree[2*v] và tree[2*v+1]. Đây là bước quan trọng nhất để đảm bảo thông tin ở các nút cha luôn đúng sau khi có sự thay đổi ở nút con/lá.

Độ phức tạp của Update

Mỗi lần gọi update, chúng ta chỉ đi xuống một nhánh của cây (trái hoặc phải) cho đến khi tới nút lá. Segment Tree có chiều cao là $O(\log N)$. Do đó, thao tác cập nhật chỉ cần thăm $O(\log N)$ nút. Mỗi nút chỉ thực hiện một số phép tính đơn giản (so sánh, cộng). Vì vậy, độ phức tạp thời gian của thao tác cập nhật là $O(\log N)$. Đây là một sự cải thiện đáng kể so với $O(N)$ nếu chúng ta phải cập nhật lại toàn bộ các tổng trên đoạn trong một mảng prefix sum thông thường.

2. Thao tác Truy vấn (Query) trên Segment Tree

Truy vấn trên Segment Tree cho phép chúng ta lấy thông tin (ví dụ: tổng, min, max) của một đoạn con bất kỳ [l, r] trong mảng gốc một cách hiệu quả.

Ý tưởng

Truy vấn trên Segment Tree cũng là một quá trình từ trên xuống (top-down), nhưng linh hoạt hơn cập nhật. Chúng ta bắt đầu từ nút gốc và di chuyển xuống, cố gắng sử dụng thông tin đã lưu ở các nút cha càng sớm càng tốt.

1. Kiểm tra sự trùng lặp: Đối với nút hiện tại đại diện cho đoạn [tl, tr], so sánh nó với đoạn truy vấn [l, r]:
   • Không trùng lặp: Nếu [tl, tr] hoàn toàn nằm ngoài [l, r], đoạn này không đóng góp vào kết quả.
   • Trùng lặp hoàn toàn: Nếu [tl, tr] hoàn toàn nằm gọn trong [l, r] (l <= tl && tr <= r), chúng ta có thể sử dụng ngay giá trị đã tính sẵn tại nút này tree[v]. Đây là bí quyết làm cho truy vấn nhanh chóng!
   • Trùng lặp một phần: Nếu [tl, tr] chỉ giao một phần với [l, r], chúng ta cần "chia để trị" bằng cách gọi đệ quy truy vấn trên cả hai nút con (bên trái và bên phải) và kết hợp kết quả của chúng.

Chi tiết thuật toán và C++

Tiếp tục với Segment Tree tính tổng. Chúng ta cần hàm query(v, tl, tr, l, r), trong đó:

• v, tl, tr: Tương tự như hàm update, là nút hiện tại và phạm vi của nó.
• l, r: Chỉ số đầu và cuối của đoạn truy vấn trong mảng gốc (0 <= l <= r < N).

// Hàm truy vấn tổng trên đoạn [l, r]
long long query(int v, int tl, int tr, int l, int r) {
    // Trường hợp 1: Đoạn của nút hiện tại không giao với đoạn truy vấn
    if (l > r) {
        // Đoạn truy vấn không hợp lệ hoặc nút hiện tại nằm hoàn toàn ngoài đoạn truy vấn
        // Trả về phần tử trung tính cho phép cộng (số 0)
        return 0;
    }
    // Trường hợp 2: Đoạn của nút hiện tại nằm hoàn toàn trong đoạn truy vấn
    if (l <= tl && tr <= r) {
        // Sử dụng ngay giá trị đã tính sẵn tại nút này - đây là sức mạnh của Segment Tree!
        return tree[v];
    }
    // Trường hợp 3: Đoạn của nút hiện tại giao một phần với đoạn truy vấn
    int tm = (tl + tr) / 2;
    // Gọi đệ quy truy vấn trên cả hai nút con
    // Đoạn truy vấn trên con trái là giao của [l, r] và [tl, tm] -> [l, min(r, tm)]
    // Đoạn truy vấn trên con phải là giao của [l, r] và [tm+1, tr] -> [max(l, tm+1), r]
    return query(2 * v, tl, tm, l, std::min(r, tm)) +
           query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
}

// Lưu ý: Hàm min và max cần include <algorithm>
#include <algorithm>

Giải thích code query:

• Hàm đệ quy query(v, tl, tr, l, r) xử lý nút v ([tl, tr]) và đoạn truy vấn [l, r].
• Trường hợp cơ sở 1 (Không giao): Nếu l > r, điều này có thể xảy ra khi đoạn truy vấn ban đầu không hợp lệ, hoặc khi gọi đệ quy, phạm vi của nút con không còn giao với đoạn truy vấn còn lại. Chúng ta trả về 0, là phần tử trung tính cho phép cộng (thêm 0 không làm thay đổi tổng). Nếu bài toán là tìm MIN, bạn sẽ trả về một số rất lớn (INT_MAX); nếu là tìm MAX, bạn trả về một số rất nhỏ (INT_MIN).
• Trường hợp cơ sở 2 (Giao hoàn toàn): Nếu l <= tl && tr <= r, nghĩa là đoạn [tl, tr] của nút hiện tại nằm hoàn toàn bên trong đoạn truy vấn [l, r]. Toàn bộ thông tin của đoạn này cần được đưa vào kết quả. Chúng ta chỉ việc trả về tree[v]. Đây là lúc chúng ta "tiết kiệm" được rất nhiều bước đi xuống các nút lá.
• Trường hợp đệ quy (Giao một phần): Nếu không rơi vào hai trường hợp trên, nghĩa là đoạn [tl, tr] của nút hiện tại chỉ giao một phần với đoạn truy vấn [l, r]. Chúng ta cần chia đoạn [tl, tr] thành hai nửa [tl, tm] và [tm+1, tr] và gọi đệ quy truy vấn trên cả hai nút con (2*v và 2*v+1).
  • Khi gọi đệ quy, đoạn truy vấn cần được cắt lại cho phù hợp với phạm vi của nút con. Ví dụ, khi gọi cho con trái ([tl, tm]), đoạn truy vấn thực tế chỉ là phần giao giữa [l, r] và [tl, tm], tức là đoạn [l, min(r, tm)]. Tương tự cho con phải.
  • Kết quả cuối cùng là tổng (hoặc MIN, MAX,...) của kết quả từ hai lời gọi đệ quy trên hai nút con.

Độ phức tạp của Query

Trong trường hợp xấu nhất, một truy vấn [l, r] có thể khiến chúng ta phải đi xuống cả hai nhánh từ một nút cha nếu đoạn truy vấn "cắt ngang" điểm giữa tm. Tuy nhiên, ở mỗi tầng của cây, đoạn truy vấn [l, r] sẽ chỉ giao với một số lượng nhỏ (thường là 2 hoặc 4) các đoạn con của các nút ở tầng đó mà chúng ta cần đi xuống tiếp. Hoặc chúng ta sẽ gặp trường hợp giao hoàn toàn và dừng lại.

Nhờ cơ chế "giao hoàn toàn", chúng ta không cần đi đến tận các nút lá cho mọi phần tử trong đoạn [l, r]. Chiều cao cây là $O(\log N)$. Số nút được thăm trong một truy vấn là $O(\log N)$. Do đó, độ phức tạp thời gian của thao tác truy vấn là $O(\log N)$.

3. Ví dụ Minh họa Hoàn chỉnh

Hãy xem một ví dụ đầy đủ về cách sử dụng Segment Tree với cả build, update và query.

Giả sử mảng gốc ban đầu a = [1, 3, 5, 7, 9, 11, 13, 15] (kích thước N=8).

1. Build: Xây dựng Segment Tree cho mảng này.
2. Query 1: Truy vấn tổng trên đoạn [2, 5] (tức là các chỉ số 2, 3, 4, 5). Kết quả mong đợi: a[2]+a[3]+a[4]+a[5] = 5 + 7 + 9 + 11 = 32.
3. Update: Cập nhật giá trị tại chỉ số 3 (giá trị 7) thành 10. Mảng gốc mới: [1, 3, 5, 10, 9, 11, 13, 15]. Segment Tree cũng được cập nhật dọc theo đường đi từ gốc đến lá tương ứng với chỉ số 3.
4. Query 2: Truy vấn tổng trên đoạn [2, 5] một lần nữa. Kết quả mong đợi: a[2]+a[3]+a[4]+a[5] = 5 + 10 + 9 + 11 = 35.

#include <vector>
#include <iostream>
#include <numeric>
#include <algorithm> // For std::min and std::max

const int MAX_N = 100; // Kích thước tối đa của mảng gốc
std::vector<int> a(MAX_N);
std::vector<long long> tree(4 * MAX_N);

// Hàm xây dựng cây Segment Tree (tính tổng)
void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

// Hàm cập nhật giá trị tại vị trí pos thành new_val
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        tree[v] = new_val;
        // Thường không cần cập nhật mảng 'a' nếu chỉ dùng tree
        // a[pos] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            update(2 * v, tl, tm, pos, new_val);
        } else {
            update(2 * v + 1, tm + 1, tr, pos, new_val);
        }
        tree[v] = tree[2 * v] + tree[2 * v + 1];
    }
}

// Hàm truy vấn tổng trên đoạn [l, r]
long long query(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        return 0; // Phần tử trung tính cho phép cộng
    }
    if (l <= tl && tr <= r) {
        return tree[v];
    }
    int tm = (tl + tr) / 2;
    return query(2 * v, tl, tm, l, std::min(r, tm)) +
           query(2 * v + 1, tm + 1, tr, std::max(l, tm + 1), r);
}

int main() {
    // Khởi tạo mảng gốc
    int n = 8; // Kích thước thực tế của mảng
    a = {1, 3, 5, 7, 9, 11, 13, 15}; // Gán giá trị cho n phần tử đầu tiên

    // Bước 1: Xây dựng Segment Tree
    build(1, 0, n - 1); // Bắt đầu xây dựng từ nút gốc 1, phạm vi [0, n-1]

    std::cout << "Segment Tree ban dau da duoc xay dung." << std::endl;

    // Bước 2: Truy vấn ban đầu
    int query_l = 2, query_r = 5;
    long long sum1 = query(1, 0, n - 1, query_l, query_r);
    std::cout << "Tong doan [" << query_l << ", " << query_r << "] ban dau: " << sum1 << std::endl; // Expected: 32

    // Bước 3: Cập nhật giá trị
    int update_pos = 3;
    int new_value = 10;
    std::cout << "Cap nhat gia tri tai vi tri " << update_pos << " tu " << a[update_pos] << " thanh " << new_value << std::endl;
    update(1, 0, n - 1, update_pos, new_value);
    // In gia tri sau update (tuy chon, de kiem tra neu ban cap nhat mang 'a')
    // std::cout << "Mang a sau update: ";
    // for(int i = 0; i < n; ++i) std::cout << a[i] << " ";
    // std::cout << std::endl;


    // Bước 4: Truy vấn sau khi cập nhật
    long long sum2 = query(1, 0, n - 1, query_l, query_r);
    std::cout << "Tong doan [" << query_l << ", " << query_r << "] sau cap nhat: " << sum2 << std::endl; // Expected: 35

    return 0;
}

Giải thích hàm main:

• Chúng ta khởi tạo mảng gốc a với 8 phần tử.
• Gọi build(1, 0, n-1) để xây dựng cây. Nút gốc có chỉ số 1, đại diện cho toàn bộ mảng từ chỉ số 0 đến n-1.
• Gọi query(1, 0, n-1, 2, 5) để truy vấn tổng đoạn từ chỉ số 2 đến 5.
• Gọi update(1, 0, n-1, 3, 10) để thay đổi giá trị tại chỉ số 3.
• Gọi query(1, 0, n-1, 2, 5) một lần nữa để thấy kết quả đã thay đổi.

Lưu ý về chỉ số:

• Trong Segment Tree, chúng ta thường sử dụng chỉ số 1 cho nút gốc để đơn giản hóa việc tính chỉ số nút con (con trái 2*v, con phải 2*v+1). Mảng gốc a và phạm vi [tl, tr] vẫn dùng chỉ số 0-based.

Bài tập ví dụ:

Cây truy vấn

Trong một chuyến đi nghiên cứu thực vật, FullHouse Dev phát hiện một loài cây đặc biệt với những chiếc đèn phát sáng trên mỗi nhánh. Để hiểu rõ hơn về cách hoạt động của loài cây này, họ đã mô hình hóa nó thành một bài toán.

Bài toán

Một cây là một đồ thị đơn giản trong đó mọi cặp đỉnh đều được kết nối bởi đúng một đường đi. Cho một cây có gốc với \(n\) đỉnh và mỗi đỉnh được gắn một chiếc đèn. Ban đầu, tất cả đèn đều được bật và cây được bắt đầu từ đỉnh \(1\).

Có \(q\) truy vấn thuộc một trong hai loại sau:

1. Chuyển đổi trạng thái đèn tại đỉnh \(v\) (từ Bật sang Tắt hoặc ngược lại)
2. Xác định số đỉnh trong cây con gốc \(v\) mà có thể đi đến được từ \(v\) chỉ qua các đỉnh có đèn đang bật

INPUT FORMAT:

• Dòng đầu tiên: Hai số nguyên \(n\) và \(q\) - số đỉnh và số truy vấn
• \(n-1\) dòng tiếp theo: Hai số \(u\) và \(v\) thể hiện cạnh nối giữa đỉnh \(u\) và \(v\)
• \(q\) dòng tiếp theo: Hai số nguyên \(t\) và \(v\), trong đó \(t\) là loại truy vấn

OUTPUT FORMAT:

• Với mỗi truy vấn loại 2, in ra kết quả trên một dòng

Ràng buộc:

• \(1 \leq n, q \leq 10^5\)

Ví dụ

INPUT

5 4
1 2
2 3
1 4
4 5
1 3
2 2
1 3
2 2

OUTPUT

1
2

Giải thích

• Ban đầu tất cả đèn đều bật
• Sau truy vấn đầu tiên, đèn tại đỉnh 3 bị tắt
• Truy vấn thứ hai hỏi về số đỉnh có thể đến được từ đỉnh 2 qua các đỉnh có đèn sáng, kết quả là 1
• Truy vấn thứ ba bật lại đèn tại đỉnh 3
• Truy vấn cuối cùng cho kết quả là 2 vì có thể đi đến cả đỉnh 2 và 3

Okay, đây là hướng dẫn giải bài Cây truy vấn bằng C++ một cách ngắn gọn, tập trung vào các kỹ thuật cần thiết mà không đưa ra code hoàn chỉnh.

1. Phân tích bài toán và nhận diện cấu trúc dữ liệu phù hợp:

• Bài toán yêu cầu thực hiện hai loại thao tác trên cây: cập nhật trạng thái một đỉnh (bật/tắt đèn) và truy vấn tính toán trên cây con (đếm số đỉnh reachable từ gốc cây con chỉ qua các đỉnh sáng).
• Cập nhật điểm (point update) và truy vấn trên cây con (subtree query) là dấu hiệu mạnh mẽ cho thấy cần sử dụng kỹ thuật làm phẳng cây (tree flattening) kết hợp với cấu trúc dữ liệu hỗ trợ truy vấn đoạn (như Segment Tree hoặc Fenwick Tree).

2. Kỹ thuật làm phẳng cây (Tree Flattening):

• Sử dụng duyệt cây theo chiều sâu (DFS) bắt đầu từ gốc (đỉnh 1).
• Trong quá trình DFS, ghi lại thời gian bắt đầu thăm tin[v] và thời gian kết thúc thăm tout[v] cho mỗi đỉnh v. tin[v] là thời điểm ta lần đầu tiên thăm v, và tout[v] là thời điểm ta kết thúc việc thăm toàn bộ cây con gốc v.
• Các đỉnh trong cây con gốc v sẽ tương ứng với các đỉnh có tin[u] nằm trong khoảng [tin[v], tout[v]].
• Ta có thể xây dựng một mảng phẳng (flat array), ví dụ nodes_in_dfs_order, trong đó nodes_in_dfs_order[i] là đỉnh được thăm ở thời điểm i trong quá trình DFS (theo thứ tự tin). Mảng này có kích thước bằng n. Đỉnh v sẽ ở vị trí tin[v] trong mảng này. Cây con gốc v sẽ tương ứng với một đoạn liên tục trong mảng này, từ index tin[v] đến tin[v] + subtree_size[v] - 1 (hoặc sử dụng tout[v], tùy cách cài đặt chính xác tout). Sử dụng tin[v] và kích thước cây con subtree_size[v] là cách phổ biến hơn, cây con v tương ứng đoạn [tin[v], tin[v] + subtree_size[v] - 1].

3. Ánh xạ bài toán lên mảng phẳng:

• Tạo một mảng boolean hoặc integer is_on_arr có kích thước n+1 (hoặc n nếu dùng 0-based index), trong đó is_on_arr[i] lưu trạng thái bật (1) hay tắt (0) của đèn tại đỉnh nodes_in_dfs_order[i] (đỉnh có tin bằng i). Ban đầu tất cả là 1.
• Truy vấn loại 1 (đổi trạng thái đèn tại v): Tương ứng với việc lật giá trị tại vị trí tin[v] trong mảng is_on_arr. Đây là một cập nhật điểm trên mảng.
• Truy vấn loại 2 (đếm reachable từ v trong cây con): Tương ứng với việc đếm các đỉnh u trong cây con v (tức là các đỉnh nodes_in_dfs_order[i] với i trong đoạn [tin[v], tin[v] + subtree_size[v] - 1]) sao cho đường đi từ v đến u chỉ đi qua các đỉnh có đèn bật. Điều này có nghĩa là u phải bật, cha của u (nếu u!=v) phải bật và reachable từ v, v.v., cho đến v phải bật.

4. Cấu trúc dữ liệu hỗ trợ truy vấn đoạn và cập nhật điểm (Segment Tree):

• Sử dụng Segment Tree trên mảng is_on_arr (các index tin). Segment Tree cho phép cập nhật điểm và truy vấn đoạn trong thời gian O(log n).
• Thử thách chính là định nghĩa trạng thái (state) cho một node trong Segment Tree biểu diễn đoạn [L, R] của các tin index, sao cho ta có thể merge (kết hợp) trạng thái của hai node con [L, M] và [M+1, R] để tính trạng thái của node cha [L, R], và từ đó trả lời được truy vấn đếm reachable.

5. Định nghĩa trạng thái Segment Tree và phép Merge:

• Đối với bài toán đếm số nút reachable từ gốc của đoạn con (trong cây phẳng) chỉ qua các nút bật, trạng thái phổ biến cho node Segment Tree trên đoạn [L, R] bao gồm:

  • count: Số lượng nút u = nodes_in_dfs_order[i] với L <= i <= R sao cho u đang bật VÀ đường đi từ nút nodes_in_dfs_order[L] đến u (chỉ sử dụng các nút nodes_in_dfs_order[j] với L <= j <= i và tất cả chúng đều bật) là hoàn toàn bật.
  • is_fully_on_prefix: Boolean, true nếu tất cả các nút nodes_in_dfs_order[i] với L <= i <= R MÀ NẰM TRÊN "đường đi chính" của quá trình duyệt DFS từ nodes_in_dfs_order[L] đến nodes_in_dfs_order[R] (trong phạm vi các index L đến R) đều đang bật. Đây là thuộc tính cho phép "lan truyền" khả năng reachable từ đoạn con bên trái sang đoạn con bên phải.

• Phép Merge của node cha [L, R] từ hai con trái [L, M] và con phải [M+1, R]:

  • new_count = left.count: Các nút reachable trong đoạn con trái từ nodes_in_dfs_order[L] vẫn reachable.
  • Nếu left.is_fully_on_prefix là true (tức là đoạn prefix trong con trái hoàn toàn bật, cho phép kết nối), ta cộng thêm right.count: Các nút reachable trong đoạn con phải từ nodes_in_dfs_order[M+1] trở thành reachable từ nodes_in_dfs_order[L] thông qua đoạn prefix bật của con trái.
  • new_is_fully_on_prefix = left.is_fully_on_prefix && right.is_fully_on_prefix: Đoạn prefix của node cha hoàn toàn bật chỉ khi cả hai đoạn prefix của con trái và con phải đều hoàn toàn bật.

• Trạng thái lá (Leaf Node) [i, i]:

  • count = is_on_arr[i]: Chỉ có nút nodes_in_dfs_order[i] là reachable từ chính nó nếu nó bật.
  • is_fully_on_prefix = is_on_arr[i]: Đoạn prefix 1 nút hoàn toàn bật nếu nút đó bật.

6. Thực hiện truy vấn và cập nhật:

• Xây dựng (Build): Xây dựng Segment Tree từ mảng is_on_arr bằng đệ quy, bắt đầu từ gốc (đoạn [1, n]).
• Cập nhật (Update) loại 1 tại v:
  • Lật trạng thái light_state[v].
  • Cập nhật giá trị tại vị trí tin[v] trong mảng is_on_arr: is_on_arr[tin[v]] = 1 - is_on_arr[tin[v]].
  • Thực hiện cập nhật điểm trên Segment Tree tại index tin[v].
• Truy vấn (Query) loại 2 tại v:
  • Trước tiên, kiểm tra trạng thái của đỉnh v. Nếu light_state[v] là 0 (tắt), trả về 0 ngay lập tức, vì không thể bắt đầu đường đi từ đỉnh tắt.
  • Nếu light_state[v] là 1 (bật), thực hiện truy vấn đoạn trên Segment Tree trên khoảng index [tin[v], tin[v] + subtree_size[v] - 1] (hoặc [tin[v], tout[v]] tùy cách tính tout). Kết quả count từ truy vấn đoạn chính là số đỉnh reachable.

7. Cài đặt:

• Cần cài đặt hàm DFS để tính tin, tout, subtree_size và mảng nodes_in_dfs_order.
• Cần cài đặt cấu trúc Segment Tree với hàm build, update và query sử dụng trạng thái count và is_fully_on_prefix (hoặc tên tương tự) và phép merge đã định nghĩa.
• Cần chú ý đến việc đánh chỉ mục (0-based hay 1-based).

Tóm tắt các bước:

1. DFS từ gốc để đánh số tin, tout, subtree_size và tạo mảng flat_tree_pos (hoặc sử dụng tin làm index trực tiếp).
2. Khởi tạo mảng is_on_arr kích thước n (hoặc n+1) dựa trên tin index, tất cả đều 1.
3. Xây dựng Segment Tree trên mảng is_on_arr với mỗi node lưu count và is_fully_on_prefix. Định nghĩa phép merge và trạng thái lá.
4. Với mỗi truy vấn loại 1 v: Cập nhật light_state[v] và is_on_arr[tin[v]]. Gọi Segment Tree update tại tin[v].
5. Với mỗi truy vấn loại 2 v: Nếu light_state[v] là 0, in 0. Ngược lại, gọi Segment Tree query trên đoạn [tin[v], tin[v] + subtree_size[v] - 1]. In ra kết quả count từ query.

Làm thêm nhiều bài tập miễn phí tại đây