Bài 30.1. Khái niệm và cài đặt cơ bản Segment Tree

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng tìm hiểu về một cấu trúc dữ liệu cực kỳ mạnh mẽ và quen thuộc trong thế giới lập trình thi đấu: Segment Tree, hay còn gọi là Cây Đoạn.

Tại sao Segment Tree lại quan trọng đến vậy? Hãy tưởng tượng bạn có một mảng lớn chứa hàng triệu phần tử. Các bài toán phổ biến trên mảng thường yêu cầu bạn thực hiện hai loại thao tác chính:

Truy vấn trên đoạn (Range Query): Tính tổng, tìm giá trị nhỏ nhất, lớn nhất, hoặc một thuộc tính nào đó trên một đoạn con liên tục của mảng (từ chỉ số l đến r).
Cập nhật điểm (Point Update): Thay đổi giá trị của một phần tử tại một chỉ số cụ thể.

Với một mảng thông thường, truy vấn trên đoạn có thể mất thời gian O(N) (với N là kích thước mảng), và cập nhật điểm thì rất nhanh O(1). Tuy nhiên, nếu bạn cần thực hiện rất nhiều truy vấn và cập nhật, O(N) cho mỗi truy vấn sẽ trở thành nút thắt cổ chai khổng lồ.

Segment Tree ra đời để giải quyết vấn đề này. Nó cho phép chúng ta thực hiện cả truy vấn trên đoạn và cập nhật điểm chỉ trong thời gian O(log N)! Đây là một sự cải thiện đáng kinh ngạc, đặc biệt khi N rất lớn.

Khái niệm Segment Tree là gì?

Segment Tree là một cấu trúc dữ liệu dạng cây nhị phân (binary tree) được sử dụng để lưu trữ thông tin về các đoạn hoặc khoảng trên một mảng.

Mỗi nút trên cây Segment Tree đại diện cho một đoạn con liên tục của mảng gốc.
Nút gốc (root) của cây đại diện cho toàn bộ mảng gốc (đoạn từ chỉ số 0 đến N-1).
Nếu một nút đại diện cho đoạn [l, r], thì nút con bên trái của nó sẽ đại diện cho nửa đầu của đoạn đó, tức là [l, (l+r)/2], và nút con bên phải đại diện cho nửa sau, tức là [(l+r)/2 + 1, r].
Quá trình phân chia đoạn này diễn ra một cách đệ quy cho đến khi đoạn chỉ còn một phần tử. Các nút đại diện cho đoạn chỉ gồm một phần tử chính là các nút lá (leaf nodes) của cây, và chúng tương ứng trực tiếp với các phần tử của mảng gốc.

Ví dụ minh họa (tưởng tượng): Nếu mảng gốc có 8 phần tử (chỉ số 0 đến 7).

Nút gốc: đại diện cho đoạn [0, 7].
Con trái nút gốc: đại diện cho đoạn [0, 3]. Con phải: [4, 7].
Con trái của [0, 3]: [0, 1]. Con phải của [0, 3]: [2, 3].
...
Các nút lá: [0], [1], [2], [3], [4], [5], [6], [7].

Tại mỗi nút, chúng ta lưu trữ một thông tin nào đó về đoạn mà nút đó đại diện. Thông tin này phụ thuộc vào bài toán cụ thể bạn muốn giải. Ví dụ:

Nếu bài toán là Range Sum Query (truy vấn tổng trên đoạn), mỗi nút sẽ lưu tổng của tất cả các phần tử trong đoạn nó đại diện.
Nếu bài toán là Range Minimum Query (truy vấn giá trị nhỏ nhất trên đoạn), mỗi nút sẽ lưu giá trị nhỏ nhất trong đoạn đó.
Tương tự với giá trị lớn nhất, GCD, v.v.

Để tính toán thông tin cho một nút cha, ta chỉ cần kết hợp thông tin từ hai nút con của nó. Ví dụ, tổng của đoạn [l, r] bằng tổng của đoạn [l, mid] cộng với tổng của đoạn [mid+1, r]. Giá trị nhỏ nhất của đoạn [l, r] bằng min của giá trị nhỏ nhất của đoạn [l, mid] và giá trị nhỏ nhất của đoạn [mid+1, r].

Độ cao của Segment Tree trên một mảng N phần tử là O(log N). Điều này là do mỗi lần ta đi xuống một tầng, kích thước đoạn được chia đôi.

Kích thước của mảng dùng để lưu trữ cây Segment Tree thường gấp khoảng 4 lần kích thước mảng gốc (N). Điều này là để đảm bảo có đủ không gian cho tất cả các nút trên cây, kể cả trong trường hợp cây không hoàn toàn cân bằng. Nếu mảng gốc có kích thước N, cây sẽ có khoảng 2N-1 nút. Tuy nhiên, do cách đánh chỉ số nút trong mảng (thường sử dụng 1-based indexing và con trái là 2*v, con phải là 2*v+1), chúng ta cần một mảng có kích thước ít nhất là 4*N để tránh tràn bộ nhớ trong các trường hợp đặc biệt hoặc chỉ đơn giản là an toàn.

Cài đặt Cơ bản: Build, Query, Update

Để cài đặt Segment Tree, chúng ta thường sử dụng một mảng một chiều để lưu trữ các nút của cây. Giả sử mảng gốc là arr có kích thước N. Mảng lưu cây là tree có kích thước 4*N. Ta có thể sử dụng 1-based indexing cho các nút cây, với nút gốc là 1. Nếu nút v đại diện cho đoạn [tl, tr], thì con trái là 2*v đại diện cho [tl, tm] và con phải là 2*v+1 đại diện cho [tm+1, tr], trong đó tm = (tl + tr) / 2.

Chúng ta sẽ minh họa cài đặt cho bài toán Range Sum Query (truy vấn tổng trên đoạn) và Point Update (cập nhật giá trị tại một điểm).

1. Hàm `build` (Xây dựng cây)

Hàm build(v, tl, tr) sẽ xây dựng cây Segment Tree cho đoạn [tl, tr] của mảng gốc, bắt đầu từ nút v.

Tham số:
- v: Chỉ số của nút hiện tại trong mảng tree.
- tl: Chỉ số bắt đầu của đoạn con mà nút v đại diện trong mảng gốc.
- tr: Chỉ số kết thúc của đoạn con mà nút v đại diện trong mảng gốc.
Logic:
- Trường hợp cơ sở (Base Case): Nếu tl == tr, tức là đoạn chỉ có một phần tử, nút v là nút lá. Giá trị của tree[v] chính là giá trị của arr[tl] (hoặc arr[tr]).
- Trường hợp đệ quy: Nếu tl != tr, ta chia đoạn [tl, tr] thành hai nửa: [tl, tm] và [tm+1, tr], với tm = (tl + tr) / 2. Ta gọi đệ quy để xây dựng cây con bên trái (build(2*v, tl, tm)) và cây con bên phải (build(2*v+1, tm+1, tr)). Sau khi hai cây con được xây dựng xong, giá trị của nút hiện tại tree[v] sẽ là tổng của giá trị hai nút con: tree[v] = tree[2*v] + tree[2*v+1].

Đây là mã C++ cho hàm build:

#include <vector>
#include <iostream>

// Giả sử arr là mảng gốc, tree là mảng lưu Segment Tree
std::vector<int> arr;
std::vector<long long> tree; // Sử dụng long long cho tổng để tránh tràn số

// Kích thước mảng gốc
int n;

// Hàm xây dựng cây Segment Tree
// v: chỉ số nút hiện tại trong mảng tree
// tl, tr: đoạn mà nút v đại diện trong mảng gốc arr [tl, tr]
void build(int v, int tl, int tr) {
    if (tl == tr) {
        // Trường hợp cơ sở: nút lá
        tree[v] = arr[tl];
    } else {
        // Trường hợp đệ quy: chia đôi đoạn
        int tm = (tl + tr) / 2;
        // Xây dựng cây con trái cho đoạn [tl, tm]
        build(2*v, tl, tm);
        // Xây dựng cây con phải cho đoạn [tm+1, tr]
        build(2*v+1, tm+1, tr);
        // Giá trị của nút hiện tại là tổng của hai nút con
        tree[v] = tree[2*v] + tree[2*v+1];
    }
}

// Cách sử dụng hàm build trong hàm main hoặc sau khi khởi tạo:
// Giả sử arr đã được nạp dữ liệu và n là kích thước của arr
// tree.resize(4 * n); // Khởi tạo kích thước mảng tree
// build(1, 0, n - 1); // Bắt đầu xây dựng từ nút gốc (chỉ số 1), cho toàn bộ mảng [0, n-1]

Giải thích code:

#include <vector> và #include <iostream>: Bao gồm thư viện cần thiết.
arr: Mảng gốc chứa dữ liệu ban đầu.
tree: Mảng lưu Segment Tree. Kích thước 4*n là kích thước an toàn.
n: Kích thước của mảng gốc.
build(v, tl, tr):
- v: Chỉ số của nút hiện tại trong mảng tree. Ta dùng 1-based index nên nút gốc là 1.
- tl, tr: Biên của đoạn con trong mảng arr mà nút v quản lý.
- if (tl == tr): Đây là trường hợp nút lá, đoạn chỉ có 1 phần tử (tl đến tl). Giá trị của nút lá bằng giá trị của phần tử tương ứng trong mảng arr.
- else: Nút hiện tại không phải lá. Ta tìm điểm giữa tm = (tl + tr) / 2.
- build(2*v, tl, tm): Gọi đệ quy để xây dựng cây con trái. Nút con trái của v là 2*v, quản lý đoạn [tl, tm].
- build(2*v+1, tm+1, tr): Gọi đệ quy để xây dựng cây con phải. Nút con phải của v là 2*v+1, quản lý đoạn [tm+1, tr].
- tree[v] = tree[2*v] + tree[2*v+1]: Sau khi hai cây con được xây dựng và tính toán xong giá trị của chúng, giá trị của nút hiện tại v (đại diện cho đoạn [tl, tr]) là tổng giá trị của hai cây con (đoạn [tl, tm] và [tm+1, tr]).

Độ phức tạp của hàm build là O(N), vì mỗi nút trên Segment Tree được thăm đúng một lần.

2. Hàm `query` (Truy vấn trên đoạn)

Hàm query(v, tl, tr, l, r) sẽ tính toán kết quả (ví dụ: tổng) trên đoạn [l, r] của mảng gốc, sử dụng thông tin từ cây con gốc v đại diện cho đoạn [tl, tr].

Tham số:
- v: Chỉ số của nút hiện tại trong mảng tree.
- tl, tr: Đoạn mà nút v đại diện trong mảng gốc ([tl, tr]).
- l, r: Đoạn truy vấn cần tính toán kết quả ([l, r]).
Logic:
- Trường hợp 1: Đoạn của nút hiện tại nằm hoàn toàn bên ngoài đoạn truy vấn. Tức là tr < l hoặc tl > r. Trong trường hợp này, đoạn của nút v không đóng góp gì vào kết quả của đoạn truy vấn [l, r]. Ta trả về một giá trị trung lập (identity element) đối với phép toán đang dùng (ví dụ: 0 cho phép cộng, vô cùng lớn cho phép min, vô cùng bé cho phép max).
- Trường hợp 2: Đoạn của nút hiện tại nằm hoàn toàn bên trong đoạn truy vấn. Tức là l <= tl và tr <= r. Trong trường hợp này, toàn bộ đoạn [tl, tr] nằm trong đoạn truy vấn [l, r]. Giá trị của nút tree[v] chính là kết quả cần tìm cho đoạn này. Ta trả về tree[v].
- Trường hợp 3: Đoạn của nút hiện tại giao với đoạn truy vấn. Tức là có sự chồng lấn nhưng không hoàn toàn nằm trong hoặc ngoài. Trong trường hợp này, ta cần đệ quy xuống cả hai cây con (trái và phải). Kết quả cuối cùng sẽ là kết hợp kết quả từ truy vấn trên cây con trái và truy vấn trên cây con phải đối với đoạn truy vấn [l, r]. Ta tính điểm giữa tm = (tl + tr) / 2. Truy vấn cây con trái: query(2*v, tl, tm, l, r). Truy vấn cây con phải: query(2*v+1, tm+1, tr, l, r). Kết quả là tổng của hai kết quả đệ quy này.

Đây là mã C++ cho hàm query:

// Hàm truy vấn tổng trên đoạn [l, r] trong mảng gốc
// v: chỉ số nút hiện tại trong mảng tree
// tl, tr: đoạn mà nút v đại diện trong mảng gốc [tl, tr]
// l, r: đoạn truy vấn cần tính tổng [l, r]
long long query(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        // Đoạn truy vấn không hợp lệ hoặc nút hiện tại nằm ngoài đoạn truy vấn
        // Trả về giá trị trung lập cho phép cộng (0)
        return 0;
    }
    if (l == tl && r == tr) {
        // Đoạn của nút hiện tại khớp hoàn toàn với đoạn truy vấn
        return tree[v];
    }
    // Đoạn của nút hiện tại giao với đoạn truy vấn
    int tm = (tl + tr) / 2;
    // Truy vấn cây con trái cho phần giao với đoạn [l, r]
    // min(r, tm): giới hạn đoạn truy vấn không vượt quá biên phải của cây con trái (tm)
    // max(l, tl): giới hạn đoạn truy vấn không nhỏ hơn biên trái của cây con trái (tl)
    long long sum_left = query(2*v, tl, tm, l, std::min(r, tm));
    // Truy vấn cây con phải cho phần giao với đoạn [l, r]
    // min(r, tr): giới hạn đoạn truy vấn không vượt quá biên phải của cây con phải (tr)
    // max(l, tm + 1): giới hạn đoạn truy vấn không nhỏ hơn biên trái của cây con phải (tm + 1)
    long long sum_right = query(2*v+1, tm+1, tr, std::max(l, tm + 1), r);

    return sum_left + sum_right;
}

// Cách sử dụng hàm query:
// long long total_sum = query(1, 0, n - 1, query_l, query_r); // Truy vấn tổng trên đoạn [query_l, query_r]

Giải thích code:

query(v, tl, tr, l, r):
- v, tl, tr: Tương tự như hàm build, xác định nút hiện tại và đoạn nó quản lý.
- l, r: Biên của đoạn mà chúng ta thực sự muốn tính tổng.
- if (l > r): Kiểm tra này cần thiết vì khi đệ quy, các đoạn con truy vấn có thể trở nên không hợp lệ (ví dụ, đoạn truy vấn là [3, 5], cây con trái quản lý [0, 2]. Khi truy vấn xuống cây con trái, ta cần truy vấn đoạn [3, min(5, 2)] = [3, 2], là đoạn không hợp lệ). Ta trả về 0, là phần tử trung hòa của phép cộng.
- if (l == tl && r == tr): Nếu đoạn truy vấn [l, r] trùng khớp với đoạn [tl, tr] mà nút v quản lý, ta đã tìm thấy nút chứa thông tin chính xác cho đoạn đó. Trả về tree[v].
- else: Đoạn truy vấn [l, r] giao với đoạn [tl, tr]. Ta chia đoạn [tl, tr] thành hai nửa [tl, tm] và [tm+1, tr].
- query(2*v, tl, tm, l, std::min(r, tm)): Đệ quy xuống cây con trái (2*v), quản lý đoạn [tl, tm]. Đoạn truy vấn thực sự cho cây con trái là phần giao của [l, r] và [tl, tm], tức là [max(l, tl), min(r, tm)]. Ở đây, vì ta đã kiểm tra l > r ở đầu hàm, nên chỉ cần dùng std::min(r, tm) cho biên phải mới. Biên trái vẫn là l vì nó bị giới hạn bởi max(l, tl) bên trong hàm đệ quy tiếp theo nếu cần, nhưng ở đây ta đơn giản hóa thành l, std::min(r, tm).
- query(2*v+1, tm+1, tr, std::max(l, tm+1), r): Tương tự, đệ quy xuống cây con phải (2*v+1), quản lý đoạn [tm+1, tr]. Đoạn truy vấn thực sự là [max(l, tm+1), min(r, tr)]. Ta đơn giản hóa thành std::max(l, tm+1), r.
- return sum_left + sum_right: Tổng kết quả từ hai cây con chính là tổng trên đoạn truy vấn [l, r] trong đoạn [tl, tr].

Độ phức tạp của hàm query là O(log N). Mỗi lần đệ quy, ta chỉ đi xuống các nút mà đoạn của chúng giao với đoạn truy vấn. Số lượng các nút như vậy trên mỗi tầng của cây là cố định (ít nhất là 1, nhiều nhất là 2), và cây có độ cao log N.

3. Hàm `update` (Cập nhật điểm)

Hàm update(v, tl, tr, pos, new_val) sẽ cập nhật giá trị của phần tử tại chỉ số pos trong mảng gốc thành new_val, và điều chỉnh các nút trên cây Segment Tree bị ảnh hưởng bởi sự thay đổi này.

Tham số:
- v: Chỉ số của nút hiện tại trong mảng tree.
- tl, tr: Đoạn mà nút v đại diện trong mảng gốc ([tl, tr]).
- pos: Chỉ số của phần tử trong mảng gốc cần cập nhật.
- new_val: Giá trị mới của phần tử tại pos.
Logic:
- Trường hợp cơ sở (Base Case): Nếu tl == tr, tức là nút v là nút lá và nó đại diện cho phần tử tại chỉ số tl (hoặc tr). Nếu tl == pos, ta đã đến đúng vị trí cần cập nhật. Cập nhật giá trị của nút lá tree[v] = new_val. Ta cũng nên cập nhật giá trị trong mảng gốc arr[pos] = new_val nếu muốn mảng gốc luôn đồng bộ với cây.
- Trường hợp đệ quy: Nếu tl != tr, nút v không phải lá. Ta cần xác định pos nằm ở cây con trái hay cây con phải. Tính điểm giữa tm = (tl + tr) / 2.
  - Nếu pos <= tm, phần tử cần cập nhật nằm trong đoạn của cây con trái ([tl, tm]). Ta gọi đệ quy update(2*v, tl, tm, pos, new_val).
  - Nếu pos > tm, phần tử cần cập nhật nằm trong đoạn của cây con phải ([tm+1, tr]). Ta gọi đệ quy update(2*v+1, tm+1, tr, pos, new_val).
- Sau khi gọi đệ quy để cập nhật ở cây con tương ứng, giá trị của nút hiện tại tree[v] có thể đã thay đổi (vì giá trị của một trong các con đã thay đổi). Ta cần cập nhật lại giá trị của tree[v] bằng cách kết hợp giá trị mới của hai nút con: tree[v] = tree[2*v] + tree[2*v+1]. Bước này cực kỳ quan trọng để đảm bảo tính đúng đắn của cây.

Đây là mã C++ cho hàm update:

// Hàm cập nhật giá trị tại chỉ số pos trong mảng gốc thành new_val
// v: chỉ số nút hiện tại trong mảng tree
// tl, tr: đoạn mà nút v đại diện trong mảng gốc [tl, tr]
// pos: chỉ số cần cập nhật trong mảng gốc
// new_val: giá trị mới
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        // Trường hợp cơ sở: đến nút lá tương ứng với pos
        tree[v] = new_val; // Cập nhật giá trị nút lá
        // Có thể cập nhật cả arr[pos] nếu muốn đồng bộ mảng gốc
        // arr[pos] = new_val;
    } else {
        // Trường hợp đệ quy: tìm đường đi xuống nút lá
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            // pos nằm ở cây con trái
            update(2*v, tl, tm, pos, new_val);
        } else {
            // pos nằm ở cây con phải
            update(2*v+1, tm+1, tr, pos, new_val);
        }
        // Sau khi cập nhật ở dưới, cập nhật lại giá trị của nút hiện tại
        tree[v] = tree[2*v] + tree[2*v+1];
    }
}

// Cách sử dụng hàm update:
// update(1, 0, n - 1, update_pos, updated_value); // Cập nhật phần tử tại update_pos thành updated_value

Giải thích code:

update(v, tl, tr, pos, new_val):
- v, tl, tr: Tương tự như các hàm trên.
- pos: Chỉ số trong mảng gốc cần thay đổi.
- new_val: Giá trị mới của phần tử tại pos.
- if (tl == tr): Nếu nút hiện tại là lá, nó đại diện cho đoạn chỉ tl. Nếu tl đúng là pos, ta đã đến đúng vị trí cần cập nhật. Cập nhật giá trị trong tree[v].
- else: Nếu không phải lá, ta tìm điểm giữa tm. Dựa vào pos so với tm, ta xác định được pos nằm ở cây con trái hay phải và gọi đệ quy tương ứng.
- tree[v] = tree[2*v] + tree[2*v+1]: Đây là bước quan trọng. Sau khi gọi đệ quy và giá trị ở cây con đã được cập nhật (đến tận nút lá), các nút trên đường đi từ nút lá lên gốc cần được cập nhật lại giá trị của chúng. Nút v cần tính lại giá trị dựa trên giá trị mới nhất của hai nút con 2*v và 2*v+1. Thao tác này đảm bảo thông tin trong cây Segment Tree luôn chính xác.

Độ phức tạp của hàm update là O(log N), vì mỗi lần đệ quy ta chỉ đi xuống một trong hai cây con (cây chứa chỉ số pos). Do đó, ta chỉ đi qua log N nút trên đường từ gốc đến nút lá tương ứng với pos.

4. Cấu trúc hoàn chỉnh và Ví dụ

Để sử dụng Segment Tree, bạn thường khai báo mảng arr và tree (toàn cục hoặc trong một struct/class), sau đó gọi build một lần để xây dựng cây ban đầu, và gọi query hoặc update nhiều lần tùy theo yêu cầu bài toán.

Dưới đây là một ví dụ hoàn chỉnh sử dụng Segment Tree để giải bài toán Range Sum Query và Point Update:

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::min và std::max

// Kích thước tối đa của mảng gốc (hoặc n)
const int MAXN = 100005;

// Mảng gốc
std::vector<int> arr;
// Mảng lưu Segment Tree. Kích thước 4 * MAXN để đảm bảo an toàn
std::vector<long long> tree;
// Kích thước thực tế của mảng gốc
int n;

// Hàm xây dựng cây Segment Tree
// v: chỉ số nút hiện tại trong mảng tree (1-based index)
// tl, tr: đoạn mà nút v đại diện trong mảng gốc arr [tl, tr]
void build(int v, int tl, int tr) {
    if (tl == tr) {
        // Trường hợp cơ sở: nút lá
        tree[v] = arr[tl];
    } else {
        // Trường hợp đệ quy: chia đôi đoạn
        int tm = (tl + tr) / 2;
        // Xây dựng cây con trái cho đoạn [tl, tm]
        build(2*v, tl, tm);
        // Xây dựng cây con phải cho đoạn [tm+1, tr]
        build(2*v+1, tm+1, tr);
        // Giá trị của nút hiện tại là tổng của hai nút con
        tree[v] = tree[2*v] + tree[2*v+1];
    }
}

// Hàm truy vấn tổng trên đoạn [l, r] trong mảng gốc
// v: chỉ số nút hiện tại trong mảng tree
// tl, tr: đoạn mà nút v đại diện trong mảng gốc [tl, tr]
// l, r: đoạn truy vấn cần tính tổng [l, r]
long long query(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        // Đoạn truy vấn không hợp lệ hoặc nút hiện tại nằm ngoài đoạn truy vấn
        // Trả về giá trị trung lập cho phép cộng (0)
        return 0;
    }
    if (l == tl && r == tr) {
        // Đoạn của nút hiện tại khớp hoàn toàn với đoạn truy vấn
        return tree[v];
    }
    // Đoạn của nút hiện tại giao với đoạn truy vấn
    int tm = (tl + tr) / 2;
    // Truy vấn cây con trái cho phần giao với đoạn [l, r]
    long long sum_left = query(2*v, tl, tm, l, std::min(r, tm));
    // Truy vấn cây con phải cho phần giao với đoạn [l, r]
    long long sum_right = query(2*v+1, tm+1, tr, std::max(l, tm + 1), r);

    return sum_left + sum_right;
}

// Hàm cập nhật giá trị tại chỉ số pos trong mảng gốc thành new_val
// v: chỉ số nút hiện tại trong mảng tree
// tl, tr: đoạn mà nút v đại diện trong mảng gốc [tl, tr]
// pos: chỉ số cần cập nhật trong mảng gốc
// new_val: giá trị mới
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        // Trường hợp cơ sở: đến nút lá tương ứng với pos
        tree[v] = new_val; // Cập nhật giá trị nút lá
        // arr[pos] = new_val; // Có thể cập nhật cả mảng gốc nếu cần
    } else {
        // Trường hợp đệ quy: tìm đường đi xuống nút lá
        int tm = (tl + tr) / 2;
        if (pos <= tm) {
            // pos nằm ở cây con trái
            update(2*v, tl, tm, pos, new_val);
        } else {
            // pos nằm ở cây con phải
            update(2*v+1, tm+1, tr, pos, new_val);
        }
        // Sau khi cập nhật ở dưới, cập nhật lại giá trị của nút hiện tại
        tree[v] = tree[2*v] + tree[2*v+1];
    }
}

int main() {
    // Ví dụ sử dụng:
    // Giả sử mảng gốc là [1, 3, 5, 7, 9, 11]
    arr = {1, 3, 5, 7, 9, 11};
    n = arr.size();

    // Khởi tạo kích thước mảng tree (an toàn là 4*n)
    tree.resize(4 * n);

    // Xây dựng cây Segment Tree
    build(1, 0, n - 1); // Bắt đầu từ nút gốc 1, cho đoạn [0, n-1]

    std::cout << "**Segment Tree được xây dựng xong.**" << std::endl;
    // In ra một vài giá trị nút để kiểm tra (ví dụ: gốc)
    // std::cout << "Root node (sum of [0, 5]): " << tree[1] << std::endl; // Should be 1+3+5+7+9+11 = 36

    // Thực hiện truy vấn
    int ql = 1, qr = 4; // Truy vấn tổng trên đoạn [1, 4] (phần tử thứ 1 đến 4: 3, 5, 7, 9)
    long long result_query = query(1, 0, n - 1, ql, qr);
    std::cout << "*Truy vấn: Tổng trên đoạn [" << ql << ", " << qr << "] là: " << result_query << "*" << std::endl; // Expected: 3 + 5 + 7 + 9 = 24

    // Thực hiện cập nhật
    int up_pos = 2; // Cập nhật phần tử tại chỉ số 2 (số 5)
    int new_value = 10; // Giá trị mới là 10
    std::cout << "*Cập nhật: Thay đổi giá trị tại chỉ số " << up_pos << " thành " << new_value << "*" << std::endl;
    update(1, 0, n - 1, up_pos, new_value); // Cập nhật tại chỉ số 2

    // Thực hiện lại truy vấn trên đoạn tương tự để kiểm tra
    long long result_query_after_update = query(1, 0, n - 1, ql, qr); // Truy vấn tổng trên đoạn [1, 4] sau cập nhật
    std::cout << "*Truy vấn lại: Tổng trên đoạn [" << ql << ", " << qr << "] sau cập nhật là: " << result_query_after_update << "*" << std::endl; // Expected: 3 + 10 + 7 + 9 = 29

    // Thêm một vài truy vấn/cập nhật khác
    int ql2 = 0, qr2 = 5; // Truy vấn toàn bộ mảng
    long long result_query_all = query(1, 0, n-1, ql2, qr2);
    std::cout << "*Truy vấn: Tổng trên đoạn [" << ql2 << ", " << qr2 << "] là: " << result_query_all << "*" << std::endl; // Expected: 1 + 3 + 10 + 7 + 9 + 11 = 41

    int up_pos2 = 0; // Cập nhật phần tử tại chỉ số 0 (số 1)
    int new_value2 = 20; // Giá trị mới là 20
    std::cout << "*Cập nhật: Thay đổi giá trị tại chỉ số " << up_pos2 << " thành " << new_value2 << "*" << std::endl;
    update(1, 0, n - 1, up_pos2, new_value2); // Cập nhật tại chỉ số 0

    long long result_query_all_after_update = query(1, 0, n-1, ql2, qr2); // Truy vấn toàn bộ mảng sau cập nhật
    std::cout << "*Truy vấn lại: Tổng trên đoạn [" << ql2 << ", " << qr2 << "] sau cập nhật là: " << result_query_all_after_update << "*" << std::endl; // Expected: 20 + 3 + 10 + 7 + 9 + 11 = 60


    return 0;
}

Giải thích code ví dụ hoàn chỉnh:

Ta định nghĩa mảng arr ban đầu và biến n là kích thước của nó.
Mảng tree được khai báo với kích thước 4*MAXN để đảm bảo đủ chỗ cho mọi trường hợp kích thước mảng gốc lên tới MAXN. std::vector<long long> được dùng cho tree để chứa tổng, tránh tràn số khi tổng lớn.
Trong main, ta khởi tạo arr và n.
tree.resize(4 * n): Điều chỉnh kích thước của vector tree cho phù hợp với n thực tế.
build(1, 0, n - 1): Gọi hàm build để xây dựng cây. Bắt đầu từ nút gốc (chỉ số 1), quản lý toàn bộ mảng gốc từ chỉ số 0 đến n-1.
Các dòng code tiếp theo minh họa cách gọi hàm query để tính tổng trên đoạn [1, 4] (trong mảng gốc) và hàm update để thay đổi giá trị tại chỉ số 2.
Sau khi cập nhật, ta gọi lại query trên đoạn tương tự để kiểm tra xem kết quả có đúng với giá trị mới hay không.
Các ví dụ truy vấn và cập nhật thêm được đưa ra để minh họa thêm cách sử dụng.

Độ phức tạp

Thời gian:
- Xây dựng (Build): O(N)
- Truy vấn (Query): O(log N)
- Cập nhật (Update): O(log N)
Không gian: O(N) (chính xác hơn là O(4N) cho mảng lưu cây)

Segment Tree là một cấu trúc dữ liệu tuyệt vời khi bạn cần thực hiện nhiều thao tác truy vấn trên đoạn và cập nhật điểm trên cùng một mảng. Nó cân bằng tốt giữa thời gian xây dựng và thời gian thực hiện các thao tác sau đó.

Bài tập ví dụ:

Truy vấn đơn giản

Trong một buổi phỏng vấn tuyển dụng, FullHouse Dev được đưa ra một bài toán về xử lý truy vấn trong mảng dữ liệu. Đây là một tình huống thực tế mà công ty thường gặp khi phân tích dữ liệu kinh doanh.

Bài toán

Cho một mảng có kích thước \(n\) trong đó giá trị của các phần tử là \(0\) hoặc \(1\). Tất cả các phần tử của mảng được đánh số từ vị trí \(0\) đến \(n-1\). Bạn được cho một số truy vấn thuộc một trong hai loại sau:

Loại \(0\): Tìm phần tử gần nhất bên trái và bên phải từ vị trí \(p\) trong mảng có giá trị \(1\).
Loại \(1\): Thay đổi giá trị tại vị trí \(p\) thành \(1\) nếu giá trị trước đó là \(0\), ngược lại giữ nguyên.

Lưu ý quan trọng: Nếu không có vị trí nào có giá trị \(1\) ở bên trái của chỉ số trong truy vấn, in ra -1. Tương tự, nếu không có giá trị \(1\) ở bên phải, in ra -1.

INPUT FORMAT:

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) - số lượng phần tử trong mảng và số lượng truy vấn.
Dòng thứ hai chứa \(n\) số nguyên mô tả mảng ban đầu.
\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả loại truy vấn.

OUTPUT FORMAT:

Với mỗi truy vấn loại \(0\), in ra hai số nguyên là vị trí của phần tử \(1\) gần nhất bên trái và bên phải, cách nhau bởi dấu cách.

Ràng buộc:

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

Ví dụ

INPUT

7 4
1 0 0 0 1 0 1
0 1
0 5
1 2
0 2

OUTPUT

0 4
4 6
0 4

Giải thích

Truy vấn đầu tiên là 0 1: Phần tử \(1\) gần nhất bên trái của vị trí 1 nằm ở vị trí 0, bên phải nằm ở vị trí 4.
Truy vấn thứ hai là 0 5: Phần tử \(1\) gần nhất bên trái của vị trí 5 nằm ở vị trí 4, bên phải nằm ở vị trí 6.
Truy vấn thứ ba là 1 2: Thay đổi giá trị tại vị trí 2 thành 1.
Truy vấn thứ tư là 0 2: Phần tử \(1\) gần nhất bên trái của vị trí 2 nằm ở vị trí 0, bên phải nằm ở vị trí 4. Okay, đây là hướng dẫn giải bài toán "Truy vấn đơn giản" bằng C++ một cách hiệu quả, không cung cấp code hoàn chỉnh:

1. Phân tích bài toán và ràng buộc:

Kích thước mảng n và số lượng truy vấn q lên đến 10^5.
Mảng chỉ chứa 0 hoặc 1.
Truy vấn loại 0: Tìm 1 gần nhất bên trái và bên phải một vị trí p. Cần hiệu quả.
Truy vấn loại 1: Cập nhật giá trị tại p thành 1 (nếu đang là 0). Cập nhật này ảnh hưởng đến các truy vấn loại 0 sau đó.

Với n, q lớn, giải pháp duyệt tuyến tính O(n) cho mỗi truy vấn loại 0 sẽ dẫn đến độ phức tạp O(n*q), quá chậm (~10^10 phép tính). Cần một cách tìm kiếm nhanh hơn, có thể sử dụng cấu trúc dữ liệu phù hợp. Độ phức tạp mong muốn thường là O((n+q) log n) hoặc O((n+q) sqrt n).

2. Ý tưởng chính:

Bài toán yêu cầu tìm các phần tử có giá trị 1 theo vị trí (chỉ mục). Khi các phần tử 1 thay đổi (loại 1), danh sách các vị trí có giá trị 1 cũng thay đổi. Cần một cấu trúc dữ liệu có thể:

Lưu trữ các vị trí của các phần tử có giá trị 1.
Cho phép tìm kiếm hiệu quả (tìm phần tử lớn nhất nhỏ hơn p và nhỏ nhất lớn hơn p).
Cho phép thêm/bớt vị trí một cách hiệu quả khi có cập nhật.

3. Lựa chọn cấu trúc dữ liệu:

Cấu trúc dữ liệu phù hợp nhất cho việc lưu trữ một tập hợp các giá trị (các chỉ mục của số 1) và tìm kiếm các giá trị lân cận (lớn nhất nhỏ hơn, nhỏ nhất lớn hơn) một cách hiệu quả là tập hợp có thứ tự (ordered set), ví dụ như std::set trong C++.

std::set lưu trữ các phần tử theo thứ tự và cho phép các thao tác tìm kiếm, thêm, xóa với độ phức tạp O(log k), trong đó k là số lượng phần tử trong set.

4. Hướng giải chi tiết với std::set:

Khởi tạo:
- Tạo một std::set<int> (hoặc std::unordered_set nếu bạn chỉ cần thêm/xóa nhanh, nhưng std::set cần thiết cho tìm kiếm lân cận có thứ tự). Lưu trữ các chỉ mục i mà mảng ban đầu có giá trị arr[i] == 1. Duyệt mảng ban đầu một lần và chèn các chỉ mục này vào set. Độ phức tạp: O(n log n).
Xử lý truy vấn loại 0 (tìm 1 gần nhất):
- Cho vị trí p. Cần tìm chỉ mục lớn nhất trong set < p và chỉ mục nhỏ nhất trong set > p.
- Sử dụng hàm set.lower_bound(p): Trả về iterator tới phần tử đầu tiên trong set không nhỏ hơn p (tức là >= p).
  - Tìm 1 bên phải: Nếu lower_bound(p) trả về iterator it, thì phần tử sau p là *it nếu it không phải set.end(). Tuy nhiên, lower_bound(p) có thể trả về chính p nếu arr[p] là 1. Ta cần phần tử lớn hơn p. Sử dụng set.upper_bound(p) sẽ trả về iterator tới phần tử đầu tiên lớn hơn p. Nếu upper_bound(p) trả về set.end(), không có 1 nào bên phải; in ra -1. Ngược lại, in ra *upper_bound(p).
  - Tìm 1 bên trái: Bắt đầu từ iterator it = set.lower_bound(p). Phần tử lớn nhất nhỏ hơn p chính là phần tử ngay trước it. Nếu it là set.begin(), không có phần tử nào nhỏ hơn p trong set; in ra -1. Ngược lại, lấy iterator prev_it = std::prev(it) (yêu cầu C++11 trở lên, hoặc dùng it-- nếu cẩn thận với begin()) và in ra *prev_it.
- Độ phức tạp cho mỗi truy vấn loại 0: O(log k), trong đó k là số lượng 1s (k <= n).
Xử lý truy vấn loại 1 (cập nhật):
- Cho vị trí p. Cần thay đổi giá trị tại p thành 1. Trong mô hình này, ta chỉ cần đảm bảo chỉ mục p có trong set nếu nó có giá trị 1.
- Sử dụng set.insert(p). Hàm insert của set chỉ thêm p nếu nó chưa tồn tại. Nếu p đã có trong set (tức là arr[p] đã là 1), hàm không làm gì cả. Nếu p chưa có (tức là arr[p] là 0 và giờ thành 1), nó sẽ được thêm vào. Ta không cần theo dõi mảng gốc arr nữa, set chính là đại diện cho các vị trí có giá trị 1.
- Độ phức tạp cho mỗi truy vấn loại 1: O(log k).

5. Độ phức tạp tổng:

Khởi tạo: O(n log n)
q truy vấn: Mỗi truy vấn O(log n) (vì k <= n). Tổng O(q log n).
Tổng cộng: O((n+q) log n), đáp ứng yêu cầu về thời gian.
Bộ nhớ: O(n) để lưu trữ set (tối đa n phần tử).

6. Lưu ý khi implement:

Sử dụng std::set<int> để lưu trữ các chỉ mục.
Đặc biệt chú ý các trường hợp biên khi dùng iterator của set: begin(), end(), lower_bound(), upper_bound(), std::prev().
Kiểm tra it == set.begin() và it == set.end() để xử lý trường hợp không có 1 bên trái hoặc bên phải (in ra -1).

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

Comments

There are no comments at the moment.