# Hướng dẫn giải: I. Bài cuối cùng

:::info
**Ý tưởng cốt lõi:** Thay vì duyệt 2 vòng lặp lồng nhau gây quá thời gian (TLE), ta sẽ gom nhóm các phép tính và dùng mảng cộng dồn (Prefix Sum) để trả lời truy vấn trong $O(1)$.
:::

## 1. Phân tích từ ví dụ để đưa ra quy luật
Hãy nhìn vào ví dụ của đề bài: Xét truy vấn từ $l = 2$ đến $r = 4$.
Theo yêu cầu, ta phải tính tổng các tích:
$S = a_2 \times a_3 + a_3 \times a_4 + a_2 \times a_4$

Nếu sắp xếp và gom nhóm các nhân tử chung lại, ta có thể tách biểu thức trên thành:
$S = a_4 \times (a_2 + a_3) + a_3 \times (a_2)$

> **=> Suy ra quy luật tổng quát:** > Để tính tổng các tích trong một đoạn, ta lấy từng phần tử $a_i$ nhân với **tổng của tất cả các phần tử đứng ngay trước nó** (trong phạm vi đang xét).

## 2. Hình thành ý tưởng Mảng tiền tố
Từ quy luật gom nhóm trên, rất tự nhiên để chúng ta nghĩ ra việc tạo một **mảng tiền tố lưu tổng các tích** (gọi là `pre2`). Việc này giúp ta tránh bị TLE như cách duyệt trâu hai vòng lặp lồng nhau.

Mảng `pre2[i]` sẽ lưu kết quả của bài toán nếu xét từ phần tử đầu tiên ($1$) đến $i$.
Công thức tính lúc khởi tạo:
`pre2[i] = pre2[i-1] + a[i] * (Tổng từ a[1] đến a[i-1])`

**Đoạn code minh họa bước khởi tạo:**

ll sum = 0;
for(int i = 1; i <= n; i ++) {
    cin >> arr[i];
    ...
    pre2[i] = pre2[i - 1] + arr[i] * sum;  // Mảng lưu tổng tích
    sum += arr[i];                         // Cập nhật tổng các số phía trước
}

## 3. Tại sao `pre2[r] - pre2[l - 1]` là chưa đủ?
Thông thường với mảng cộng dồn, để lấy tổng trong đoạn $[l, r]$, ta hay dùng `pre[r] - pre[l-1]`. Tuy nhiên, với mảng tổng tích này thì **chưa đủ**.

Hãy nhìn lại ví dụ $l = 2, r = 4$. Giả sử ta lấy `pre2[4] - pre2[1]`:
Bản thân `pre2[4]` đang chứa:
* $a_4 \times (a_1 + a_2 + a_3)$
* $a_3 \times (a_1 + a_2)$
* $a_2 \times (a_1)$

Trừ đi `pre2[1]` (bằng 0), biểu thức vẫn y nguyên như trên. Trong khi đó, đáp án thực sự của đoạn từ $2 \rightarrow 4$ chỉ là $a_4 \times (a_2 + a_3) + a_3 \times (a_2)$.
Rõ ràng, kết quả đang bị **dư thừa** các phép nhân với $a_1$ (các phần tử đứng trước $l$). Ta cần loại bỏ thằng $a_1$ này ra khỏi tất cả các cụm.

## 4. Xử lý phần dư thừa bằng mảng cộng dồn thường
Do đó, ta cần tạo thêm một mảng cộng dồn thường (gọi là `pre1`) lưu tổng các phần tử để tính phần bị dư.

Nhìn lại phần bị dư ở trên:
Ta có $a_4 \times a_1$ , $a_3 \times a_1$ và $a_2 \times a_1$.
Rút nhân tử chung ra, phần dư chính là: $a_1 \times (a_2 + a_3 + a_4)$.

:::success
**Quy luật phần dư:** Phần dư luôn bằng: **(Tổng các phần tử từ 1 đến l-1)** nhân với **(Tổng các phần tử từ l đến r)**.
Dùng mảng `pre1`, phần dư = `pre1[l - 1] * (pre1[r] - pre1[l - 1])`
:::

**Hoàn thành vòng lặp khởi tạo ở phía trên**

ll sum = 0;
for(int i = 1; i <= n; i ++) {
    cin >> arr[i];
    // mảng cộng dồn mới được thêm vào
    pre1[i] = pre1[i - 1] + arr[i];
    pre2[i] = pre2[i - 1] + arr[i] * sum;  // Mảng lưu tổng tích
    sum += arr[i];                         // Cập nhật tổng các số phía trước
}

## 5. Ví dụ chốt lại ($l = 3, r = 4$)
Để hiểu rõ công thức cuối cùng, ta thử lấy $l = 3, r = 4$. Yêu cầu bài toán lúc này chỉ là tính: $a_3 \times a_4$.

**Bước 1:** Lấy `pre2[4] - pre2[2]`
* `pre2[4]` có: $a_4(a_1 + a_2 + a_3) + a_3(a_1 + a_2) + a_2(a_1)$
* `pre2[2]` có: $a_2(a_1)$
* Trừ đi ta còn: $a_4(a_1 + a_2 + a_3) + a_3(a_1 + a_2)$

**Bước 2:** Trừ đi phần dư thừa
Phần dư thừa trong cụm trên là $a_4(a_1 + a_2)$ và $a_3(a_1 + a_2)$.
Gom lại ta được phần dư = $(a_1 + a_2) \times (a_3 + a_4)$.
Chính là: `pre1[2] * (pre1[4] - pre1[2])`

Lấy biểu thức ở Bước 1 trừ đi Bước 2, ta sẽ triệt tiêu hết $a_1, a_2$, phần còn lại đúng bằng $a_3 \times a_4$.

:::danger
**Công thức tổng quát cuối cùng cho mọi truy vấn l, r:**
`Đáp án = pre2[r] - pre2[l - 1] - (pre1[r] - pre1[l - 1]) * pre1[l - 1]`
:::

**Phần Code giải quyết truy vấn**

for(int i = 1; i <= q; i ++) {
    int l, r; cin >> l >> r;
    ll ans = pre2[r] - pre2[l - 1] - (pre1[r] - pre1[l - 1]) * pre1[l - 1];
    cout << ans << '\n';
}