Prefix Sum

Trong các bài học trước, chúng ta đã cùng nhau tìm hiểu về một số cấu trúc dữ liệu. Các cấu trúc dữ liệu đó được gọi chung là cấu trúc dữ liệu lưu trữ. Ngày hôm nay, chúng ta sẽ cùng nhau đi tìm hiểu về cấu trúc dữ liệu dạng truy vấn đầu tiên là Prefix Sum.

Nội dung

Để có thể hiểu được bài học này một cách tốt nhất, các bạn nên có kiến thức cơ bản về các phần:

• Biến, kiểu dữ liệu, toán tử trong C++
• Câu điều kiện, vòng lặp, hàm trong C++
• Mảng trong C++
• Các kiến thức cần thiết để theo dõi khóa học   
• Nhập, xuất dữ liệu qua file trong C++

Trong bài học này chúng ta sẽ tìm hiểu về:

• Khái niệm Prefix Sum
• Cách ứng dụng

Prefix Sum

Bài toán đặt ra

Ta có một bài toán như sau:

Cho một dãy n số nguyên dương a_i (n ≤ 10⁵, a_i ≤ 10⁹). Có t truy vấn t ≤ 10⁶, mỗi truy vấn gồm hai số nguyên dương i và j yêu cầu in ra tổng của các số trong đoạn a_i, a_i+1, …, a_j.

Ví dụ:

Lời giải ban đầu

Theo suy nghĩ thông thường, đề bài bảo gì ta sẽ làm đó. Do đó, với mỗi một truy vấn, ta sẽ tiến hành duyệt từ i đến j để tính được tổng các số trong đoạn đó.

Từ suy nghĩ đó, ta có thể triển khai code như sau:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MaxN = 1 + 1e5;

int n, a[MaxN], t;

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i];
    cin >> t;
    while(t--){
        int x, y;
        ll sum = 0;
        cin >> x >> y;
        for(int i = x ; i <= y ; ++i) sum += a[i];
        cout << sum << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Tuy nhiên, ta thấy ở thuật toán trên, với mỗi truy vấn thì ta phải duyệt lại dãy để tính tổng. Do đó, độ phức tạp sẽ là O(t * n). Với n≤ 10⁵  và t ≤ 10⁶ thì thuật toán này là chưa đủ tối ưu. Vậy thì liệu có cách tiếp cận nào khác không?

Nhận xét

Hãy thử cùng nhau suy nghĩ bằng một ví dụ trong thực tế. Chúng ta có một dải băng kích thước 1×n được chia thành n ô có kích thước 1×1. Hãy tìm cách cắt dải băng để lấy được đoạn [i, j] (màu xanh).

Vậy thì chúng ta sẽ làm như thế nào?

Đầu tiên, ta sẽ cắt đoạn [j + 1, n] (màu đỏ) để lấy được đoạn [1, j].

Tiếp theo, ta sẽ cắt đoạn [1, i – 1] (màu đỏ) để thu được đoạn từ [i, j].

Từ ví dụ trên, ta nghĩ để tính tổng các số trong đoạn [i, j], ta sẽ tính tổng các số trong đoạn [1, j] rồi trừ đi tổng các số trong đoạn [1, i – 1].

Thật vậy, hãy xét một dãy số a₁, a₂, a₃, …, a_n-1, a_n .

Gọi S_i là tổng các số trong dãy trên từ vị trí 1 đến vị trí i.

Ta thấy rằng: a_i + a_{i + 1} + a_{i + 2} +…+ a_j = (a₁ + a₂ +…+ a_j) - (a₁ + a₂+…+ a_{i - 1})= S_j - S_i-1 

Mặt khác, ta lại thấy rằng các giá trị S_i hoàn toàn có thể được tính toán trước và truy vấn trong O(1). Do đó, ta nghĩ đến việc sẽ tính toán trước các S_i. S_i ở đây chính là Prefix Sum (tổng tiền tố).

Cách giải cải tiến

Từ những nhận xét phía bên trên, ta sẽ đưa ra một thuật toán như sau:

• Tiến hành tính toán các S_i với S_i là tổng các số trong dãy trên từ vị trí 1 đến vị trí i.
• Với mỗi truy vấn, in ra s_j - s_i-1

Câu hỏi bây giờ sẽ là: Tính toán S_i bằng cách nào để hiệu quả? Ta thấy

 S_i = a₁ + a₂ + …+ a_i-1 + a_i = (a₁ + a₂ + … + a_i-1) + a_i = S_i-1 + a_i 

Do đó, ta có thể dùng một vòng lặp, tính toán S_i  dựa vào S_i-1.

Từ toàn bộ những nhận xét trên, ta có đoạn code sau:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MaxN = 1 + 1e5;

int n, a[MaxN], t, s[MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i];
    for(int i = 1 ; i <= n ; ++i) s[i] = s[i - 1] + a[i];
    cin >> t;
    while(t--){
        int x, y;
        cin >> x >> y;
        cout << s[y] - s[x - 1] << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Khi này, mỗi truy vấn ta sẽ thực hiện trong O(1) nên độ phức tạp giảm xuống chỉ còn là O(n + t).

Qua ví dụ trên, ta có thể hiểu đơn giản: Prefix Sum (tổng tiền tố) là một cách sử dụng mảng linh hoạt để tính toán giá trị từ vị trí gốc đến vị trí yêu cầu.

Prefix Sum với mảng hai chiều

Bài toán đặt ra

Tiếp theo, mình sẽ có một bài toán mở rộng cho bài toán ở trên như sau:

Cho một mảng hai chiều n hàng và m cột gồm các số nguyên dương a_i (n, m ≤ 10³, a_i ≤ 10⁹) với ô trên cùng bên trái là ô (1, 1) và ô dưới cùng bên phải là ô (n, m). Có t truy vấn t ≤ 10⁶, mỗi truy vấn gồm 4 số nguyên dương i, j, k, h yêu cầu in ra tổng các ô trong hình chữ nhật có góc trái trên là ô (i, j), góc phải dưới là ô (k, h).

Ví dụ:

Giải thích ví dụ:

Ở truy vấn 1, ta cần in ra tổng các ô tử (1, 1) đến (4, 5) có nghĩa là các ô trong vùng khoanh đỏ

Ở truy vấn 2, ta cần in ra tổng các ô tử (2, 3) đến (4, 4) có nghĩa là các ô trong vùng khoanh đỏ

Ở truy vấn 3, ta cần in ra tổng các ô tử (3, 1) đến (3, 4) có nghĩa là các ô trong vùng khoanh đỏ

Với các ý tưởng tương tự phần trước, liệu các bạn có thể tìm ra cách làm cho bài toán này không? Trước khi đọc phần tiếp theo để biết đáp án, hãy thử dừng lại để suy nghĩ một chút nhé.

Ý tưởng

Hãy tưởng tượng, chúng ta có một tấm bìa có kích thước n×m được chia làm n×m ô vuông nhỏ có kích thước 1×1. Giờ ta sẽ cần cắt để thu được vùng màu xanh như hình:

Bây giờ, hãy cùng nhau xem làm sao để có thể thu được phần màu xanh đó nhé. Ta sẽ gọi ô trên trái của vùng màu xanh là ô (i, j).
Đầu tiên, ta sẽ cắt bỏ hình chữ nhật có ô trên trái là (1, 1) và ô phải dưới là (i – 1, m) (màu đỏ)

Tiếp theo, ta sẽ cắt bỏ hình chữ nhật có ô trên trái là (1, 1) và ô phải dưới là (n, j - 1) (màu cam).

Lúc này ta sẽ thấy có một vùng chống lấn bị cắt 2 lần (màu tím). Hãy nhớ đến vùng này vì ở phần sau ta sẽ cần chú ý đến nó.

Sau 2 bước, ta đã thu được vùng màu xanh mà ta muốn. Nhìn vào quá trình vừa rồi, các bạn đã nhìn ra lời giải chưa?

Lời giải

Gọi S_{i, j} là tổng của các ô trong hình chữ nhật có ô trái trên là (1, 1) và ô phải dưới là (i, j).

Để có thể tính tổng các ô trong hình chữ nhật có góc trái trên là ô (i, j), góc phải dưới là (k, h) ta sẽ lấy S_{k, h}  (bảng gốc) trừ đi S_i-1,_h (vùng đỏ) và S_k, _j-1 (vùng cam). Tuy nhiên, ta đã trừ đi hai lần giá trị S_{i-1, j-1} (vùng tím) do đó ta sẽ cần cộng bù vùng này.

Tóm lại, ta sẽ có tổng các ô trong hình chữ nhật có góc trái trên là ô (i, j), góc phải dưới là (k, h) là s_k,h - S_i-1, _h- S_k,j-1 + S_i-1,j-1.

Bây giờ lại đặt ra vấn đề, ta sẽ tính s_{i, j} như thế nào?

Hãy giả sử ô màu xanh là ô (i, j) và hiện tại ta đang cần tính s_{i, j}. Ta chỉ cần biết tổng của toàn bộ các ô màu trắng rồi cộng với ô (i, j) là sẽ tính được s_{i, j}.

Ta thấy S_{i-1, j} (màu vàng) và S_{i, j-1} (màu xanh dương) khi cộng lại sẽ bao gồm tất cả các ô màu trắng.

Tuy nhiên, hai vùng này chồng lấn lên nhau ở vùng màu đỏ, chính là s_i-1,j-1 đo đó sẽ cần trừ bỏ vùng này để đảm bảo kết quả chính xác.

Tóm lại, ta sẽ có: S_i,j =S_{i-1, j} + S_{i, j-1}- S_{i-1, j-1} + a_i, j

Từ toàn bộ các nhận xét trên, ta có đoạn code sau:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MaxN = 1 + 1e3;

int n, m, a[MaxN][MaxN], t;
ll s[MaxN][MaxN];

int main(){
    freopen("CTDL.inp","r",stdin);
    freopen("CTDL.out","w",stdout);
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
    for(int j = 1 ; j <= m ; ++j) cin >> a[i][j];
    for(int i = 1 ; i <= n ; ++i)
    for(int j = 1 ; j <= m ; ++j) s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    cin >> t;
    while(t--){
        int i, j, k, h;
        cin >> i >> j >> k >> h;
        cout << s[k][h] - s[i - 1][h] - s[k][j - 1] + s[i - 1][j - 1] << endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Kết luận

Qua bài này chúng ta đã nắm được về Prefix Sum

Bài sau chúng ta sẽ bắt đầu tìm hiểu về thuật toán, mở đầu là Đệ quy

Cảm ơn các bạn đã theo dõi bài viết. Hãy để lại bình luận hoặc góp ý của mình để phát triển bài viết tốt hơn. Đừng quên “Luyện tập – Thử thách – Không ngại khó”.

---

Tải xuống

Tài liệu

Nhằm phục vụ mục đích học tập Offline của cộng đồng, Kteam hỗ trợ tính năng lưu trữ nội dung bài học Prefix Sum dưới dạng file PDF trong link bên dưới.

Ngoài ra, bạn cũng có thể tìm thấy các tài liệu được đóng góp từ cộng đồng ở mục TÀI LIỆU trên thư viện Howkteam.com

Đừng quên like và share để ủng hộ Kteam và tác giả nhé!

Thảo luận

Nếu bạn có bất kỳ khó khăn hay thắc mắc gì về khóa học, đừng ngần ngại đặt câu hỏi trong phần BÌNH LUẬN bên dưới hoặc trong mục HỎI & ĐÁP trên thư viện Howkteam.com để nhận được sự hỗ trợ từ cộng đồng.

CỘNG ĐỒNG HỎI ĐÁP HOWKTEAM.COM

GROUP THẢO LUẬN FACEBOOK