Đề bài

Cho một mảng số nguyên A gồm N phần tử. Hãy viết chương trình xử lý Q truy vấn, mỗi truy vấn yêu cầu tính tổng bình phương các phần tử trong đoạn từ chỉ số L đến R (tính theo chỉ mục 1-based).

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên N và Q (1 ≤ N, Q ≤ 105) - số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa N số nguyên A1, A2, ..., AN (-104 ≤ Ai ≤ 104) - các phần tử của mảng.
• Mỗi dòng trong Q dòng tiếp theo chứa hai số nguyên L, R (1 ≤ L ≤ R ≤ N) - chỉ số bắt đầu và kết thúc của đoạn cần tính tổng bình phương.

Dữ liệu ra:

• Với mỗi truy vấn, in ra một số nguyên là tổng bình phương các phần tử trong đoạn [L, R].

Ví dụ:

Input:
5 3
1 -2 3 -4 5
1 3
2 5
1 5

Output:
14
54
55

Gợi ý kỹ thuật:

• Sử dụng mảng cộng dồn để tối ưu tính toán tổng bình phương trong O(1).
• Tạo mảng tiền tố S[i] sao cho S[i] = A12 + A22 + ... + Ai2.
• Tổng bình phương trong đoạn [L, R] có thể tính nhanh bằng công thức:

  sumSq(L, R) = S[R] - S[L - 1]

• Độ phức tạp tổng quát là O(N + Q).