Truy vấn cập nhật đoạn
Trong chuyên đề này, tôi sẽ chia sẻ tới các bạn một kĩ thuật khá hữu ích trong các kì thi lập trình, sử dụng cho các bài toán liên quan tới nhiều truy vấn cập nhật tăng/giảm một đoạn liên tiếp trên dãy số hoặc ma trận. Chúng ta sẽ tiếp cận các kĩ thuật này thông qua một số bài toán cụ thể để cho dễ hình dung. Những bài toán tôi giới thiệu dưới đây cũng có thể coi là những kĩ thuật cơ bản của truy vấn cập nhật đoạn, ta sẽ áp dụng chúng như một bước của thuật toán trong những bài toán lớn hơn.
Bài toán 1
Đề bài
Cho dãy số nguyên gồm phần tử . Ban đầu tất cả các phần tử đều mang giá trị . Bạn cần thực hiện thao tác cập nhật trên dãy số này, với mỗi thao tác, cần tăng đoạn gồm các phần tử từ vị trí tới vị trí của dãy số thêm đơn vị.
Yêu cầu: Tìm giá trị lớn nhất của dãy số sau khi thực hiện xong cả thao tác cập nhật?
Input:
- Dòng đầu tiên chứa hai số nguyên dương và - độ dài dãy số và số lượng thao tác cập nhật.
- dòng tiếp theo, mỗi dòng chứa ba số nguyên dương thể hiện một thao tác cập nhật.
Ràng buộc:
- .
- .
- .
Output:
- In ra giá trị lớn nhất của dãy số sau thao tác cập nhật.
Sample Input:
5 4
1 4 3
2 5 3
1 5 10
2 2 1
Sample Output:
17
Ý tưởng
Với bài toán này, hiển nhiên cách làm sử dụng hai vòng lặp để cập nhật lại dãy số với từng truy vấn sẽ không thỏa mãn thời gian chạy, vì độ phức tạp sẽ lên tới .
Tuy nhiên, ta có thể cải tiến cách làm như sau để giảm độ phức tạp: Ứng với mỗi truy vấn :
- Cộng thêm vào .
- Trừ đi ở .
Sau khi làm hết như vậy với truy vấn, sau đó thực hiện cộng dồn từ đầu mảng ra cuối mảng:
Như vậy ta có được mảng số nguyên sau khi cập nhật. Cuối cùng chỉ cần in ra phần tử lớn nhất của mảng.
Độ phức tạp thu được là: .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define int long long
using namespace std;
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector < int > a(n + 2);
while (q--)
{
int l, r, k;
cin >> l >> r >> k;
a[l] += k;
a[r + 1] -= k;
}
for (int i = 1; i <= n; ++i)
a[i] += a[i - 1];
cout << *max_element(a.begin() + 1, a.begin() + n);
return 0;
}
Ngôn ngữ Python:
if __name__ == '__main__':
n, q = map(int(input().split()))
a = [0] * (n + 2)
for _ in range(q):
l, r, k = map(int, input().split())
a[l] += k
a[r + 1] -= k
for i in range(1, n + 1):
a[i] += a[i - 1]
res = 0
for i in range(1, n + 1):
res = max(res, a[i])
print(res)
Bài toán 2
Đề bài
Cho dãy số gồm phần tử, các phần tử được đánh số từ tới . Ban đầu tất cả các phần tử trong mảng đều mang giá trị . Người ta tiến hành điều chỉnh dãy số bằng thao tác có dạng với mỗi thao tác, phần tử sẽ tăng thêm đơn vị, phần tử tăng thêm đơn vị,..., tăng thêm đơn vị.
Yêu cầu: Hãy đưa ra dãy số sau khi tất cả các thao tác được thực hiện?
Input:
- Dòng đầu chứa hai số nguyên và – số lượng phần tử trong mảng và số thao tác điều chỉnh.
- dòng tiếp theo, mỗi dòng chứa hai số nguyên – biểu thị một thao tác điều chỉnh.
Ràng buộc:
- .
- .
- .
Output:
- Đưa ra số nguyên là các phần tử của dãy số sau khi thực hiện thao tác cập nhật, các số phân tách nhau bởi dấu cách.
Sample Input:
5 3
1 2
2 5
3 4
Sample Output:
1 3 3 5 4
Ý tưởng
Vẫn tương tự như bài toán trước, ta không thể sử dụng hai vòng lặp để giải quyết bài tập này. Thay vào đó, ta sẽ tìm cách đưa nó về bài toán cơ bản vừa rồi.
Xét truy vấn [l, r]; việc cập nhật sẽ diễn ra như sau:
- .
- .
- .
Cộng thêm vào vế phải của các phép biến đổi, ta có:
- .
- .
- .
Như vậy, ta có thể tách truy vấn thành hai truy vấn nhỏ:
- Truy vấn : Giảm đoạn đi đơn vị. Truy vấn này giống bài toán cập nhật đoạn cơ bản số .
- Truy vấn : Với mỗi thuộc tăng lên đơn vị. Truy vấn này ta có thể đếm số lần được tăng lên bằng mảng như vậy sau khi xử lý xong ta chỉ cần cập nhật . Việc cập nhật mảng cũng có thể thực hiện giống như bài toán cập nhật đoạn cơ bản.
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 10;
int n, q, decrease[maxn], i_count[maxn], a[maxn];
void update_queries(int l, int r)
{
// Truy vấn nhỏ 1: Giảm đoạn [l, r] đi (l - 1) đơn vị.
decrease[l] -= (l - 1);
decrease[r + 1] += (l - 1);
// Truy vấn nhỏ 2: Vì a[i] += i, nên ta đếm số lần a[i] được tăng,
// rồi lưu vào mảng i_count[i].
i_count[l]++;
i_count[r + 1]--;
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q;
while (q--)
{
int l, r;
cin >> l >> r;
update_queries(l, r);
}
for (int i = 1; i <= n; ++i)
{
decrease[i] += decrease[i - 1];
i_count[i] += i_count[i - 1];
a[i] = decrease[i] + i * i_count[i];
cout << a[i] << ' ';
}
return 0;
}
Ngôn ngữ Python:
def update_queries(l, r, decrease, i_count):
# Truy vấn nhỏ 1: Giảm đoạn [l, r] đi (l - 1) đơn vị.
decrease[l] -= (l - 1)
decrease[r + 1] += (l - 1)
# Truy vấn nhỏ 2: Vì a[i] += i, nên ta đếm số lần a[i] được tăng,
# rồi lưu vào mảng i_count[i].
i_count[l] += 1
i_count[r + 1] -= 1
if __name__ == '__main__':
n, q = map(int, input.split())
decrease = [0] * (n + 2)
i_count = [0] * (n + 2)
for _ in range(q):
l, r = map(int, input().split())
update_queries(l, r, decrease, i_count)
a = [0] * (n + 1)
for i in range(1, n + 1):
decrease[i] += decrease[i - 1]
i_count[i] += i_count[i - 1]
a[i] = decrease[i] + i * i_count[i]
print(a[i], end=' ')
Bài toán 3
Đề bài
Cho một bảng kích thước ( dòng, cột). Ucoder muốn thực hiện truy vấn trên bảng này, mỗi truy vấn có dạng yêu cầu cộng vào tất cả các ô thuộc hình chữ nhật có góc trái trên là và góc phải dưới là một giá trị bằng .
Yêu cầu: Hãy thực hiện các truy vấn và in ra bảng số sau khi thực hiện hết truy vấn?
Input:
- Dòng đầu tiên chứa ba số nguyên dương và - kích thước bảng và số truy vấn.
- dòng tiếp theo, mỗi dòng chứa số nguyên thể hiện một dòng của bảng số.
- dòng tiếp theo, mỗi dòng ghi năm số nguyên thể hiện một truy vấn.
Ràng buộc:
- .
- .
- .
- .
Output:
- In ra bảng số sau khi thực hiện hết truy vấn.
Sample Input:
3 3 2
1 2 3
0 2 2
3 3 5
1 1 2 2 -1
2 2 3 3 2
Sample Output:
0 1 3
-1 3 4
3 5 7
Ý tưởng
Ta sẽ phát triển cách làm lần lượt từ dễ đến khó.
Các cách làm đơn giản
Cách đơn giản nhất là với mỗi truy vấn, sử dụng hai vòng lặp để duyệt qua hình chữ nhật tương ứng (hàng từ cột từ ) và cập nhật trực tiếp trên ma trận. Độ phức tạp của cách này là .
Ta có thể cải tiến một chút như sau: Ứng với mỗi truy vấn, ta sẽ cập nhật trên từng hàng từ tới bằng kĩ thuật cập nhật đoạn trên mảng một chiều:
Sau đó, duyệt lại toàn bộ ma trận và cập nhật trên từng hàng từ trước ra sau:
Ta sẽ thu được ma trận đã cập nhật. Lúc này độ phức tạp giảm xuống còn: . Nhưng như vậy vẫn chưa đủ tốt, ta cần một cách làm tốt hơn.
Cách làm tối ưu
Ta sẽ cập nhật các hình chữ nhật con dựa trên ý tưởng tương tự với tổng tiền tố trên ma trận.
Sử dụng bảng để lưu các cập nhật diễn ra ở các truy vấn, sẽ là giá trị cập nhật thêm của hình chữ nhật con .
Xét một yêu cầu cập nhật ta sẽ cập nhật hình chữ nhật con như sau:
Theo cách cập nhật này, thì ta thấy rằng, mỗi một ô trong hình chữ nhật con được cập nhật đều sẽ khiến cho ô bị cập nhật tăng lên. Vì thế, tổng giá trị tăng thêm sau lần cập nhật của ô sẽ là tổng hình chữ nhật con trên mảng .
Vậy sau khi cập nhật xong, ta tính lại mảng bằng quy hoạch động hình chữ nhật trên chính nó theo công thức:
Rồi lấy để thu được kết quả tại ô sau khi cập nhật.
Độ phức tạp: .
Cài đặt
Ngôn ngữ C++:
#include <bits/stdc++.h>
#define int long long
#define task "table."
using namespace std;
const int max_size = 1010;
int a[max_size][max_size], b[max_size][max_size];
void query(int m, int n, int a[][max_size], int b[][max_size])
{
int x1, y1, x2, y2, val;
cin >> x1 >> y1 >> x2 >> y2 >> val;
b[x2][y2] += val;
b[x1 - 1][y2] -= val;
b[x2][y1 - 1] -= val;
b[x1 - 1][y1 - 1] += val;
}
void print_result(int m, int n, int a[][max_size], int b[][max_size])
{
// Cập nhật lại bảng b cho chính xác.
for (int i = m; i >= 1; --i)
for (int j = n; j >= 1; --j)
b[i][j] = b[i + 1][j] + b[i][j + 1] - b[i + 1][j + 1] + b[i][j];
// Tính kết quả đã cập nhật trên bảng a.
for (int i = 1; i <= m; ++i)
{
for (int j = 1; j <= n; ++j)
cout << a[i][j] + b[i][j] << ' ';
cout << endl;
}
}
main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, n, q;
cin >> m >> n >> q;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
for (int i = 1; i <= q; ++i)
query(m, n, a, b);
print_result(m, n, a, b);
return 0;
}
Các bạn có thể luyện tập thêm về dạng bài tập này tại series Range Queries của CSES, tôi để link tại đây: https://cses.fi/problemset/task/1646.
©️ Tác giả: Vũ Quế Lâm từ Viblo
All Rights Reserved