¶ Cây chỉ số nhị phân 2 chiều (BIT 2 chiều)
Tác giả:
- Phạm Công Minh - THPT chuyên Khoa học Tự Nhiên, ĐHQGHN
Reviewer:
- Lê Minh Hoàng - Đại học Khoa học Tự nhiên, ĐHQG-HCM
- Phạm Hoàng Hiệp - University of Georgia
- Ngô Nhật Quang - The University of Texas at Dallas
¶ Giới thiệu
BIT 2 chiều là cấu trúc dữ liệu mở rộng của BIT 1 chiều. Công dụng chính của BIT 2 chiều là xử lý các truy vấn lên hình chữ nhật con trên một mảng 2 chiều.
Bài viết yêu cầu người đọc hiểu rõ cách hoạt động của BIT 1 chiều. Các bạn có thể đọc về BIT 1 chiều tại đây: VNOI - Cây chỉ số nhị phân.
¶ Bài toán
Các định nghĩa:
-
Trong mảng hai chiều , là giá trị của phần tử hàng thứ , cột thứ .
-
là hình chữ nhật con có góc trái trên là và góc phải dưới là . Nếu hoặc thì hình chữ nhật con rỗng.
-
là tổng các phần tử trong hình chữ nhật con .
Đề bài:
Cho mảng 2 chiều có hàng cột (đánh số từ 1). Có truy vấn thuộc 2 loại:
- : Cộng vào .
- : Tính .
Giới hạn: ,
¶ Thuật toán ngây thơ 1
Với truy vấn 1, ta cộng trực tiếp vào mảng. Với truy vấn 2, ta duyệt qua từng phần tử của và cộng giá trị vào kết quả.
int A[N][M];
void add(int u, int v, int x){
A[u][v] += x;
}
int query(int u, int v){
int sum = 0;
for(int i = 1; i <= u; i++){
for(int j = 1; j <= v; j++){
sum += A[i][j];
}
}
return sum;
}
¶ Phân tích
- Độ phức tạp khi cập nhật:
- Độ phức tạp khi truy vấn:
- Có truy vấn, nên độ phức tạp là
¶ Thuật toán ngây thơ 2
Ta định nghĩa là giá trị của bit nhỏ nhất trong biểu diễn nhị phân của . Ví dụ:
Ta sẽ lưu BIT 1 chiều, mỗi BIT quản lý một hàng.
Như đã giới thiệu trong bài viết BIT 1 chiều, phần tử thứ trong BIT 1 chiều sẽ lưu tổng các phần tử trong đoạn . Ở đây, phần tử thứ của BIT thứ sẽ lưu .
Đối với truy vấn 1 ta update BIT của hàng . Còn đối với truy vấn 2 ta duyệt qua và truy vấn trên từng BIT của các hàng từ đến .
int A[N][M], BIT[N][M];
void add(int u, int v, int x){
for(v; v <= m; v += v&(-v))BIT[u][v]+=x;
}
int query(int u, int v){
int sum = 0;
for(int i = 1; i <= u; i++){
for(int j = v; j > 0; j -= j&(-j))sum += BIT[i][j];
}
return sum;
}
void preprocess(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
add(i, j, A[i][j]);
}
}
}
¶ Phân tích
- Độ phức tạp tiền xử lý:
- Độ phức tạp khi cập nhật:
- Độ phức tạp khi truy vấn:
- Có Q truy vấn, nên độ phức tạp là
¶ BIT 2 chiều
Ta gọi BIT trong phần ngây thơ 2 là . Như vậy
Từ thuật toán ngây thơ 2, thay vì sử dụng BIT 1 chiều độc lập, ta có thể sử dụng một BIT 1 chiều lớn để quản lý toàn bộ BIT 1 chiều. Như vậy, mỗi phần tử của BIT lớn là một BIT nhỏ gồm phần tử, BIT nhỏ thứ quản lý thông tin về các trong đoạn .
Trong BIT 2 chiều, phần tử thứ của BIT nhỏ thứ sẽ lưu:
Vì nên tổng này tương đương với:
Ta có thể viết lại biểu thức thành:
Như vậy phần tử thứ của BIT thứ trong BIT 2 chiều lưu tổng các phần tử trong hình chữ nhật con có góc trái trên là và góc phải dưới là .
Dưới đây là hình minh họa cho trường hợp .
¶ Cài đặt
Ta khai báo BIT 2 chiều dưới dạng một mảng , trong đó BIT[u][v] lưu giá trị của phần tử thứ trong BIT thứ ;
int BIT[N][M];
Hàm để update:
void add(int u, int v, int x){
for(int i = u; i <= n; i += i&(-i)){
for(int j = v; j <= m; j += j&(-j))BIT[i][j]+=x;
}
}
Hàm để truy vấn:
int query(int u, int v){
int sum = 0;
for(int i = u; i > 0; i -= i&(-i)){
for(int j = v; j > 0; j -= j&(-j))sum += BIT[i][j];
}
return sum;
}
Để tính tổng các phần tử trong một hình chữ nhật nhất định, ta có thể sử dụng tổng tiền tố 2 chiều, có công thức như sau:
¶ Phân tích
- Độ phức tạp khi cập nhật:
- Độ phức tạp khi truy vấn:
- Có Q truy vấn, nên độ phức tạp là
¶ Cập nhật hình chữ nhật con, truy vấn phần tử
Ta thay đổi bài toán ban đầu như sau:
- : Cộng vào các phần tử thuộc
- : Tính
Tương tự với BIT 1 chiều, ta sẽ sử dụng mảng hiệu để cập nhật.
Ta có:
Do đó, ta có thể lưu . Khi đó,
Khi ta thực hiện truy vấn , có giá trị của thay đổi:
- tăng lên
- giảm đi
- giảm đi
- tăng lên
Nếu vẫn chưa rõ, bạn đọc có thể tham khảo hình minh họa sau:
¶ Cài đặt
Hàm cập nhật:
void rectAdd(int a, int b, int u, int v, int x){
add(a, b, x);
add(u+1, v+1, x);
add(u+1, b, -x);
add(a, v+1, -x);
}
Hàm truy vấn tương tự như phần trước.
¶ Cập nhật hình chữ nhật con, truy vấn hình chữ nhật con
Ta thay đổi bài toán ban đầu:
-
: Cộng vào các phần tử thuộc
-
: Tính
Ta tiếp tục sử dụng ý tưởng mảng hiệu. Do nên ta có:
Dựa vào công thức biến đổi ở trên, ta cần duy trì bằng bốn BIT:
int BIT[4][N][M]; // {D[i][j]; i*D[i][j]; j*D[i][j]; i*j*D[i][j]}
void add(int u, int v, int x){
for(int i = u; i <= n; i += i&(-i)){
for(int j = v; j <= m; j += j&(-j)){
BIT[0][i][j] += x;
BIT[1][i][j] += u * x;
BIT[2][i][j] += v * x;
BIT[3][i][j] += u * v * x;
}
}
}
void rectAdd(int a, int b, int u, int v, int x){
add(a, b, x);
add(a, v + 1, -x);
add(u + 1, b, -x);
add(u + 1, v + 1, x);
}
Khi truy vấn, ta lấy tửng hệ số nhân lên rồi cộng trừ để ra kết quả
int query(int u, int v){
int a[4] = {0, 0, 0, 0};
for(int ty = 0; ty < 4; ty++){
for(int i = u; i > 0; i -= i&(-i)){
for(int j = v; j > 0; j -= j&(-j)){
a[ty] += BIT[ty][i][j];
}
}
}
return a[0]*(u + 1)*(v + 1) - a[1]*(v + 1) - a[2]*(u + 1) + a[3];
}
¶ Kĩ thuật nén BIT 2 chiều
Phần này được lấy nhiều cảm hứng từ blog cá nóc cắn cáp
Chú ý kĩ thuật này chỉ dùng được khi ta biết trước tất cả các truy vấn.
Ta thay đổi giới hạn bài toán ban đầu thành .
Ta sẽ không thể lưu được toàn bộ BIT 2 chiều bằng một mảng , nếu sử dụng std::map hay std::unordered_map thì code sẽ không đủ nhanh để AC.
Tuy nhiên, ta nhận thấy rằng, với mỗi truy vấn, chỉ có BIT được duyệt qua, và mỗi BIT chỉ có thao tác là cộng một phần tử và tính tổng một tiền tố. Vì vậy, đối với mỗi BIT, ta có thể lưu lại tất cả các vị trí được cộng và được truy vấn trước, sau đó tiến hành rời rạc hóa các vị trí đó. Do có truy vấn, mỗi truy vấn tạo thêm tối đa vị trí trên BIT nên có tổng cộng vị trí cần lưu.
Để lưu như vậy, ta tạo 2 hàm mới chỉ để lưu các vị trí được truy vấn.
vector<int> pos[N];
vector<int> BIT[N];
void fakeAdd(int u, int v, int x){
for(u; u <= n; u += u&(-u)){
pos[u].push_back(v);
}
}
void fakeQuery(int u, int v){
for(u; u <= n; u += u&(-u)){
pos[u].push_back(v);
}
}
Sau khi lưu các vị trí cần thiết, ta tiến hành rời rạc hóa trên từng BIT.
void compress(){
for(int i = 1; i <= n; i++){
pos[i].push_back(0);
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
BIT[i].assign(pos[i].size(), 0);
}
}
Khi đã rời rạc hóa xong, ta thực hiện các truy vấn như thường. Lưu ý lúc này mảng pos chỉ để ánh xạ lại index trên mảng đã được rời rạc hóa.
void add(int u, int v, int x){
for(int i = u; i <= n; i += i&(-i)){
for(int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j < BIT[i].size(); j += j&(-j)){
BIT[i][j] += x;
}
}
}
void query(int u, int v){
int sum = 0;
for(int i = u; i > 0; i -= i&(-i)){
for(int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j > 0; j -= j&(-j)){
sum += BIT[i][j];
}
}
return sum;
}