Mảng cộng dồn, mảng hiệu (Prefixsum, Difference Array)

Đỗ Thị Hồng Ngát 13/09/2023
13
Th9

Mảng cộng dồn, mảng hiệu (Prefixsum, Difference Array)

1. Bài toán mảng cộng dồn

Cho một dãy \(A\) gồm \(n\) số nguyên và \(q\) truy vấn. \((n, q \le 10^5 )\). Mỗi truy vấn gồm hai số \(L, R\) \((1 \le L \le R \le n)\).

Yêu cầu: Với mỗi truy vấn, tính tổng các số trong đoạn từ vị trí \(L\) đến vị trí \(R\) trong mảng \(A\)

Input

  • Dòng đầu tiên chứa hai số \(n\) và \(q\)
  • Dòng thứ \(2\) chứa \(n\) số nguyên miêu tả dãy \(A\), mỗi số cách nhau một dấu cách.
  • \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) miêu tả đoạn cần tính tổng.

Output
In ra \(q\) dòng, mỗi dòng tương ứng với kết quả của \(1\) truy vấn theo thứ tự đề bài.

Sample Input

7 3
4 -3 5 7 -1 2 6
1 3
2 6
4 7

Sample Output

6 
10 
14

Phân tích bài toán

Cách làm thông thường với độ phức tạp \(O(q * n)\)

Ý tưởng: Với mỗi truy vấn, ta sẽ duyệt lại các vị trí từ \(L\) đến \(R\) trong mảng \(A\) để tính lại tổng

void sum(int L, int R){
    int s = 0;
    for(int i = L; i <= R; i++)
        s+= a[i];
    return s;
}

Dễ thấy hàm \(sum(L, R)\) có độ phức tạp là \(O(n)\).
Vậy với \(q\) truy vấn, ta có độ phức tạp của cả bài toán là \(O(q * n)\)
=> Không đáp ứng được thời gian chạy trong \(1s\) với kích thước dữ liệu \(n, q\) khoảng \(10^5\).

Cách làm với mảng cộng dồn 1 chiều

Gọi \(F_i\) = Tổng các phần tử từ \(1\) tới \(i\)
\(F_1 = A_1\)
\(F_2 = A_1 + A_2\)
\(F_3 = A_1 + A_2 + A_3\)
…
\(F_i = A_1 + A_2 + A_3 + … + A_i\)
…
\(F_n = A_1 + A_2 + A_3 + … + A_i + … + A_n\)

Cách tính tổng đoạn từ L đến R

Ta có: \(Sum(L,R) = A_L +A_{L+1} +A_{L+2} + … + A_R\)

Nhận xét:
\(F_{L-1} = A_1 + A_2 + A_3 + … + A_{L-1}\)
\(F_R = A_1 + A_2 + A * 3 + … + A_{L-1} + A_L +A_{L+1} + A_{L+2} + … + A_R\)

Vậy: \(Sum(L, R) = F_R – F_{L-1}\)

Giải thích công thức: xanh = đỏ – tím
Mảng cộng dồn một chiều

Code mảng cộng dồn cho bài toán trên

for(int i = 1; i <= N; i++)
    F[i] = F[i-1] + A[i];

Code full bài toán

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define MAXN 100005

using namespace std;

int n,q;
int a[MAXN];
ll f[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>q;
    for(int i = 1; i<=n; i++) cin>>a[i];
    //chuẩn bị trước mảng f
    for(int i = 1; i <=n; i++)
        f[i] = f[i-1]+a[i];
    // thực hiện các truy vấn
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<f[r] - f[l-1]<<endl;
    }
    return 0;
}

Đánh giá độ phức tạp

Với mảng cộng dồn \(1\) chiều, ta cần chuẩn bị trước mảng \(F\) với độ phức tạp \(O(n)\). Sau đó với mỗi truy vấn, ta chỉ mất \(O(1)\) để lấy tổng của một đoạn. Vậy độ phức tạp của cả bài toán là \(O(n+q)\).

2. Mảng cộng dồn 2 chiều

Cho ma trận \(m * n\), các hàng đánh số từ \(1\) đến \(m\), các cột đánh số từ \(1\) đến \(n\) và \(q\) truy vấn \((n, m \le 1000, q \le 10^5)\).

Mỗi truy vấn chứa 4 số \(x, y, u, v\). Cần tính tổng hình chữ nhật có ô trái trên là \((x, y)\), ô phải dưới là \((u, v)\).

Hướng dẫn giải bằng mảng cộng dồn 2 chiều

Gọi mảng \(F_{i,j}\) = tổng hình chữ nhật có ô trái trên là \((1, 1)\) ô phải dưới là \((i, j)\).

Công thức tính mảng \(F\): \(F_{i,j} = F_{i-1,j} + F_{i,j-1} – F_{i-1,j-1} + A_{i,j}\)

Giải thích công thức: xanh = đỏ + vàng – cam + hồng
Mảng cộng dồn hai chiều

Công thức tính tổng hình chữ nhật \((x, y, u, v)\)

\(Sum = F_{u,v} – F_{x-1,v} – F_{u,y-1} + F_{x-1,y-1}\).

Giải thích công thức: xanh = đỏ – vàng – cam + tím
Mảng cộng dồn hai chiều

Code mảng cộng dồn 2 chiều

for(int i = 1; i <= m; i++)
    for(int j = 1; j <= n; j++)
        F[i][j] = F[i-1][j] + F[i][j-1] - F[i-1][j-1] + a[i][j];

Đánh giá độ phức tạp

Với mảng cộng dồn \(2\) chiều, ta cần chuẩn bị trước mảng \(F\) với độ phức tạp là \(O(m * n)\). Sau đó, mỗi truy vấn, ta chỉ mất \(1\) phép tính để tính được tổng. Vậy độ phức tạp của cả bài toán khi sử dụng kỹ thuật mảng cộng dồn là \(O(m * n * q)\).

3. Bài toán mảng hiệu

Cho một mảng \(A\) gồm \(n\) số nguyên và \(q\) truy vấn trên đoạn \((1 \le n, q \le 10^5)\). Ban đầu tất cả phần tử trong mảng \(A\) đều có giá trị bằng \(0\).
Mỗi truy vấn gồm hai số \(L, R (1 \le L \le R \le n)\) cho biết, sau truy vấn này các phần tử trong đoạn \(L, R\) sẽ được tăng lên \(1\) đơn vị.

Yêu cầu: In ra tất cả các phần tử của mảng \(A\) sau \(q\) truy vấn
Input

  • Dòng đầu tiên chứa hai số \(n\) và \(q\)
  • Các dòng tiếp theo, mỗi dòng chứa một truy vấn

Output
In ra tất cả các phần tử của mảng \(A\) sau \(q\) truy vấn

Sample Input

7 3
1 3
2 6
4 7

Sample Output

1 2 2 2 2 2 1

Hướng dẫn giải bằng mảng hiệu

Gọi \(D_i = A_i – A_{i-1}\).

Vậy, khi tăng đoạn từ \(L\) đến \(R\) trong mảng \(A\) thì các phần tử của mảng \(D\) sẽ lần lượt thay đổi như sau:

  • \(D_L = (A_L + K) – A_{L-1} = (A_L – A_{L-1}) + K = D_L + K\) (tăng thêm \(K\) so với ban đầu)
  • \(D_{L+1} = (A_{L+1} + K) – (A_L + K) = A_{L+1} + K – A_L – K = A_{L+1} – A_{L} = D_L\) (giữ nguyên so với ban đầu)
    … Tương tự với các phần tử khác từ vị trí \(L+1\) đến \(R\), mảng \(D\) sẽ không thay đổi
  • \(D_{R+1} = A_{R+1} – (A_R + K) = A_{R+1} – A_R – K = (A_{R+1} – A_R) – K = D_{R+1} – K\) (giảm đi \(K\) so với ban đầu)

Khi tăng từ \(L\) đến \(R\) trong mảng \(A\) thì chỉ có \(2\) phần tử của mảng \(D\) bị thay đổi so với ban đầu. Vậy, thay vì tăng tất cả các phần tử của mảng \(A\) lên một lượng \(K\), ta chỉ cần tăng \(D_L\) lên \(K\) và giảm \(D_{R+1}\) đi \(K\).

=> Mỗi truy vấn sẽ chỉ mất \(O(1)\) để cập nhật
Mảng hiệu một chiều

Sau khi thực hiện xong \(q\) truy vấn, để khôi phục lại mảng \(A\) ta làm như sau:
Vì: \(D_i = A_i – A_{i-1}\)
Nên: \(D_1 = A_1\)
\(A_i = D_i + A_{i-1}\)

Code mẫu của bài toán mảng hiệu một chiều

#include<bits/stdc++.h> 
#define ll long long 
#define MAXN 100005 
using namespace std;

int n,q;
int a[MAXN];
ll d[MAXN];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>q;
    // thực hiện các truy vấn 
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        d[l]+=k;
        d[r+1]-=k;
    }
    //khôi phục lại mảng a
    for(int i = 1; i <=n; i++){
        a[i] = d[i]+a[i-1];
        cout<<a[i]<<" ";
    }
    return 0;
}

4. Mảng hiệu 2 chiều

Cho một ma trận \(m * n\) và \(q\) truy vấn \((1 \le n, q \le 10^5)\).

Mỗi truy vấn gồm 5 số \(x, y, u, v, K\) cho biết, sau truy vấn này các phần tử trong hình chữ nhật có ô trái trên \((x, y)\) và ô phải dưới \((u, v)\) sẽ tăng lên \(K\) đơn vị.

Hướng dẫn giải bằng mảng hiệu 2 chiều

Tương tự mảng hiệu 1 chiều ta gọi
\(D_{i,j} = A_{i,j} + A_{i-1,j-1} – A_{i,j-1} – A_{i-1,j}\)

Vậy với mỗi truy vấn tăng \(K\) đơn vị trong hình chữ nhật có ô trái trên là \((x, y)\), ô phải dưới là \((u, v)\) trên mảng \(A\) thì sẽ chỉ có \(4\) ô ở mảng \(D\) được cập nhật:

  • ô \((x,y)\) và ô \((u+1, v+1)\) tăng lên \(K\)
  • ô \((x, v+1)\) và ô \((u+1, y)\) giảm đi \(K\).

Khi đó, để khôi phục lại \(A_{i,j}\), ta có công thức: \(A_{i,j} = D_{i,j} – A_{i-1,j-1} + A_{i,j-1} + A_{i-1,j}\)

Mảng hiệu hai chiều

5. Luyện tập

Đây là một số bài tập luyện tập trong sách Competitive Programming Basic của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Unable to display PDF file. Download instead. 

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *