Bài 31.3. Fenwick Tree 2D và các mở rộng cơ bản

Chào mừng các bạn trở lại với series về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen và thấy được sự hiệu quả của Fenwick Tree (hay Binary Indexed Tree - BIT) trong việc xử lý các bài toán cập nhật điểm, truy vấn đoạn trên mảng một chiều, đã đến lúc chúng ta nâng tầm sức mạnh này lên hai chiều.

Các bài toán trên lưới (grid) hay ma trận là vô cùng phổ biến, từ các bài toán tin học cơ bản đến các ứng dụng thực tế như xử lý ảnh, bản đồ số, hay mô phỏng. Khi cần thực hiện các thao tác cập nhật một ô và truy vấn tổng (hoặc một tính chất kết hợp được) trên một khu vực hình chữ nhật, Fenwick Tree 2D chính là một trong những công cụ đáng gờm nhất!

Hãy cùng lặn sâu vào thế giới hai chiều của BIT nhé!

Nhắc Lại Nhanh về Fenwick Tree 1D

Trước khi lao vào 2D, hãy nhắc lại nhanh ý tưởng cốt lõi của BIT 1D. BIT 1D cho phép chúng ta thực hiện hai thao tác chính:

update(index, value): Thêm value vào phần tử tại index.
query(index): Tính tổng tiền tố từ chỉ số 1 đến index.

Cả hai thao tác này đều có độ phức tạp O(log N), nơi N là kích thước mảng. Sự kỳ diệu nằm ở cách nó biểu diễn các tổng tiền tố: mỗi phần tử BIT[i] lưu trữ tổng của một đoạn con có độ dài là i & -i (lowbit của i), kết thúc tại chỉ số i. Khi cập nhật hoặc truy vấn, chúng ta di chuyển qua các chỉ số bằng cách cộng hoặc trừ đi lowbit, tương tự như di chuyển trên cây nhị phân biểu diễn các đoạn.

Từ 1D lên 2D: Ý Tưởng

Giờ, làm thế nào để mở rộng khái niệm này lên hai chiều? Hãy nghĩ về một lưới kích thước N x M. Chúng ta muốn hỗ trợ:

update(x, y, value): Thêm value vào ô (x, y).
query(x, y): Tính tổng của hình chữ nhật có góc trên bên trái là (1, 1) và góc dưới bên phải là (x, y).
query(x1, y1, x2, y2): Tính tổng của hình chữ nhật có góc trên bên trái là (x1, y1) và góc dưới bên phải là (x2, y2).

Ý tưởng chính là áp dụng cơ chế của BIT 1D hai lần, một lần cho mỗi chiều. Thay vì một mảng 1D BIT[N], chúng ta sẽ có một ma trận 2D BIT[N][M]. Phần tử BIT[i][j] sẽ lưu trữ tổng của một hình chữ nhật kết thúc tại (i, j), với kích thước phụ thuộc vào i & -i (theo chiều ngang) và j & -j (theo chiều dọc).

Cấu Trúc Dữ Liệu: Ma Trận BIT 2D

Chúng ta sẽ sử dụng một ma trận BIT kích thước (N+1) x (M+1) để lưu trữ thông tin. Kích thước thêm +1 là để sử dụng chỉ số 1-based indexing, giúp việc tính toán lowbit trở nên thuận tiện hơn, giống như trong BIT 1D.

const int MAXN = 1005; // Kích thước tối đa cho lưới
const int MAXM = 1005;
long long BIT[MAXN][MAXM]; // Sử dụng long long nếu tổng có thể lớn
int N, M; // Kích thước thực tế của lưới

Các Thao Tác Cơ Bản trên Fenwick Tree 2D

1. Cập nhật Điểm (Point Update): `update(x, y, val)`

Để thêm val vào ô (x, y), chúng ta cần đi qua tất cả các ô BIT[i][j] mà "phụ thuộc" vào (x, y). Trong 2D, điều này có nghĩa là tất cả các ô (i, j) sao cho i >= x và j >= y và BIT[i][j] lưu trữ tổng của một vùng bao gồm (x, y).

Quá trình này tương tự như cập nhật trong 1D, nhưng áp dụng đồng thời trên cả hai chiều:

Đối với chiều x (hàng): Chúng ta bắt đầu từ i = x và tăng i bằng i += i & -i cho đến khi vượt quá N.
Đối với chiều y (cột): Với mỗi giá trị i, chúng ta bắt đầu từ j = y và tăng j bằng j += j & -j cho đến khi vượt quá M.

Tại mỗi cặp (i, j) tìm được, chúng ta cộng val vào BIT[i][j].

void update(int x, int y, int val) {
    // Đảm bảo chỉ số nằm trong giới hạn 1..N, 1..M
    if (x <= 0 || x > N || y <= 0 || y > M) return;

    for (int i = x; i <= N; i += i & -i) {
        for (int j = y; j <= M; j += j & -j) {
            BIT[i][j] += val;
        }
    }
}

Giải thích code:

Hàm nhận vào chỉ số x, y (1-based) và giá trị val cần thêm.
Kiểm tra chỉ số để đảm bảo tính hợp lệ.
Vòng lặp ngoài for (int i = x; i <= N; i += i & -i) duyệt qua các chỉ số hàng i từ x trở lên, theo quy luật của BIT 1D.
Vòng lặp trong for (int j = y; j <= M; j += j & -i) duyệt qua các chỉ số cột j từ y trở lên, cũng theo quy luật của BIT 1D, cho mỗi giá trị i.
BIT[i][j] += val; thực hiện cập nhật giá trị tại ô BIT tương ứng.

2. Truy Vấn Tổng Tiền Tố 2D (Prefix Sum 2D): `query(x, y)`

Để tính tổng của hình chữ nhật từ (1, 1) đến (x, y), chúng ta cần cộng lại các giá trị từ các ô BIT[i][j] mà "đóng góp" vào tổng này. Điều này có nghĩa là tất cả các ô BIT[i][j] sao cho i <= x và j <= y.

Quá trình này cũng tương tự như truy vấn trong 1D, áp dụng đồng thời trên hai chiều:

Đối với chiều x: Chúng ta bắt đầu từ i = x và giảm i bằng i -= i & -i cho đến khi i về 0.
Đối với chiều y: Với mỗi giá trị i, chúng ta bắt đầu từ j = y và giảm j bằng j -= j & -j cho đến khi j về 0.

Tại mỗi cặp (i, j) tìm được, chúng ta cộng BIT[i][j] vào kết quả.

long long query(int x, int y) {
    // Đảm bảo chỉ số không âm
    if (x <= 0 || y <= 0) return 0;

    long long sum = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            sum += BIT[i][j];
        }
    }
    return sum;
}

Giải thích code:

Hàm nhận vào chỉ số x, y (1-based, giới hạn trên của hình chữ nhật).
Kiểm tra chỉ số không âm (nếu truyền 0 hoặc âm, tổng tiền tố là 0).
Khởi tạo sum = 0.
Vòng lặp ngoài for (int i = x; i > 0; i -= i & -i) duyệt qua các chỉ số hàng i từ x trở xuống, theo quy luật của BIT 1D.
Vòng lặp trong for (int j = y; j > 0; j -= j & -j) duyệt qua các chỉ số cột j từ y trở xuống, cũng theo quy luật của BIT 1D, cho mỗi giá trị i.
sum += BIT[i][j]; cộng giá trị tại ô BIT tương ứng vào tổng.

3. Truy Vấn Tổng Hình Chữ Nhật Bất Kỳ: `query(x1, y1, x2, y2)`

Để tính tổng của hình chữ nhật có góc trên bên trái là (x1, y1) và góc dưới bên phải là (x2, y2), chúng ta sử dụng nguyên lý bao gồm-loại trừ (inclusion-exclusion).

Tổng của hình chữ nhật (x1, y1) đến (x2, y2) có thể được tính bằng cách:

Tổng tiền tố đến (x2, y2) (query(x2, y2))
Trừ đi tổng tiền tố đến (x1-1, y2) (phần bên trái bị thừa)
Trừ đi tổng tiền tố đến (x2, y1-1) (phần bên trên bị thừa)
Cộng lại tổng tiền tố đến (x1-1, y1-1) (phần góc trên bên trái bị trừ đi hai lần)

Công thức là: query(x2, y2) - query(x1-1, y2) - query(x2, y1-1) + query(x1-1, y1-1).

long long query(int x1, int y1, int x2, int y2) {
    // Đảm bảo chỉ số hợp lệ: x1 <= x2, y1 <= y2
    if (x1 > x2 || y1 > y2) return 0;

    long long res = query(x2, y2);
    if (x1 > 1) res -= query(x1 - 1, y2);
    if (y1 > 1) res -= query(x2, y1 - 1);
    if (x1 > 1 && y1 > 1) res += query(x1 - 1, y1 - 1);

    return res;
}

Giải thích code:

Hàm nhận vào tọa độ (x1, y1) và (x2, y2) của hình chữ nhật.
Kiểm tra tính hợp lệ của tọa độ.
Thực hiện các phép trừ và cộng dựa trên công thức bao gồm-loại trừ, sử dụng hàm query(x, y) đã xây dựng ở trên. Lưu ý kiểm tra x1 > 1 và y1 > 1 để tránh truy vấn với chỉ số 0 hoặc âm.

Độ Phức Tạp

update(x, y, val): Vòng lặp ngoài chạy tối đa log N lần, vòng lặp trong chạy tối đa log M lần. Tổng độ phức tạp là O(log N * log M).
query(x, y): Tương tự, hai vòng lặp lồng nhau, độ phức tạp là O(log N * log M).
query(x1, y1, x2, y2): Gọi 4 lần hàm query(x, y), độ phức tạp vẫn là O(log N * log M).

Với cùng kích thước N x M, việc cập nhật và truy vấn trên lưới 2D bằng phương pháp ngây thơ (duyệt qua toàn bộ hình chữ nhật hoặc cập nhật trực tiếp mảng và tính prefix sums lại) thường mất O(N*M) hoặc O(N) hay O(M). Fenwick Tree 2D cho phép chúng ta làm điều này hiệu quả hơn rất nhiều khi có nhiều thao tác cập nhật và truy vấn xen kẽ.

Ví Dụ Minh Họa 1: Cập nhật ô và Truy vấn tổng hình chữ nhật

Bài toán: Cho một lưới N x M ban đầu toàn số 0. Có hai loại thao tác:

UPDATE x y val: Cộng val vào ô (x, y).
QUERY x1 y1 x2 y2: In ra tổng các giá trị trong hình chữ nhật từ (x1, y1) đến (x2, y2).

#include <iostream>
#include <vector>

const int MAXN = 1005;
const int MAXM = 1005;
long long BIT[MAXN][MAXM];
int N, M;

void update(int x, int y, int val) {
    if (x <= 0 || x > N || y <= 0 || y > M) return;
    for (int i = x; i <= N; i += i & -i) {
        for (int j = y; j <= M; j += j & -j) {
            BIT[i][j] += val;
        }
    }
}

long long query(int x, int y) {
    if (x <= 0 || y <= 0) return 0;
    long long sum = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            sum += BIT[i][j];
        }
    }
    return sum;
}

long long query(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return 0;
    long long res = query(x2, y2);
    if (x1 > 1) res -= query(x1 - 1, y2);
    if (y1 > 1) res -= query(x2, y1 - 1);
    if (x1 > 1 && y1 > 1) res += query(x1 - 1, y1 - 1);
    return res;
}

int main() {
    std::cin >> N >> M; // Đọc kích thước lưới

    int Q; // Số lượng truy vấn
    std::cin >> Q;

    for (int q = 0; q < Q; ++q) {
        char type;
        std::cin >> type;
        if (type == 'U') { // UPDATE
            int x, y, val;
            std::cin >> x >> y >> val;
            update(x, y, val);
        } else if (type == 'Q') { // QUERY
            int x1, y1, x2, y2;
            std::cin >> x1 >> y1 >> x2 >> y2;
            std::cout << query(x1, y1, x2, y2) << std::endl;
        }
    }

    return 0;
}

Giải thích code:

Code bao gồm khai báo mảng BIT, kích thước N, M và các hàm update, query(x, y), query(x1, y1, x2, y2) như đã mô tả.
Trong hàm main, chúng ta đọc kích thước lưới N, M và số lượng truy vấn Q.
Một vòng lặp chạy Q lần, đọc loại thao tác ('U' hoặc 'Q').
Nếu là 'U', đọc x, y, val và gọi update(x, y, val).
Nếu là 'Q', đọc x1, y1, x2, y2 và gọi query(x1, y1, x2, y2), sau đó in kết quả.

Ví dụ input/output: Input:

Output:

15
18

Giải thích:

Lưới 3x3, ban đầu toàn 0.
U 1 1 10: (1,1) = 10.
U 2 2 5: (2,2) = 5.
Q 1 1 2 2: Query hình chữ nhật (1,1) đến (2,2). Các ô trong vùng này là (1,1), (1,2), (2,1), (2,2). Tổng là 10 (tại 1,1) + 0 (tại 1,2) + 0 (tại 2,1) + 5 (tại 2,2) = 15.
U 1 2 3: (1,2) = 3.
Q 1 1 2 2: Query lại hình chữ nhật (1,1) đến (2,2). Tổng là 10 (tại 1,1) + 3 (tại 1,2) + 0 (tại 2,1) + 5 (tại 2,2) = 18.

Ví Dụ Minh Họa 2: Đếm số "đối tượng" trong một vùng

Bài toán: Cho một lưới N x M, ban đầu không có gì. Có hai loại thao tác:

ADD x y: Thêm một đối tượng tại ô (x, y). Nếu đã có, bỏ qua.
COUNT x1 y1 x2 y2: Đếm số lượng đối tượng trong hình chữ nhật từ (x1, y1) đến (x2, y2).

Bài toán này có thể giải quyết bằng 2D BIT. Chúng ta sẽ sử dụng BIT để lưu trữ số lượng đối tượng tại mỗi ô. update(x, y, 1) khi thêm đối tượng, và query(x1, y1, x2, y2) để đếm. Cần thêm một cách để kiểm tra xem ô (x, y) đã có đối tượng chưa để tránh thêm trùng. Một ma trận boolean hoặc map có thể dùng, nhưng nếu giới hạn là chỉ thêm một đối tượng duy nhất tại mỗi ô nếu chưa có, chúng ta có thể kiểm tra giá trị hiện tại của ô đó bằng cách dùng BIT 2D để truy vấn tổng tại chính ô đó ( query(x, y) - query(x-1, y) - query(x, y-1) + query(x-1, y-1) ) trước khi update. Tuy nhiên, cách đơn giản hơn là sử dụng một ma trận boolean has_object[N][M].

#include <iostream>
#include <vector>

const int MAXN = 1005;
const int MAXM = 1005;
long long BIT[MAXN][MAXM];
bool has_object[MAXN][MAXM]; // Mảng để kiểm tra xem ô đã có đối tượng chưa
int N, M;

void update(int x, int y, int val) {
    if (x <= 0 || x > N || y <= 0 || y > M) return;
    for (int i = x; i <= N; i += i & -i) {
        for (int j = y; j <= M; j += j & -j) {
            BIT[i][j] += val;
        }
    }
}

long long query(int x, int y) {
    if (x <= 0 || y <= 0) return 0;
    long long sum = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            sum += BIT[i][j];
        }
    }
    return sum;
}

long long query(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return 0;
    long long res = query(x2, y2);
    if (x1 > 1) res -= query(x1 - 1, y2);
    if (y1 > 1) res -= query(x2, y1 - 1);
    if (x1 > 1 && y1 > 1) res += query(x1 - 1, y1 - 1);
    return res;
}

int main() {
    std::cin >> N >> M; // Đọc kích thước lưới

    // Khởi tạo mảng has_object
    for(int i=1; i<=N; ++i) {
        for(int j=1; j<=M; ++j) {
            has_object[i][j] = false;
        }
    }
    // Mảng BIT được khởi tạo mặc định là 0 global

    int Q; // Số lượng truy vấn
    std::cin >> Q;

    for (int q = 0; q < Q; ++q) {
        std::string type;
        std::cin >> type;
        if (type == "ADD") {
            int x, y;
            std::cin >> x >> y;
            if (!has_object[x][y]) { // Chỉ thêm nếu chưa có
                update(x, y, 1);
                has_object[x][y] = true;
            }
        } else if (type == "COUNT") {
            int x1, y1, x2, y2;
            std::cin >> x1 >> y1 >> x2 >> y2;
            std::cout << query(x1, y1, x2, y2) << std::endl;
        }
    }

    return 0;
}

Giải thích code:

Code tương tự ví dụ 1, nhưng thêm mảng has_object[MAXN][MAXM] để theo dõi các ô đã có đối tượng.
Trong hàm main, mảng has_object được khởi tạo bằng false.
Đối với thao tác "ADD", chúng ta đọc x, y. Nếu has_object[x][y] là false (chưa có đối tượng tại đó), chúng ta gọi update(x, y, 1) để thêm 1 vào ô đó trong BIT và đánh dấu has_object[x][y] = true. Nếu đã có, chúng ta bỏ qua.
Thao tác "COUNT" giống hệt truy vấn tổng trong ví dụ 1, vì mỗi đối tượng được đếm là 1.

Ví dụ input/output: Input:

4 4
6
ADD 1 1
ADD 2 2
COUNT 1 1 2 2
ADD 1 1
ADD 3 3
COUNT 1 1 3 3

Output:

2
3

Giải thích:

Lưới 4x4.
ADD 1 1: Thêm đối tượng tại (1,1). BIT tại (1,1) tăng 1.
ADD 2 2: Thêm đối tượng tại (2,2). BIT tại (2,2) tăng 1.
COUNT 1 1 2 2: Hình chữ nhật (1,1) đến (2,2) chứa (1,1) và (2,2). Mỗi ô có 1 đối tượng. Tổng = 2.
ADD 1 1: (1,1) đã có đối tượng, bỏ qua.
ADD 3 3: Thêm đối tượng tại (3,3). BIT tại (3,3) tăng 1.
COUNT 1 1 3 3: Hình chữ nhật (1,1) đến (3,3) chứa (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3). Các ô có đối tượng là (1,1), (2,2), (3,3). Tổng = 3.

Các Mở Rộng Cơ Bản (Khái quát)

Giống như BIT 1D có thể mở rộng cho các bài toán cập nhật đoạn, truy vấn điểm hoặc cập nhật đoạn, truy vấn đoạn bằng cách sử dụng kỹ thuật mảng hiệu (difference array) và/hoặc nhiều BIT, BIT 2D cũng có các mở rộng tương ứng.

Tuy nhiên, việc triển khai các mở rộng này trong 2D phức tạp hơn đáng kể:

Cập nhật hình chữ nhật, truy vấn điểm: Có thể sử dụng một BIT 2D lưu trữ mảng hiệu 2D. Khi cập nhật hình chữ nhật (x1, y1) đến (x2, y2) với giá trị val, chúng ta cần update(x1, y1, val), update(x1, y2+1, -val), update(x2+1, y1, -val), update(x2+1, y2+1, val) trên BIT hiệu. Khi truy vấn điểm (x, y), chúng ta chỉ cần query(x, y) trên BIT hiệu.
Cập nhật hình chữ nhật, truy vấn hình chữ nhật: Đây là trường hợp phức tạp nhất. Nó đòi hỏi sử dụng bốn BIT 2D để lưu trữ các dạng mảng hiệu khác nhau. Công thức truy vấn và cập nhật trở nên khá dài dòng và khó nhớ.

Với mục tiêu giữ bài viết tập trung vào những kiến thức "cơ bản" và "mở rộng cơ bản" nhất của BIT 2D, chúng ta sẽ chỉ dừng lại ở việc giới thiệu khả năng này và tập trung vào ứng dụng mạnh mẽ và phổ biến nhất của BIT 2D là cập nhật điểm, truy vấn hình chữ nhật. Các biến thể phức tạp hơn thường ít xuất hiện hơn trong các bài toán cơ bản và đòi hỏi sự hiểu biết sâu sắc hơn về mảng hiệu 2D kết hợp với BIT 2D.

Bài tập ví dụ:

Đếm số chẵn và lẻ

Trong một buổi thảo luận về toán học, FullHouse Dev đã được giao một bài toán thú vị. Họ cần phải xử lý một mảng các số tự nhiên và thực hiện một số truy vấn để kiểm tra tính chất của các số trong mảng. Nhiệm vụ của nhóm là giải quyết các truy vấn liên quan đến việc sửa đổi mảng và đếm số lượng số chẵn và số lẻ trong một khoảng cho trước.

Bài toán

FullHouse Dev nhận được một mảng $A$ gồm $N$ số tự nhiên. Họ cần thực hiện các truy vấn sau:

Truy vấn 0: sửa đổi phần tử tại chỉ số $i$ thành $x$.
Truy vấn 1: đếm số lượng số chẵn trong khoảng từ $l$ đến $r$ (bao gồm cả $l$ và $r$).
Truy vấn 2: đếm số lượng số lẻ trong khoảng từ $l$ đến $r$ (bao gồm cả $l$ và $r$).

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên $N$ - số lượng phần tử trong mảng.
Dòng tiếp theo chứa $N$ số tự nhiên - các phần tử của mảng.
Dòng tiếp theo chứa số nguyên $Q$ - số lượng truy vấn, tiếp theo là $Q$ truy vấn.
Mỗi truy vấn có dạng:
- 0 x y - sửa đổi số tại chỉ số $x$ thành $y$.
- 1 x y - đếm số lượng số chẵn trong khoảng từ $l$ đến $r$.
- 2 x y - đếm số lượng số lẻ trong khoảng từ $l$ đến $r$.

OUTPUT FORMAT:

Đối với mỗi truy vấn đếm, in ra kết quả tương ứng.

Ràng buộc:

$1 \leq N, Q \leq 10^5$
$1 \leq l \leq r \leq N$
$0 \leq A[i] \leq 10^9$
$1 \leq x \leq N$
$0 \leq y \leq 10^9$

VÍ DỤ

INPUT

6
1 2 3 4 5 6
4
1 2 5
2 1 4
0 5 4
1 1 6

OUTPUT

2
2
4

Giải thích

Trong ví dụ trên, truy vấn đầu tiên yêu cầu đếm số lượng số chẵn trong khoảng từ 2 đến 5, kết quả là 2. Truy vấn thứ hai yêu cầu đếm số lượng số lẻ trong khoảng từ 1 đến 4, kết quả cũng là 2. Sau khi sửa đổi phần tử tại chỉ số 5 thành 4, truy vấn cuối cùng yêu cầu đếm số lượng số chẵn trong khoảng từ 1 đến 6, kết quả là 4. Bài toán này yêu cầu thực hiện các thao tác cập nhật trên một mảng và đếm số lượng số chẵn/lẻ trong một khoảng cho trước. Với ràng buộc $N, Q \leq 10^5$, một phương pháp duyệt mảng trực tiếp cho mỗi truy vấn đếm sẽ có độ phức tạp $O(Q \times N)$, quá chậm.

Chúng ta cần một cấu trúc dữ liệu hỗ trợ cả cập nhật điểm (point update) và truy vấn đoạn (range query) một cách hiệu quả. Các cấu trúc dữ liệu phù hợp cho việc này bao gồm Cây Phân đoạn (Segment Tree) hoặc Cây Fenwick (Binary Indexed Tree - BIT).

Hướng giải sử dụng Cây Phân đoạn (Segment Tree):

Ý tưởng: Xây dựng một cây phân đoạn để lưu trữ thông tin về số chẵn và số lẻ trong các đoạn con của mảng. Mỗi nút trên cây sẽ đại diện cho một đoạn con liên tục của mảng ban đầu.
Thông tin tại mỗi nút: Thay vì lưu tổng giá trị, mỗi nút của cây sẽ lưu trữ một cặp giá trị: số lượng số chẵn và số lượng số lẻ trong đoạn mà nút đó quản lý.
Xây dựng cây (Build):
- Cây được xây dựng đệ quy. Nút lá (leaf node) tương ứng với một phần tử duy nhất trong mảng gốc. Nếu phần tử đó là chẵn, nút lá đó lưu {1, 0} (1 chẵn, 0 lẻ). Nếu là lẻ, lưu {0, 1} (0 chẵn, 1 lẻ).
- Nút cha (internal node) sẽ tổng hợp thông tin từ hai nút con của nó. Nếu nút con trái quản lý đoạn $[L, M]$ có {even_L, odd_L} và nút con phải quản lý đoạn $[M+1, R]$ có {even_R, odd_R}, thì nút cha quản lý đoạn $[L, R]$ sẽ lưu {even_L + even_R, odd_L + odd_R}.
Cập nhật (Update): Khi cần sửa đổi phần tử tại chỉ số $i$ thành giá trị $x$:
- Xác định sự thay đổi về tính chẵn lẻ của phần tử tại chỉ số $i$ (trước và sau cập nhật).
- Đi xuống cây từ gốc đến nút lá tương ứng với chỉ số $i$. Cập nhật thông tin tại nút lá đó dựa trên tính chẵn lẻ mới của $x$.
- Sau khi cập nhật nút lá, đi ngược lên cây đến gốc, cập nhật lại thông tin (số chẵn, số lẻ) tại các nút cha bị ảnh hưởng bằng cách tổng hợp lại từ các nút con.
- Lưu ý: Chỉ số trong đề bài là 1-based, cần xử lý chuyển đổi sang 0-based nếu cần thiết.
Truy vấn (Query): Khi cần đếm số chẵn/lẻ trong khoảng $[l, r]$:
- Sử dụng hàm truy vấn đoạn chuẩn trên cây phân đoạn.
- Hàm truy vấn sẽ trả về cặp {tổng số chẵn, tổng số lẻ} trong đoạn $[l, r]$.
- Nếu truy vấn là loại 1 (đếm chẵn), in ra tổng số chẵn. Nếu là loại 2 (đếm lẻ), in ra tổng số lẻ.
Độ phức tạp:
- Xây dựng cây: $O(N)$
- Cập nhật điểm: $O(\log N)$
- Truy vấn đoạn: $O(\log N)$
- Tổng thời gian cho $Q$ truy vấn: $O(N + Q \log N)$, hiệu quả với ràng buộc đề bài.
- Không gian bộ nhớ: $O(N)$ để lưu cây phân đoạn.

Hướng giải sử dụng Hai Cây Fenwick (BIT):

Ý tưởng: Sử dụng hai cây Fenwick. Một cây BIT_even lưu trữ thông tin về sự xuất hiện của số chẵn, và một cây BIT_odd lưu trữ thông tin về sự xuất hiện của số lẻ.
Thông tin trong BIT: BIT_even[i] (và BIT_odd[i]) sẽ giúp tính tổng tiền tố số chẵn (và số lẻ) cho các chỉ số đến $i$.
Xây dựng: Duyệt qua mảng ban đầu. Nếu $A[i]$ là chẵn, cập nhật BIT_even tại chỉ số $i$ với giá trị 1. Nếu $A[i]$ là lẻ, cập nhật BIT_odd tại chỉ số $i$ với giá trị 1.
Cập nhật: Khi sửa $A[i]$ thành $x$:
- Kiểm tra tính chẵn lẻ của giá trị cũ $A[i]$ và giá trị mới $x$.
- Nếu $A[i]$ cũ là chẵn và $x$ là lẻ: cập nhật BIT_even tại $i$ với $-1$ (giảm count chẵn) và BIT_odd tại $i$ với $1$ (tăng count lẻ).
- Nếu $A[i]$ cũ là lẻ và $x$ là chẵn: cập nhật BIT_odd tại $i$ với $-1$ và BIT_even tại $i$ với $1$.
- Nếu tính chẵn lẻ không đổi, không cần cập nhật BIT.
- Lưu ý: Cần lưu lại giá trị hiện tại của $A[i]$ để biết tính chẵn lẻ cũ khi cập nhật.
Truy vấn: Để đếm số chẵn/lẻ trong khoảng $[l, r]$:
- Đếm số chẵn trong $[l, r]$ = (Tổng chẵn đến $r$) - (Tổng chẵn đến $l-1$). Sử dụng BIT_even để tính tổng tiền tố.
- Đếm số lẻ trong $[l, r]$ = (Tổng lẻ đến $r$) - (Tổng lẻ đến $l-1$). Sử dụng BIT_odd để tính tổng tiền tố.
Độ phức tạp: Tương tự như Segment Tree, $O(\log N)$ cho mỗi thao tác cập nhật và truy vấn, tổng $O(N + Q \log N)$. Không gian $O(N)$.

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

Comments

There are no comments at the moment.