Hiểu bài toán

Bài toán yêu cầu tìm giá trị lớn nhất của một dãy số sau khi thực hiện m truy vấn. Dãy số ban đầu có n phần tử, tất cả đều bằng 0. Mỗi truy vấn có dạng Q(u, v, k), nghĩa là tăng giá trị của các phần tử từ chỉ số u đến v lên k. Sau khi thực hiện tất cả m truy vấn, ta cần tìm giá trị lớn nhất trong dãy số thu được.

Các cách tiếp cận

Cách Duyệt tuần tự với mảng

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

const int MAX = 1e7 + 10;

int n, m;
long long a[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    while(m--)
    {
        int u, v;
        long long k;
        cin >> u >> v >> k;
        a[u] += k;
        a[v + 1] -= k;
    }

    long long res = a[0];
    for(int i = 2; i <= n; ++i)
    {
        a[i] += a[i - 1];
        res = max(res, a[i]);
    }

    cout << res;

    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Phương pháp này sử dụng kỹ thuật 'difference array' (mảng chênh lệch). Thay vì cập nhật trực tiếp từng phần tử trong đoạn [u, v] (tốn O(n) mỗi truy vấn), ta chỉ cập nhật hai vị trí: a[u] += k và a[v+1] -= k. Sau khi xử lý xong tất cả các truy vấn, ta thực hiện một lần duyệt duy nhất từ 1 đến n để tính tổng tiền tố (prefix sum), giá trị tại mỗi chỉ số i chính là giá trị a[i] sau khi áp dụng tất cả các truy vấn. Trong quá trình duyệt, ta đồng thời tracking giá trị lớn nhất. Cách này tối ưu về thời gian xử lý nhưng tốn bộ nhớ O(n) để lưu mảng.

Cách Duyệt tuần tự với vector

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

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

    long long n, m;
    cin >> n >> m;

    vector<long long> diff(n + 2, 0);

    while (m--) {
        long long l, r, k;
        cin >> l >> r >> k;
        diff[l] += k;
        diff[r + 1] -= k;
    }

    long long mx = 0, cur = 0;
    for (long long i = 1; i <= n; i++) {
        cur += diff[i];
        mx = max(mx, cur);
    }

    cout << mx;
    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Đây là phiên bản khác của phương pháp Difference Array, sử dụng vector của C++ thay vì mảng tĩnh. Logic xử lý hoàn toàn tương tự: cập nhật hai đầu mút của đoạn interval vào vector, sau đó duyệt để tính tổng tiền tố và tìm max. Việc sử dụng vector giúp linh hoạt hơn về bộ nhớ và tránh lỗi tràn mảng (buffer overflow) nếu khai báo mảng quá lớn trên stack, mặc dù với n=10^7 thì việc khai báo mảng global/static là bắt buộc.

Cách Sử dụng biến đếm

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

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

    long long n, m;
    cin >> n >> m;

    vector<long long> events(n + 2, 0);

    while(m--) {
        long long u, v, k;
        cin >> u >> v >> k;
        events[u] += k;
        events[v+1] -= k;
    }

    long long current_val = 0;
    long long max_val = 0;

    for(int i = 1; i <= n; ++i) {
        current_val += events[i];
        if(current_val > max_val) {
            max_val = current_val;
        }
    }

    cout << max_val;
    return 0;
}

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Đây là cách tiếp cận chuẩn để giải quyết bài toán Range Update Point Query (RUPQ) bằng kỹ thuật Difference Array. Ta tạo một mảng 'sự kiện' (events hoặc diff). Với mỗi truy vấn tăng giá trị từ u đến v lên k, ta đánh dấu sự kiện tăng k tại u và trừ k tại v+1. Sau đó, duyệt từ 1 đến n, cộng dồn các sự kiện vào biến currentval. Giá trị currentval tại mỗi bước chính là giá trị của phần tử tại vị trí đó sau khi áp dụng hết các truy vấn. Ta chỉ cần tìm giá trị lớn nhất trong quá trình này.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Kỹ thuật Difference Array (Mảng chênh lệch) là chìa khóa để giảm độ phức tạp thời gian từ O(m*n) xuống O(n + m). Thay vì cập nhật cả một đoạn, ta chỉ cần đánh dấu sự thay đổi tại đầu và cuối đoạn.
• Vì n có thể lên tới 10^7, cần phải tối ưu bộ nhớ và tránh các thao tác nhập/xuất thừa. Sử dụng các thư viện chuẩn C++ với tối ưu hóa I/O (iosbase::syncwith_stdio(0); cin.tie(0);) là cần thiết.

Lỗi thường gặp

• Lỗi tràn số (Integer Overflow): Tổng giá trị k có thể rất lớn (tới 10^9 * 2*10^5), do đó biến lưu trữ phải là kiểu dữ liệu 64-bit (long long trong C++).
• Lỗi chỉ số mảng: Khi thực hiện diff[v+1] -= k, cần đảm bảo rằng chỉ số v+1 không vượt quá kích thước mảng được cấp phát (vì n có thể bằng 10^7).
• Bỏ qua chỉ số 0: Trong một số cách implement mảng, phần tử tại chỉ số 0 có thể được dùng để lưu tổng ban đầu hoặc bị bỏ qua, cần duyệt đúng phạm vi từ 1 đến n.