Bài 31.2: Các thao tác cập nhật và truy vấn trên Fenwick 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!

Trong thế giới lập trình thi đấu và giải quyết các bài toán thực tế liên quan đến mảng, chúng ta thường xuyên gặp phải hai yêu cầu cơ bản:

Cập nhật giá trị tại một vị trí cụ thể (Point Update).
Tính tổng các giá trị trong một đoạn (Range Sum Query).

Nếu chỉ cần một trong hai thao tác này, chúng ta có những cách giải quyết đơn giản:

Nếu chỉ cần cập nhật điểm nhanh: Dùng mảng thông thường. Cập nhật O(1), truy vấn tổng đoạn O(N).
Nếu chỉ cần truy vấn tổng đoạn nhanh: Dùng mảng tổng tiền tố (prefix sum array). Cập nhật O(N) (phải tính lại toàn bộ mảng prefix sum), truy vấn tổng đoạn O(1).

Tuy nhiên, khi cả hai thao tác này đều xảy ra thường xuyên và với số lượng lớn, cả hai cách trên đều trở nên kém hiệu quả với độ phức tạp cao. Chúng ta cần một cấu trúc dữ liệu cân bằng được cả cập nhật và truy vấn. Đó chính là lúc Fenwick Tree, hay còn gọi là Binary Indexed Tree (BIT), toả sáng!

Fenwick Tree cho phép chúng ta thực hiện cả hai thao tác: cập nhật giá trị tại một điểm và truy vấn tổng tiền tố (hoặc tổng đoạn) với độ phức tạp chỉ O(log N), trong đó N là kích thước của mảng. Đây là một sự cải thiện đáng kể so với O(N) của các phương pháp naive khi cả hai thao tác đều quan trọng.

Trong bài viết này, chúng ta sẽ đi sâu vào cách thức hoạt động của hai thao tác cốt lõi trên Fenwick Tree: cập nhật (update) và truy vấn (query).

Hiểu về Fenwick Tree (BIT)

Fenwick Tree không phải là một cây theo nghĩa đen với các nút con trỏ như Binary Search Tree hay AVL Tree. Nó là một mảng, nhưng các chỉ số (index) của mảng này được sử dụng một cách thông minh để lưu trữ tổng của các đoạn con xác định trước. Điều đặc biệt là các đoạn con này được chọn dựa trên biểu diễn nhị phân của các chỉ số.

Mỗi phần tử bit[i] trong Fenwick Tree lưu trữ tổng của một đoạn con kết thúc tại chỉ số i. Độ dài của đoạn con này chính là giá trị của lowbit(i).

Toán tử `lowbit(x)`

Đây là "trái tim" của Fenwick Tree. Hàm lowbit(x) trả về giá trị của bit cuối cùng (bit có trọng số thấp nhất) trong biểu diễn nhị phân của x. Ví dụ:

x = 1 (0001) -> lowbit(1) = 1 (0001)
x = 2 (0010) -> lowbit(2) = 2 (0010)
x = 4 (0100) -> lowbit(4) = 4 (0100)
x = 6 (0110) -> lowbit(6) = 2 (0010)
x = 8 (1000) -> lowbit(8) = 8 (1000)

Trong lập trình, lowbit(x) thường được tính bằng biểu thức bitwise: x & (-x). Điều này hoạt động bởi vì biểu diễn nhị phân của -x trong hệ bù 2 là lật hết các bit của x rồi cộng 1. Kết quả là bit thấp nhất của x và -x vẫn giữ nguyên ở vị trí đó, và khi AND lại, chỉ có bit thấp nhất này là 1, còn lại là 0.

Độ dài của đoạn con mà bit[i] lưu trữ chính là lowbit(i). Đoạn con này bắt đầu từ i - lowbit(i) + 1 và kết thúc tại i. Ví dụ (với indexing 1-based):

bit[1] (lowbit(1)=1) lưu tổng đoạn [1-1+1, 1] tức là [1, 1].
bit[2] (lowbit(2)=2) lưu tổng đoạn [2-2+1, 2] tức là [1, 2].
bit[3] (lowbit(3)=1) lưu tổng đoạn [3-1+1, 3] tức là [3, 3].
bit[4] (lowbit(4)=4) lưu tổng đoạn [4-4+1, 4] tức là [1, 4].
bit[6] (lowbit(6)=2) lưu tổng đoạn [6-2+1, 6] tức là [5, 6].
bit[8] (lowbit(8)=8) lưu tổng đoạn [8-8+1, 8] tức là [1, 8].

Lưu ý quan trọng: Fenwick Tree thường được triển khai với indexing 1-based (các chỉ số bắt đầu từ 1 thay vì 0) để việc sử dụng lowbit trở nên tự nhiên và đơn giản hơn. Nếu sử dụng 0-based indexing, cần có một chút điều chỉnh. Trong bài viết này, chúng ta sẽ sử dụng indexing 1-based. Do đó, mảng Fenwick Tree có kích thước lớn hơn mảng gốc một chút (ví dụ: mảng gốc N phần tử từ index 0 đến N-1, BIT cần kích thước N+1 và sử dụng index 1 đến N).

Thao tác 1: Cập nhật (Update)

Giả sử chúng ta muốn thêm một giá trị delta vào phần tử tại chỉ số idx trong mảng gốc (tức là giá trị tại array[idx] thay đổi thành array[idx] + delta). Làm thế nào để cập nhật Fenwick Tree tương ứng?

Khi giá trị tại array[idx] thay đổi, bất kỳ tổng tiền tố nào kết thúc tại các chỉ số lớn hơn hoặc bằng idx đều bị ảnh hưởng. Trong Fenwick Tree, chúng ta cần cập nhật tất cả các phần tử bit[i] mà đoạn con nó lưu trữ chứa chỉ số idx.

Cách thức cập nhật là đi từ chỉ số idx lên "cây". Bắt đầu từ bit[idx], ta cộng delta vào giá trị hiện tại của bit[idx]. Sau đó, ta nhảy đến chỉ số tiếp theo cần cập nhật. Chỉ số tiếp theo này là chỉ số nhỏ nhất lớn hơn idx mà đoạn con của nó bao gồm idx. Chỉ số này được tìm bằng cách cộng thêm lowbit(idx) vào idx: next_idx = idx + lowbit(idx). Ta lặp lại quá trình này cho đến khi vượt ra ngoài kích thước của mảng BIT.

Tại sao lại cộng lowbit(idx)? Biểu diễn nhị phân giúp giải thích điều này. Việc cộng lowbit(idx) sẽ lật các bit sau bit thấp nhất của idx về 0 và lật bit thấp nhất đó lên 1, đưa chúng ta đến chỉ số "cha" tiếp theo trong cấu trúc cây ẩn của BIT mà vẫn "phụ trách" đoạn chứa idx.

Ví dụ minh họa cập nhật

Giả sử mảng gốc có kích thước 8. Ta có mảng BIT bit kích thước 9 (từ index 0 đến 8, sử dụng index 1 đến 8). Ban đầu, BIT rỗng (toàn số 0).

Ta muốn thêm giá trị 5 vào index 3 (update(3, 5)).

Bắt đầu từ idx = 3. lowbit(3) = lowbit(0011_2) = 1 (0001_2).
- Cộng 5 vào bit[3]. bit[3] = 5.
- Chỉ số tiếp theo: 3 + lowbit(3) = 3 + 1 = 4.
Tại idx = 4. lowbit(4) = lowbit(0100_2) = 4 (0100_2).
- Cộng 5 vào bit[4]. bit[4] = 5.
- Chỉ số tiếp theo: 4 + lowbit(4) = 4 + 4 = 8.
Tại idx = 8. lowbit(8) = lowbit(1000_2) = 8 (1000_2).
- Cộng 5 vào bit[8]. bit[8] = 5.
- Chỉ số tiếp theo: 8 + lowbit(8) = 8 + 8 = 16. 16 vượt quá kích thước BIT (8), dừng lại.

Sau khi update(3, 5), mảng BIT sẽ có các giá trị sau (các index khác vẫn là 0): bit: [0, 0, 0, 5, 5, 0, 0, 0, 5] (index 0 bị bỏ qua, đây là 1-based indexing)

C++ Code cho thao tác cập nhật

#include <vector>
#include <iostream>

// Hàm tính lowbit(x)
int lowbit(int x) {
    return x & (-x);
}

// Hàm cập nhật Fenwick Tree (1-based indexing)
// array_size là kích thước mảng gốc (ví dụ 8),
// bit là mảng Fenwick Tree có kích thước array_size + 1
void update(std::vector<int>& bit, int array_size, int idx, int delta) {
    // idx là chỉ số trong mảng gốc (1-based)
    // delta là giá trị muốn thêm vào array[idx]

    // Duyệt từ idx lên các "cha" trong cây BIT ẩn
    for (; idx <= array_size; idx += lowbit(idx)) {
        bit[idx] += delta; // Cộng delta vào các nút BIT bị ảnh hưởng
    }
}

// Hàm khởi tạo Fenwick Tree từ mảng gốc
// array_size là kích thước mảng gốc (ví dụ 8)
// initial_array là mảng gốc (1-based, kích thước array_size + 1, bỏ qua index 0)
std::vector<int> build_fenwick_tree(const std::vector<int>& initial_array, int array_size) {
    std::vector<int> bit(array_size + 1, 0);
    // Khởi tạo bằng cách gọi update cho từng phần tử của mảng gốc
    for (int i = 1; i <= array_size; ++i) {
        update(bit, array_size, i, initial_array[i]);
    }
    return bit;
}

/*
// Để test hàm update:
int main() {
    int array_size = 8;
    // Mảng gốc giả định (chỉ số 1-based)
    std::vector<int> initial_array(array_size + 1, 0); // Khởi tạo với 0
    // Giả sử mảng ban đầu là [0, 1, 2, 3, 4, 5, 6, 7, 8] (index 1-based)
    for(int i = 1; i <= array_size; ++i) initial_array[i] = i;

    // Xây dựng Fenwick Tree từ mảng gốc
    std::vector<int> bit = build_fenwick_tree(initial_array, array_size);

    // In trạng thái BIT sau khi build (chỉ mục 1-based)
    std::cout << "BIT sau khi build:" << std::endl;
    for(int i = 1; i <= array_size; ++i) {
        std::cout << "bit[" << i << "] = " << bit[i] << std::endl;
    }
    // Expected: bit[1]=1, bit[2]=3, bit[3]=3, bit[4]=10, bit[5]=5, bit[6]=11, bit[7]=7, bit[8]=36

    // Thực hiện cập nhật: thêm 5 vào index 3
    std::cout << "\nCap nhat: them 5 vao index 3" << std::endl;
    update(bit, array_size, 3, 5);

    // In trạng thái BIT sau khi update (chỉ mục 1-based)
    std::cout << "\nBIT sau khi update(3, 5):" << std::endl;
    for(int i = 1; i <= array_size; ++i) {
        std::cout << "bit[" << i << "] = " << bit[i] << std::endl;
    }
    // Expected: bit[1]=1, bit[2]=3, bit[3]=3+5=8, bit[4]=10+5=15, bit[5]=5, bit[6]=11, bit[7]=7, bit[8]=36+5=41

    return 0;
}
*/

Giải thích Code Cập nhật:

Hàm lowbit(x): Trả về bit thấp nhất của x sử dụng phép toán bitwise & và unary negation (-).
Hàm update(bit, array_size, idx, delta):
- Nhận vào mảng bit (Fenwick Tree), kích thước mảng gốc array_size, chỉ số idx cần cập nhật, và giá trị delta muốn thêm vào.
- Vòng lặp for (; idx <= array_size; idx += lowbit(idx)) thực hiện việc di chuyển "lên" trong cây BIT. Nó bắt đầu từ idx và ở mỗi bước, cộng thêm lowbit(idx) để nhảy tới chỉ số BIT tiếp theo cần cập nhật. Vòng lặp dừng khi idx vượt quá array_size.
- bit[idx] += delta;: Tại mỗi chỉ số idx trong đường đi, ta cộng delta vào giá trị hiện tại của bit[idx]. Điều này đảm bảo rằng các tổng đoạn được lưu trữ trong BIT bị ảnh hưởng bởi sự thay đổi tại array[idx] đều được cập nhật đúng.
Hàm build_fenwick_tree: Đây là cách phổ biến để khởi tạo BIT từ một mảng gốc. Thay vì tính toán trực tiếp các tổng đoạn, ta bắt đầu với BIT rỗng và "cập nhật" từng phần tử của mảng gốc vào BIT. Mỗi lần gọi update cho một phần tử ban đầu có giá trị v tại index i, ta thực chất thêm giá trị v này vào các tổng đoạn tương ứng trong BIT.

Thao tác 2: Truy vấn Tổng Tiền Tố (Query)

Mục tiêu của thao tác truy vấn là tính tổng của các phần tử từ chỉ số 1 đến chỉ số idx trong mảng gốc (tức là tính array[1] + array[2] + ... + array[idx]). Đây còn gọi là tổng tiền tố S[idx].

Trong Fenwick Tree, mỗi bit[i] lưu tổng của một đoạn con kết thúc tại i với độ dài lowbit(i). Để tính tổng tiền tố đến idx, chúng ta cần cộng lại các giá trị bit[i] của một tập hợp các chỉ số i sao cho các đoạn con tương ứng của chúng bao phủ chính xác đoạn từ 1 đến idx.

Cách thức truy vấn là đi từ chỉ số idx xuống "cây". Bắt đầu với tổng ban đầu là 0. Tại chỉ số idx, ta cộng giá trị của bit[idx] vào tổng. Sau đó, ta nhảy đến chỉ số tiếp theo cần xét. Chỉ số tiếp theo này là chỉ số của đoạn con ngay trước đoạn con kết thúc tại idx trong việc xây dựng tổng tiền tố. Chỉ số này được tìm bằng cách trừ đi lowbit(idx) từ idx: next_idx = idx - lowbit(idx). Ta lặp lại quá trình này cho đến khi chỉ số bằng 0.

Tại sao lại trừ lowbit(idx)? Việc trừ lowbit(idx) sẽ đưa ta đến chỉ số của nút "cha" (hoặc đúng hơn là nút đại diện cho đoạn tổng trước đó) trong cấu trúc cây ẩn của BIT. Bằng cách lặp lại việc trừ lowbit, chúng ta thu thập các đoạn tổng con rời rạc nhưng khi gộp lại sẽ tạo thành tổng chính xác từ 1 đến idx.

Ví dụ minh họa truy vấn

Sử dụng mảng BIT từ ví dụ cập nhật trước, sau khi update(3, 5) lên mảng ban đầu [0, 1, 2, 3, 4, 5, 6, 7, 8]. BIT lúc này là: bit: [0, 1, 3, 8, 15, 5, 11, 7, 41] (index 0 bị bỏ qua)

Ta muốn tính tổng tiền tố đến index 6 (query(6)).

Bắt đầu từ idx = 6. lowbit(6) = lowbit(0110_2) = 2 (0010_2).
- Cộng bit[6] vào tổng. Tổng = bit[6] = 11.
- Chỉ số tiếp theo: 6 - lowbit(6) = 6 - 2 = 4.
Tại idx = 4. lowbit(4) = lowbit(0100_2) = 4 (0100_2).
- Cộng bit[4] vào tổng. Tổng = 11 + bit[4] = 11 + 15 = 26.
- Chỉ số tiếp theo: 4 - lowbit(4) = 4 - 4 = 0.
Tại idx = 0. Dừng lại.

Tổng tiền tố đến index 6 là 26. Kiểm tra lại mảng gốc sau khi update (thêm 5 vào index 3): [0, 1, 2, 3+5, 4, 5, 6, 7, 8] -> [0, 1, 2, 8, 4, 5, 6, 7, 8] (index 1-based) Tổng từ 1 đến 6: 1 + 2 + 8 + 4 + 5 + 6 = 26. Kết quả khớp!

C++ Code cho thao tác truy vấn

#include <vector>
#include <iostream>

// Hàm tính lowbit(x)
// int lowbit(int x) { return x & (-x); } // Đã định nghĩa ở trên

// Hàm truy vấn tổng tiền tố đến chỉ số idx (1-based indexing)
// bit là mảng Fenwick Tree
int query(const std::vector<int>& bit, int idx) {
    // idx là chỉ số trong mảng gốc mà ta muốn tính tổng tiền tố đến đó (1-based)

    int sum = 0;
    // Duyệt từ idx xuống các "cha" trong cây BIT ẩn
    for (; idx > 0; idx -= lowbit(idx)) {
        sum += bit[idx]; // Cộng giá trị của các nút BIT chứa đoạn tổng cần thiết
    }
    return sum;
}

/*
// Để test hàm query cùng với build và update:
// Sử dụng hàm build_fenwick_tree và update từ ví dụ trên

int main() {
    int array_size = 8;
    // Mảng gốc giả định (chỉ số 1-based)
    std::vector<int> initial_array(array_size + 1, 0); // Khởi tạo với 0
    // Giả sử mảng ban đầu là [0, 1, 2, 3, 4, 5, 6, 7, 8] (index 1-based)
    for(int i = 1; i <= array_size; ++i) initial_array[i] = i;

    // Xây dựng Fenwick Tree từ mảng gốc
    std::vector<int> bit = build_fenwick_tree(initial_array, array_size);

    // Thực hiện cập nhật: thêm 5 vào index 3
    update(bit, array_size, 3, 5);

    // Thực hiện truy vấn: tính tổng đến index 6
    int sum_to_6 = query(bit, 6);
    std::cout << "Tong tien to den index 6 (sau update 3): " << sum_to_6 << std::endl; // Expected: 26

    // Thực hiện truy vấn khác: tính tổng đến index 8
    int sum_to_8 = query(bit, 8);
    std::cout << "Tong tien to den index 8 (tong toan bo mang sau update 3): " << sum_to_8 << std::endl; // Expected: sum(1..8) + 5 = 36 + 5 = 41

    // Truy vấn tổng tiền tố đến index 2
    int sum_to_2 = query(bit, 2);
    std::cout << "Tong tien to den index 2 (sau update 3): " << sum_to_2 << std::endl; // Expected: 1 + 2 = 3 (update o index 3 khong anh huong)

    return 0;
}
*/

Giải thích Code Truy vấn:

Hàm query(bit, idx):
- Nhận vào mảng bit (Fenwick Tree) và chỉ số idx mà ta muốn tính tổng tiền tố đến đó.
- Khởi tạo sum = 0.
- Vòng lặp for (; idx > 0; idx -= lowbit(idx)) thực hiện việc di chuyển "xuống" trong cây BIT. Nó bắt đầu từ idx và ở mỗi bước, trừ đi lowbit(idx) để nhảy tới chỉ số BIT tiếp theo cần xét. Vòng lặp dừng khi idx bằng 0.
- sum += bit[idx];: Tại mỗi chỉ số idx trong đường đi, ta cộng giá trị của bit[idx] vào sum. Các giá trị bit[idx] này đại diện cho các đoạn tổng con mà khi kết hợp lại sẽ tạo ra tổng tiền tố chính xác đến chỉ số ban đầu.

Thao tác mở rộng: Truy vấn Tổng Đoạn (Range Sum Query)

Sau khi đã có hàm query tính tổng tiền tố S[idx], việc tính tổng của một đoạn bất kỳ [L, R] (bao gồm các phần tử từ index L đến R) trở nên rất đơn giản.

Tổng đoạn Sum(L, R) chính là tổng tiền tố đến R trừ đi tổng tiền tố đến L-1. Sum(L, R) = S[R] - S[L-1]

Sử dụng hàm query: Sum(L, R) = query(bit, R) - query(bit, L - 1).

Lưu ý: Khi tính query(bit, L - 1), nếu L = 1, thì L - 1 = 0. Hàm query của chúng ta được thiết kế để dừng khi idx bằng 0 và trả về 0, điều này là chính xác vì tổng tiền tố đến index 0 là 0.

C++ Code cho truy vấn tổng đoạn

#include <vector>
#include <iostream>

// Hàm lowbit và query (đã định nghĩa ở trên)
// int lowbit(int x) { return x & (-x); }
// int query(const std::vector<int>& bit, int idx) { ... }

// Hàm truy vấn tổng đoạn từ L đến R (1-based indexing)
// bit là mảng Fenwick Tree
int range_sum_query(const std::vector<int>& bit, int L, int R) {
    if (L > R) return 0; // Xử lý trường hợp L > R

    // Tổng từ L đến R = Tổng từ 1 đến R - Tổng từ 1 đến L-1
    return query(bit, R) - query(bit, L - 1);
}

/*
// Để test hàm range_sum_query:
// Sử dụng hàm build_fenwick_tree và update từ ví dụ trên

int main() {
    int array_size = 8;
    // Mảng gốc giả định (chỉ số 1-based)
    std::vector<int> initial_array(array_size + 1, 0); // Khởi tạo với 0
    // Giả sử mảng ban đầu là [0, 1, 2, 3, 4, 5, 6, 7, 8] (index 1-based)
    for(int i = 1; i <= array_size; ++i) initial_array[i] = i;

    // Xây dựng Fenwick Tree từ mảng gốc
    std::vector<int> bit = build_fenwick_tree(initial_array, array_size);

    // Thực hiện cập nhật: thêm 5 vào index 3
    update(bit, array_size, 3, 5);
    // Mảng gốc lúc này (logic): [0, 1, 2, 8, 4, 5, 6, 7, 8]

    // Truy vấn tổng đoạn từ index 3 đến index 6
    int sum_3_to_6 = range_sum_query(bit, 3, 6);
    std::cout << "Tong doan tu 3 den 6 (sau update 3): " << sum_3_to_6 << std::endl;
    // Expected: 8 + 4 + 5 + 6 = 23

    // Truy vấn tổng đoạn từ index 1 đến index 4
    int sum_1_to_4 = range_sum_query(bit, 1, 4);
    std::cout << "Tong doan tu 1 den 4 (sau update 3): " << sum_1_to_4 << std::endl;
    // Expected: 1 + 2 + 8 + 4 = 15

    // Truy vấn tổng đoạn từ index 5 đến index 7
    int sum_5_to_7 = range_sum_query(bit, 5, 7);
    std::cout << "Tong doan tu 5 den 7 (sau update 3): " << sum_5_to_7 << std::endl;
    // Expected: 5 + 6 + 7 = 18 (khong bi anh huong boi update 3)

    return 0;
}
*/

Giải thích Code Truy vấn Tổng Đoạn:

Hàm range_sum_query(bit, L, R):
- Nhận mảng bit, chỉ số bắt đầu L và chỉ số kết thúc R của đoạn cần tính tổng.
- Gọi hàm query(bit, R) để lấy tổng tiền tố đến R.
- Gọi hàm query(bit, L - 1) để lấy tổng tiền tố đến L-1.
- Trả về hiệu của hai giá trị trên. Đây chính là tổng các phần tử từ L đến R.

Thao tác mở rộng: Truy vấn Giá trị tại một Điểm (Point Query)

Một ứng dụng khác của tổng tiền tố là tìm giá trị của một phần tử tại một chỉ số i cụ thể. Giá trị này chính là tổng tiền tố đến i trừ đi tổng tiền tố đến i-1.

Value(i) = S[i] - S[i-1]

Sử dụng hàm query: Value(i) = query(bit, i) - query(bit, i - 1).

Điều này có thể hơi dư thừa nếu chúng ta chỉ cần đọc giá trị ban đầu, nhưng nó hữu ích nếu chúng ta chỉ duy trì mảng BIT và không lưu trữ mảng gốc.

C++ Code cho truy vấn giá trị tại điểm

#include <vector>
#include <iostream>

// Hàm lowbit và query (đã định nghĩa ở trên)
// int lowbit(int x) { return x & (-x); }
// int query(const std::vector<int>& bit, int idx) { ... }

// Hàm truy vấn giá trị tại chỉ số idx (1-based indexing)
// bit là mảng Fenwick Tree
int point_query(const std::vector<int>& bit, int idx) {
    // Giá trị tại idx = Tổng tiền tố đến idx - Tổng tiền tố đến idx-1
    return query(bit, idx) - query(bit, idx - 1);
}

/*
// Để test hàm point_query:
// Sử dụng hàm build_fenwick_tree và update từ ví dụ trên

int main() {
    int array_size = 8;
    // Mảng gốc giả định (chỉ số 1-based)
    std::vector<int> initial_array(array_size + 1, 0); // Khởi tạo với 0
    // Giả sử mảng ban đầu là [0, 1, 2, 3, 4, 5, 6, 7, 8] (index 1-based)
    for(int i = 1; i <= array_size; ++i) initial_array[i] = i;

    // Xây dựng Fenwick Tree từ mảng gốc
    std::vector<int> bit = build_fenwick_tree(initial_array, array_size);

    // Thực hiện cập nhật: thêm 5 vào index 3
    update(bit, array_size, 3, 5);
    // Mảng gốc lúc này (logic): [0, 1, 2, 8, 4, 5, 6, 7, 8]

    // Truy vấn giá trị tại index 3
    int val_at_3 = point_query(bit, 3);
    std::cout << "Gia tri tai index 3 (sau update): " << val_at_3 << std::endl; // Expected: 8

    // Truy vấn giá trị tại index 5
    int val_at_5 = point_query(bit, 5);
    std::cout << "Gia tri tai index 5 (sau update): " << val_at_5 << std::endl; // Expected: 5

    return 0;
}
*/

Giải thích Code Truy vấn Giá trị tại Điểm:

Hàm point_query(bit, idx):
- Nhận mảng bit và chỉ số idx cần tìm giá trị.
- Gọi hàm query(bit, idx) và query(bit, idx - 1) để lấy hai tổng tiền tố liên tiếp.
- Trả về hiệu của chúng, chính là giá trị tại idx.

Tổng kết về Độ phức tạp

Thời gian:
- update: O(log N)
- query (tổng tiền tố): O(log N)
- range_sum_query (tổng đoạn): O(log N) (vì gọi 2 lần query)
- point_query: O(log N) (vì gọi 2 lần query)
- build_fenwick_tree: O(N log N) (vì gọi update N lần)
Không gian: O(N) (để lưu mảng BIT)

Bài tập ví dụ:

Độ dài tối thiểu

Trong một buổi họp mặt, đội trưởng của FullHouse Dev đã đưa ra một bài toán đầy thách thức cho các thành viên trong nhóm. Họ được yêu cầu tìm cách chọn một đoạn con trong hai mảng để sau khi sắp xếp đoạn con đó, hai mảng sẽ trở nên giống nhau.

Bài toán

FullHouse Dev nhận được hai mảng \(A\) và \(B\) có độ dài \(n\). Họ có thể chọn bất kỳ đoạn con nào trong mỗi mảng và sắp xếp các phần tử trong đoạn con đó theo thứ tự tăng dần. Nhiệm vụ của nhóm là tìm ra độ dài ngắn nhất của đoạn con mà khi chọn, sau khi sắp xếp, mảng \(A\) và \(B\) sẽ trở nên giống nhau. Cả hai mảng \(A\) và \(B\) là các hoán vị của nhau.

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
Dòng đầu tiên của mỗi test case chứa số nguyên \(n\).
Dòng tiếp theo của mỗi test case chứa \(n\) số nguyên - các phần tử của mảng \(A\).
Dòng tiếp theo của mỗi test case chứa \(n\) số nguyên - các phần tử của mảng \(B\).

OUTPUT FORMAT:

Với mỗi test case, in ra độ dài tối thiểu của đoạn con mà FullHouse Dev có thể chọn để khiến \(A\) và \(B\) trở nên giống nhau sau khi thực hiện sắp xếp.

Ràng buộc:

\(1 \leq T \leq 100\)
\(1 \leq n \leq 10^5\)
\(1 \leq A[i], B[i] \leq 10^9\)

Ví dụ

INPUT

OUTPUT

2
3

Giải thích

Ở test case đầu tiên, FullHouse Dev có thể chọn đoạn con từ chỉ số 1 đến 2 (tính theo chỉ số 1). Sau khi sắp xếp đoạn con đó, cả hai mảng sẽ trở nên giống nhau. Vì vậy, đáp án là 2.
Ở test case thứ hai, nhóm có thể chọn đoạn con từ chỉ số 2 đến 4. Sau khi sắp xếp đoạn con đó, mảng \(A\) và \(B\) trở nên giống nhau, nên đáp án là 3. Okay, đây là hướng giải ngắn gọn cho bài toán "Độ dài tối thiểu":

Xác định phạm vi cần xử lý: Bài toán yêu cầu tìm đoạn con có độ dài nhỏ nhất để khi sắp xếp đoạn con đó trong cả hai mảng A và B, chúng trở nên giống nhau. Nếu hai mảng đã giống nhau ngay từ đầu, độ dài cần tìm là 0. Nếu không, chắc chắn có ít nhất một vị trí i mà A[i] != B[i]. Bất kỳ đoạn con nào được chọn để sắp xếp bắt buộc phải bao gồm tất cả các vị trí i mà A[i] != B[i]. Nếu một vị trí khác biệt k nằm ngoài đoạn con được chọn, A[k] và B[k] sẽ không thay đổi, và mảng A và B sẽ không thể giống nhau sau khi sắp xếp.
Tìm điểm bắt đầu và kết thúc tối thiểu: Dựa trên nhận xét trên, đoạn con ngắn nhất phải bắt đầu tại vị trí khác biệt đầu tiên (từ trái sang) và kết thúc tại vị trí khác biệt cuối cùng (từ phải sang).
- Tìm chỉ số l nhỏ nhất sao cho A[l] != B[l].
- Tìm chỉ số r lớn nhất sao cho A[r] != B[r].
Kiểm tra tính đúng đắn: Nếu chúng ta sắp xếp đoạn con từ l đến r trong cả A và B, liệu chúng có trở nên giống nhau không?
- Đối với các chỉ số i < l hoặc i > r, A[i] và B[i] vốn đã bằng nhau và không thay đổi.
- Đối với các chỉ số i từ l đến r: Vì mảng A và B ban đầu là hoán vị của nhau, và các phần tử bên ngoài đoạn [l, r] là giống hệt nhau ở cả hai mảng, nên tập hợp các phần tử bên trong đoạn [l, r] ở mảng A phải là hoán vị của tập hợp các phần tử bên trong đoạn [l, r] ở mảng B. Khi hai tập hợp có cùng các phần tử được sắp xếp tăng dần, kết quả thu được sẽ giống hệt nhau.
- Do đó, sau khi sắp xếp A[l...r] và B[l...r], A[i] sẽ bằng B[i] cho tất cả các i từ l đến r.
Kết luận: Độ dài tối thiểu của đoạn con cần sắp xếp là r - l + 1. Nếu không tìm thấy vị trí khác biệt nào (l không được tìm thấy hoặc r không được tìm thấy, tức là A và B đã giống nhau), đáp án là 0.

Thuật toán cụ thể:

Duyệt từ trái sang phải để tìm chỉ số l đầu tiên mà A[i] != B[i]. Nếu không tìm thấy, kết quả là 0.
Duyệt từ phải sang trái để tìm chỉ số r đầu tiên (từ phải) mà A[i] != B[i].
Kết quả là r - l + 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.