+2

Quy hoạch động 5.5: Mảng tổng tiền tố và Mảng hiệu (phần 2)

Đây là bài viết số 22 thuộc series bài viết về Mảng tổng tiền tố và Mảng hiệu. Để xem lại bài viết số 1,1, mời các bạn nhấn vào đây.

III. Ứng dụng của mảng hiệu

1. Ứng dụng cơ bản

Bài toán cơ bản của mảng hiệu là bài toán cập nhật đoạn, được phát biểu như sau:

"Cho dãy số AA gồm nn phần tử. Bạn được cho trước kk truy vấn, với mỗi truy vấn yêu cầu cập nhật các giá trị có vị trí thuộc đoạn [l,r][l, r] thêm xx đơn vị.

Yêu cầu: In ra mảng AA sau khi thực hiện tất cả kk truy vấn?"

Input:

  • Dòng đầu tiên chứa số nguyên dương nn.
  • Dòng thứ hai chứa nn số nguyên a1,a2,,ana_1, a_2, \dots, a_n phân tách nhau bởi dấu cách.
  • Dòng thứ ba chứa số nguyên dương kk.
  • Trên kk dòng tiếp theo, mỗi dòng chứa ba số nguyên l,r,xl, r, x thể hiện một truy vấn.

Ràng buộc:

  • 1n1051 \le n \le 10^5.
  • ai109;i:1in|a_i| \le 10^9; \forall i: 1 \le i \le n.
  • 1k1061 \le k \le 10^6.
  • 1lrn1 \le l \le r \le n.
  • x109|x| \le 10^9.

Output:

  • In ra dãy AA sau khi thực hiện đủ kk thao tác cập nhật.

Sample Input:

5
1 1 1 1 1
4
2 4 2
1 5 1 
3 5 4
2 2 5

Sample Output:

2 9 8 8 6

Ý tưởng

Thay vì cộng lần lượt từng phần tử ở mỗi truy vấn với độ phức tạp O(n),O(n), ta sẽ xây dựng một mảng hiệu diff(A)diff(A) và tiến hành cập nhật trên đó trong độ phức tạp O(1)O(1).

Với mảng hiệu diff(A) (diff[i]=aiai1;i:2in);diff(A) \ \big(diff[i] = a_i - a_{i - 1}; \forall i: 2 \le i \le n \big); ta có một số trường hợp sau cho một truy vấn:

  • Nếu aia_iai1a_{i - 1} không thuộc đoạn [l,r][l, r] thì giá trị của hai phần tử không đổi diff[i]\to diff[i] không đổi.
  • Nếu aia_iai1a_{i - 1} cùng thuộc đoạn [l,r][l, r] thì giá trị của hai phần tử đều được cộng thêm xdiff[i]x \to diff[i] không đổi.
  • Nếu chỉ một trong hai phần tử aia_i hoặc ai1a_{i - 1} thuộc đoạn [l,r][l, r] thì một trong hai phần tử sẽ được cộng thêm x,x, phần tử còn lại giữ nguyên diff[i]\to diff[i] thay đổi.

Từ đây ta thấy, mảng hiệu chỉ thay đổi khi xét tới vị trí ii rơi vào trường hợp cuối. Mà trường hợp cuối chỉ xảy ra khi i=li = l hoặc i=r+1,i = r + 1, khi đó ta sẽ tác động lên diff[l]diff[l] (tăng thêm xx) và diff[r+1]diff[r + 1] (giảm đi xx) để cập nhật đoạn. Điều này yêu cầu mảng diffdiff ban đầu phải được khai báo kích thước là n+2n + 2 để không gặp lỗi truy cập mảng khi r=nr = n.

Cuối cùng, ta áp dụng tính chất A=sum(0,diff)A = sum(0, diff) để phục hồi lại mảng AA sau khi đã hoàn tất cập nhật.

Độ phức tạp: O(n+k)O(n + k).

Cài đặt

#include <bits/stdc++.h>

using namespace std;

vector < int > build_diff_array(int n, vector < int >& a)
{
    vector < int > diff(n + 2);
    diff[1] = a[1];
    for (int i = 2; i <= n; ++i)
        diff[i] = a[i] - a[i - 1];

    return diff;
}

void update(int l, int r, int x, vector < int >& diff)
{
    diff[l] += x;
    diff[r + 1] -= x;
}

void print_new_array(int n, vector < int >& diff, vector < int >& a)
{
    for (int i = 1; i <= n; ++i)
    {
        diff[i] += diff[i - 1];
        a[i] = diff[i];

        cout << a[i] << ' ';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector < int > diff = build_diff_array(n, a);

    int k;
    cin >> k;

    while (k--)
    {
        int l, r, x;
        cin >> l >> r >> x;

        update(l, r, x, diff);
    }

    print_new_array(n, diff, a);

    return 0;
}

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

Ý tưởng

Với một mảng hai chiều AA bất kì kích thước m×nm \times n và có các phần tử là ai,j,a_{i, j}, trước hết ta có thêm hai định nghĩa sau:

  • diffhaˋng(A)diff_{hàng}(A): Mảng hai chiều gồm mm hàng, hàng thứ ii thể hiện mảng hiệu của hàng thứ ii tương ứng trên ma trận AA.
  • diffct(A)diff_{cột}(A): Mảng hai chiều gồm nn cột, cột thứ ii thể hiện mảng hiệu của cột thứ ii tương ứng trên ma trận AA.

Trên mảng một chiều, ta có tính chất: sum(c,diff(A))=Asum\big(c, diff(A)\big) = A (xem lại bài viết phần 11). Để tính chất này cũng thỏa mãn trên mảng hai chiều, ta coi rằng mảng AA sẽ tồn tại hàng 00 và cột 0,0, với các giá trị trên hàng và cột này đều bằng 00. Như vậy, mảng hiệu của mảng AA sẽ là mảng diffdiff thỏa mãn:

sum(diff)=Asum(diff) = A

<center>

Với sumsum ở đây là tổng tiền tố hai chiều của mảng diffdiff

</center>

Gọi diff=diffct(diffhaˋng(A)),diff = diff_{cột}\big(diff_{hàng}(A)\big), ta có:

image.png

Lúc này mảng sum(diff)sum(diff) sẽ có giá trị như sau:

image.png

<center>

(theo công thức Bao hàm - Loại trừ)

</center>

Như vậy ta kết luận, sum(diff)=A,sum(diff) = A, mảng diffdiff vừa dựng chính là mảng hiệu của AA.

Thông qua các lập luận trên, ta có thể dựng mảng hiệu hai chiều của AA bằng hai cách:

  • Dùng trực tiếp công thức: diffi,j=ai,jai,j1ai1,j+ai1,j1diff_{i, j} = a_{i, j} - a_{i, j - 1} - a_{i - 1, j} + a_{i - 1, j - 1}.
  • Tính diffhaˋngdiff_{hàng} cho từng hàng của A,A, gán vào mảng AA' rồi tính diffctdiff_{cột} cho mảng AA'.

Tuy nhiên, cách 11 sẽ đơn giản hơn rất nhiều, dưới đây là cài đặt xây dựng mảng hiệu hai chiều theo cách 11:

vector < vector < int > > build_2d_difference_array(int m, int n, const vector < vector < int > >& a)
{
    vector < vector < int > > diff(m + 1, vector < int >(n + 1, 0));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            diff[i][j] = a[i][j] - a[i][j - 1] - a[i - 1][j] + a[i - 1][j - 1];
            
    return diff;
}

Thao tác cập nhật trên mảng hai chiều

Với mảng hiệu hai chiều, ta dễ dàng thực hiện cập nhật tăng thêm một lượng xx cho toàn bộ các ô nằm trong hình chữ nhật con (r1,c1,r2,c2)(r_1, c_1, r_2, c_2) - với (r1,c1)(r_1, c_1) là tọa độ ô trái trên, (r2,c2)(r_2, c_2) là tọa độ ô phải dưới như sau:

  • Khi tính diffhaˋngdiff_{hàng} cho từng hàng của A,A, thao tác cập nhật chỉ tác động lên giá trị của các phần tử ở biên trái (cột c1c_1) và biên phải (cột c2+1c_2 + 1) của bảng.
  • Tiếp tục tính diffctdiff_{cột} cho mảng diffhaˋng,diff_{hàng}, chỉ có các phần tử tại hàng r1r_1r2+1r_2 + 1 sẽ bị tác động bởi thao tác cập nhật.

Từ đây ta rút ra, chỉ có 44 phần tử của diff(A)diff(A) bị tác động bởi thao tác cập nhật, đó là các tọa độ (r1,c1),(r1,c2+1),(r2+1,c1)(r_1, c_1), (r_1, c_2 + 1), (r_2 + 1, c_1)(r2+1,c2+1)(r_2 + 1, c_2 + 1). Trong đó, các phần tử ở (r1,c1)(r_1, c_1)(r2+1,c2+1)(r_2 + 1, c_2 + 1) sẽ tăng thêm một lượng x;x; còn tại (r1,c2+1)(r_1, c_2 + 1)(r2+1,c1)(r_2 + 1, c_1) sẽ trừ đi một lượng xx. Như vậy mỗi thao tác cập nhật chỉ diễn ra trong O(1)O(1).

Sau khi thực hiện hết cập nhật, ta phục hồi lại mảng AA theo công thức:

sum(diff(A))=Asum\big(diff(A)\big) = A

void update(const vector < vector < int > >& diff,
            int r1, int c1, int r2, int c2, int x)
{
    diff[r1][c1] += x;
    diff[r2 + 1][c2 + 1] += x;
    diff[r1][c2 + 1] -= x;
    diff[r2 + 1][c1] -= x;
}

void print_new_array(const vector < vector < int > >& diff,
                     vector < vector < int > >& a, int m, int n)
{
    vector < vector < int > > sum(m + 1, vector < int >(n + 1, 0)); 
    for (int i = 1; i <= m; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + diff[i][j];
            a[i][j] = sum[i][j];
            
            cout << a[i][j] << ' ';
        }
        
        cout << endl;
    }
}

3. Mảng hiệu ba chiều (đọc thêm)

Ta cũng có thể tạo ra mảng hiệu cho mảng trong không gian ba chiều, tuy nhiên việc chứng minh khá phức tạp và cũng ít ứng dụng, do đó trong bài viết này chỉ giới thiệu mang tính chất tham khảo.

Nếu ta coi diffdiff là mảng hiệu ba chiều của A,A, thì bằng phương pháp Bao hàm - Loại trừ, ta có thể dựng được mảng diffdiff theo công thức dưới đây:

image.png

Bây giờ, với một truy vấn cập nhật toàn bộ phần tử trong không gian [x1,x2]×[y1,y2]×[z1,z2],[x_1, x_2] \times [y_1, y_2] \times [z_1, z_2], ta cần cập nhật giá trị tại 88 vị trí, các vị trí này đều nằm tại biên của không gian. Nếu tưởng tượng hình học, thì mảng AA sẽ giống như một hình lập phương chứa số, và các vị trí cần cập nhật sẽ tương ứng với các đỉnh của hình lập phương con đại diện cho không gian cần cập nhật. Ta sẽ tô xen kẽ các đỉnh này theo hai màu đen - trắng, đỉnh có tọa độ (x1,y1,z1)(x_1, y_1, z_1) được tô màu trắng. Phần tử diffdiff ứng với các đỉnh trắng được cộng thêm lượng x;x; ngược lại, phần tử ứng với đỉnh đen thì trừ đi lượng xx.

<center>

</center>

Truy vấn cập nhật lúc này sẽ chỉ tốn thời gian O(1)O(1).

4. Một số bài tập minh họa

Bài toán 1: Tăng đoạn

Đề bài

Cho một dãy AA gồm nn phần tử nguyên không âm a1,a2,,ana_1, a_2, \dots, a_n.

qq truy vấn, mỗi truy vấn có dạng (l,r,d),(l,r,d), có nghĩa là tăng phần tử thứ ll lên dd đơn vị, phần tử thứ l+1l+1 lên 2×d2 \times d đơn vị, ..., phần tử thứ rr lên (rl+1)×d(r-l+1) \times d đơn vị. Nói cách khác, phần tử thứ i[l,r]i \in [l,r] sẽ được tăng thêm (il+1)×d(i-l+1) \times d đơn vị.

Yêu cầu: Hãy in ra dãy aa sau khi thực hiện đủ qq truy vấn?

Input:

  • Dòng đầu tiên chứa số nguyên dương nn.
  • Dòng thứ hai gồm nn số nguyên không âm miêu tả dãy AA.
  • Trên qq dòng sau, mỗi dòng gồm 33 số nguyên (l,r,d)(l,r,d) miêu tả truy vấn.

Ràng buộc:

  • 1n,q1061 \le n,q \le 10^6.
  • 0ai,di105;i:1in0 \le a_i,d_i \le 10^5; \forall i: 1 \le i \le n.

Output:

  • Gồm một dòng in ra nn số, số thứ ii là giá trị của phần tử aia_i sau khi thực hiện qq truy vấn.

Sample Input:

5
1 2 3 4 -5
3
5 5 10
1 5 4
2 3 -1

Sample Output:

5 9 13 20 25 

Ý tưởng

Với mỗi truy vấn [l,r,d][l,r,d] ta có:

  • Phần tử thứ i (lir)i \ (l \le i \le r) sẽ được tăng lên (il+1)×d(i-l+1)\times d đơn vị, đặt β=(il+1)×dβ=i×d(l1)×d\beta = (i-l+1)\times d \Leftrightarrow \beta = i \times d - (l-1)\times d.

Như vậy, với mỗi phần tử i[l,r]i \in [l, r], ta sẽ có hai pha tăng giá trị của nó lên i×di\times d(l1)×d-(l-1)\times d.

Pha thứ hai có thể dễ dàng dùng mảng hiệu để tính. Trong code mẫu nó là mảng CC.

Nhưng pha tăng lên i×di \times d đơn vị, ta cần làm như sau:

  • Gọi cnt[i]cnt[i] là số lần phần tử ii được cộng vào giá trị ii.
  • Dễ thấy, với mỗi thao tác [l,r,d][l,r,d], mảng cnt[i]cnt[i] sẽ tăng lên dd đơn vị từ vị trí ll tới rr. Lúc này ta lại dùng mảng hiệu để tính. Trong code mẫu mảng hiệu được sử dụng là mảng BB.

Ta kết hợp cả mảng cntcnt vào để tính giá trị mảng AA.

Độ phức tạp: O(n)O(n).

Code mẫu

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e6 + 5;
int a[maxn], b[maxn], c[maxn];

void update(int l, int r, int d)
{
    b[l] += d;
    b[r + 1] -= d;
    c[l] += -(l - 1) * d;
    c[r + 1] -= -(l - 1) * d; 
}

void print_array(int n)
{
    for (int i=1; i<=n; i++) 
    {
        b[i] += b[i - 1];
        c[i] += c[i - 1];
        a[i] += b[i] * i + c[i];
		
        cout << a[i] << ' ';
    }
}

signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int q;
    cin >> q;
    while (q--) 
    {
        int l, r, d;
        cin >> l >> r >> d;

        update(l, r, d);
    }

    print_array(n);

    return 0;
}

Bài toán 2: Bỏ thao tác

Đề bài

Nam được mẹ giao nhiệm vụ rèn luyện phép tính cộng cho em trai. Nam dự định vừa rèn luyện tính cộng vừa tạo niềm yêu thích tin học bằng cách cho em trai giải bài toán sau:

Cho một bảng số nguyên gồm có mm hàng và nn cột. Các hàng của bảng được đánh số từ 11 tới mm từ trên xuông dưới, các cột của bảng số được đánh số từ 11 tới nn từ trái qua phải. Giá trị của số nằm ở hàng ii cột jj được kí hiệu là ai,ja_{i, j}. Cần thực hiện lần lượt QQ thao tác, thao tác thứ t (1tQ)t \ (1 \le t \le Q) được mô tả bằng bộ năm số xt,yt,ut,vt,ctx_t,y_t,u_t,v_t,c_t, thao tác này sẽ tăng tất cả các phần tử a(i,j)a(i,j) với mọi xiiut,ytjvtx_i \le i \le u_t, y_t \le j \le v_t lên một lượng là ct (ct>0)c_t \ (c_t > 0).

Nam sẽ yêu cầu em trai ghi ra giấy tất cả các phần tử của bảng số sau khi đã thực hiện cả QQ thao tác. Để kiểm tra xem em mình làm có đúng không, Nam phải tự mình tính toán ra được kết quả đúng trước đã. Sau một hồi tính toán, Nam đã có được bảng số sau khi thực hiện QQ thao tác.

Tuy nhiên, giá trị của các phần tử của bảng số kết quả khá lớn! Nam sợ rằng em trai mình sẽ gặp khó khăn khi thực hiện phép cộng giữa hai số lớn, do đó Nam quyết định bỏ đi một thao tác sao cho sau khi thực hiện Q1Q-1 thao tác còn lại, giá trị lớn nhất của bảng số là nhỏ nhất có thể.

Yêu cầu: Cho bảng số và dãy QQ thao tác, gọi WtW_t là giá trị lớn nhất trong bảng sau khi bỏ đi thao tác thứ t (1tQ)t \ (1 \le t \le Q). Hãy tính min(W1,W2,...,WQ)?\text{min}(W_1,W_2,...,W_Q)?

Input:

  • Dòng đầu chứa hai số nguyên dương n,mn,m .
  • Trên nn dòng tiếp theo, dòng thứ ii gồm nn số nguyên không âm ai,1,ai,2,...,ai,na_{i,1}, a_{i,2}, ..., a_{i,n}.
  • Dòng tiếp theo chứa số nguyên dương QQ.
  • Tiếp theo là QQ dòng, dòng thứ tt gồm năm số nguyên dương xt,yt,ut,vt,ctx_t,y_t,u_t,v_t,c_t - thể hiện một thao tác.

Ràng buộc:

  • 1n×m1061 \le n \times m \le 10^6.
  • 1Q1061 \le Q \le 10^6.
  • ai,j109;i,j:1im,1jna_{i,j} \le 10^9; \forall i, j: 1 \le i \le m, 1 \le j \le n.
  • ci103;i:1iQc_i \le 10^3; \forall i: 1 \le i \le Q.

Output:

  • Gồm một dòng duy nhất là giá trị nhỏ nhất của giá trị lớn nhất của bảng số sau khi loại bỏ đi đúng một thao tác.

Sample Input:

4 4
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1
3
1 1 3 3 2
2 2 3 4 1
3 1 4 3 2

Sample Output:

3

Ý tưởng

Đầu tiên, ta sử dụng kĩ thuật mảng hiệu 2D2D để tăng bảng nhanh chóng. Khi kết thúc QQ truy vấn ta sẽ thu được bảng mới trong O(m×n)O(m \times n).

Sau đó, ta sẽ xét từng truy vấn, xem liệu khi xóa truy vấn này đi thì max\text{max} của bảng sẽ là bao nhiêu.

Giả sử ta xét một truy vấn có dạng là hình chữ nhật màu vàng bên dưới và truy vấn đó có trọng số là cc (tức giá trị tăng lên là cc). Gọi α\alpha là giá trị max\text{max} của bảng sau khi thực hiện QQ truy vấn.

Như vậy, giá trị max\text{max} khi bỏ truy vấn này đi sẽ là giá trị lớn nhất của αw\alpha - w và giá trị lớn nhất trong các vùng màu xanh và đỏ bên dưới:

Phần xanh và đỏ ta có thể tính trước bằng kĩ thuật min, max\text{min, max} tiền tố và hậu tố - áp dụng Quy hoạch động trong O(n)O(n). Các bạn xem lời giải để hiểu rõ hơn!

Độ phức tạp: O(m×n+Q)O(m \times n + Q).

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 1;
int n, m, k;
vector < vector < int > > a;

int pcol[maxn], prow[maxn], scol[maxn], srow[maxn];

struct Query
{
    int x, y, u, v, c;
} q[maxn];

void get_max(int& a, int b)
{
    if (a < b)
        a = b;
}

void add(int x, int y, int u, int v, int c)
{
    a[x][y] += c;
    a[u + 1][y] -= c;
    a[x][v + 1] -= c;
    a[u + 1][v + 1] += c;
}

void solution()
{
    int maxv = 0;
    for (int i = 1; i <= m; ++i)
    {
        prow[i] = prow[i - 1];
        for (int j = 1; j <= n; ++j)
        {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            get_max(maxv, a[i][j]);
            get_max(prow[i], a[i][j]);
        }
    }

    for (int j = 1; j <= n; ++j)
    {
        pcol[j] = pcol[j - 1];
        for (int i = 1; i <= m; ++i)
            get_max(pcol[j], a[i][j]);
    }

    for (int i = m; i >= 1; --i)
    {
        srow[i] = srow[i + 1];
        for (int j = n; j >= 1; --j)
            get_max(srow[i], a[i][j]);
    }

    for (int j = n; j >= 1; --j)
    {
        scol[j] = scol[j + 1];
        for (int i = m; i >= 1; --i)
            get_max(scol[j], a[i][j]);
    }

    int res = maxv;
    for (int i = 1; i <= k; ++i)
    {
        int x = q[i].x, y = q[i].y, u = q[i].u, v = q[i].v;
        int val = max({maxv - q[i].c, prow[x - 1], pcol[y - 1], srow[u + 1], scol[v + 1]});
        res = min(res, val);
    }

    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;

    a = vector < vector < int > >(m + 1, vector < int >(n + 1));
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
        {
            int x;
            cin >> x;
            add(i, j, i, j, x);
        }

    cin >> k;

    for (int i = 1; i <= k; ++i)
    {
        cin >> q[i].x >> q[i].y >> q[i].u >> q[i].v >> q[i].c;
        add(q[i].x, q[i].y, q[i].u, q[i].v, q[i].c);
    }

    solution();

    return 0;
}

IV. Danh sách bài tập tự luyện

Dưới đây là một số bài tập hay, các bạn có thể sử dụng để luyện tập. Ngoài ra còn rất nhiều các bài tập liên quan tới chủ đề này ở các trang web OJ, các bạn có thể tìm thêm tại danh sách bài VNOJ - Mảng cộng dồn.

Mảng tổng tiền tố một chiều

Mảng tổng tiền tố nhiều chiều

Mảng hiệu một chiều

Mảng hiệu nhiều chiều

V. Tài liệu tham khảo


©️ Tác giả: Vũ Quế Lâm từ Viblo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.