Hiểu bài toán

Cho mảng A gồm N phần tử. Giá trị của một đoạn [l, r] được định nghĩa là tổng tất cả các tích Ai * Aj với l <= i < j <= r. Yêu cầu xử lý Q truy vấn, mỗi truy vấn cho l, r và cần in ra giá trị tương ứng của đoạn [l, r]. N, Q <= 10^5, các giá trị A_i <= 50000.

Ví dụ: Với mảng [1, 2, 3, 4] và đoạn [1, 3], ta có các cặp (1,2), (1,3), (2,3) tương ứng các tích là 12=2, 13=3, 2*3=6. Tổng là 2+3+6=11.

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

Cách Brute Force

long long ans = 0;
for(int i = l; i <= r; i++) {
    for(int j = i + 1; j <= r; j++) {
        ans += a[i] * a[j];
    }
}
cout << ans << '\n';

• Time Complexity: O(Q * N^2)
• Space Complexity: O(N)

Với mỗi truy vấn, duyệt qua tất cả các cặp (i, j) thỏa mãn l <= i < j <= r và cộng dồn tích Ai * Aj vào kết quả. Với N, Q lên tới 10^5, độ phức tạp này là quá chậm (khoảng 10^15 thao tác).

Cách Công thức tổng quát (Prefix Sum)

// Chuẩn bị:
vector<long long> prefixSum(n + 1);
vector<long long> prefixSqr(n + 1);
for (int i = 1; i <= n; i++) {
    prefixSum[i] = prefixSum[i-1] + a[i];
    prefixSqr[i] = prefixSqr[i-1] + a[i] * a[i];
}

// Xử lý truy vấn:
long long sum = prefixSum[r] - prefixSum[l-1];
long long sumSqr = prefixSqr[r] - prefixSqr[l-1];
long long ans = (sum * sum - sumSqr) / 2;
cout << ans << '\n';

• Time Complexity: O(N + Q)
• Space Complexity: O(N)

Sử dụng công thức đại số để tính tổng các tích.

Xét tổng bình phương của đoạn [l, r]: (sum)^2 = (Al + A{l+1} + ... + Ar)^2 => sum^2 = sum(Ai^2) + 2 * sum(Ai * Aj) với i < j.

Do đó, tổng các tích cần tìm (gọi là S) là: S = [ (sum(Al..Ar))^2 - sum(Al^2..Ar^2) ] / 2

Ta có thể tính sum(Al..Ar) và sum(Al^2..Ar^2) trong O(1) bằng mảng tổng tiền tố (prefix sum).

• sum(Al..Ar) = prefixSum[r] - prefixSum[l-1]
• sum(Al^2..Ar^2) = prefixSqr[r] - prefixSqr[l-1]

Độ phức tạp thuật toán: O(N) để xây dựng prefix arrays và O(1) cho mỗi truy vấn.

Cách Phương pháp cộng dồn

// Chuẩn bị:
// prefix_1[i] = sum(A_1...A_i)
// prefix_2[i] = sum(A_1 * (A_1 + ... + A_i))
// prefix_2[i] = prefix_2[i-1] + A[i] * prefix_1[i]

long long sum1 = prefix_1[r-1] - prefix_1[l-1];
long long sum2 = prefix_2[r-1] - prefix_2[l-1];
long long ans = sum1 * prefix_1[r] - sum2;
cout << ans << '\n';

• Time Complexity: O(N + Q)
• Space Complexity: O(N)

Đây là một cách tiếp cận khác để tính tổng tích. Gọi S(l, r) là tổng tích của đoạn [l, r].

Ta có thể tính tổng tích của đoạn [l, r] bằng cách phân tích: S(l, r) = sum{j=l+1}^{r} ( Aj * sum{i=l}^{j-1} Ai )

Sử dụng mảng prefix2 để lưu tổng tích tích (prefix2[i] = sum{k=1}^{i} Ak * sum{t=1}^{k} At). Khi đó, tổng tích của đoạn [l, r] có thể tính bằng cách sửa đổi tổng tích đã tính trước đó.

Công thức: Ta cần tính sum{j=l}^{r} (Aj * sum{i=l}^{j-1} Ai). Mảng prefix1 cho phép lấy tổng tiền tố. Mảng prefix2 cho phép lấy tổng của các tích.

Công thức cuối cùng: (PrefixSum[r-1] - PrefixSum[l-1]) * PrefixSum[r] - (Prefix2[r-1] - Prefix2[l-1]). Phương pháp này chính xác nhưng công thức tổng quát (Approach 2) trực quan và dễ nhớ hơn.

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

Bài học kinh nghiệm

• Bài toán có thể quy về tính tổng bình phương và tổng bình thường của đoạn mảng bằng công thức: (Tổng)^2 = Tổng bình phương + 2 * Tổng tích.
• Tổng tích của đoạn [l, r] bằng 1/2 của ( (Tổng đoạn [l, r])^2 - (Tổng bình phương đoạn [l, r]) ).
• Sử dụng mảng tổng tiền tố (Prefix Sum) để trả lời truy vấn interval sum trong thời gian O(1).

Lỗi thường gặp

• Overflow: Các giá trị A_i có thể lên tới 510^4, và tổng có thể lên tới 10^5 * 510^4 = 510^9. Khi tính tổng bình phương (sum^2), kết quả có thể lên tới (510^9)^2 = 2.5*10^19. Do đó, bắt buộc phải sử dụng kiểu dữ liệu 64-bit (long long trong C++).
• Sai công thức: Nhầm lẫn giữa công thức tính tổng tích và công thức tính tổng bình phương. Phải nhớ rõ: (sum)^2 = sum(Ai^2) + 2 * sum(Ai*A_j).
• Lỗi index: Khi sử dụng prefix sum, cần chú ý index l-1. Ví dụ tổng từ l đến r là prefix[r] - prefix[l-1]. Nếu l=1 thì prefix[l-1] là prefix[0] = 0.