Bài 34.1. Theo Dõi Dòng Chảy Năng Lượng - Độ khó: Khá

Trong một hệ thống phân phối năng lượng lớn, các kỹ sư cần theo dõi lượng năng lượng đi qua từng đoạn đường ống trong một khoảng thời gian nhất định. Hệ thống được mô hình hóa như một đường thẳng với \(N\) điểm đo liên tiếp. Tại mỗi điểm đo \(i\), có một giá trị \(E_i\) biểu thị lượng năng lượng ròng được tích lũy (có thể dương hoặc âm nếu năng lượng bị tiêu hao). Các kỹ sư thường xuyên cần biết tổng lượng năng lượng ròng trong một phân đoạn đường ống từ điểm đo \(L\) đến điểm đo \(R\). Hãy giúp họ xây dựng một hệ thống để trả lời các truy vấn này một cách nhanh chóng.

INPUT FORMAT

Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)) - số lượng điểm đo. Dòng thứ hai chứa \(N\) số nguyên \(E_1, E_2, \dots, E_N\) (\( -10^9 \le E_i \le 10^9\)) - lượng năng lượng ròng tại mỗi điểm đo. Dòng thứ ba chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)) - số lượng truy vấn. \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le N\)) - phạm vi truy vấn.

OUTPUT FORMAT

Với mỗi truy vấn, in ra tổng lượng năng lượng ròng trong phân đoạn từ \(L\) đến \(R\) trên một dòng riêng biệt.

Ví dụ:

Input:

7
10 -5 12 8 -3 15 -7
3
1 3
4 6
2 2

Output:

17
20
-5

Giải thích:

• Mảng năng lượng \(E = [10, -5, 12, 8, -3, 15, -7]\).
• Mảng cộng dồn \(P\) (để \(P[i]\) là tổng từ \(E_1\) đến \(E_i\)):
  • \(P[0] = 0\)
  • \(P[1] = 10\)
  • \(P[2] = 10 + (-5) = 5\)
  • \(P[3] = 5 + 12 = 17\)
  • \(P[4] = 17 + 8 = 25\)
  • \(P[5] = 25 + (-3) = 22\)
  • \(P[6] = 22 + 15 = 37\)
  • \(P[7] = 37 + (-7) = 30\)
• Truy vấn 1: \(L=1, R=3\). Tổng từ \(E_1\) đến \(E_3\) là \(E_1 + E_2 + E_3 = 10 + (-5) + 12 = 17\). Dùng mảng cộng dồn: \(P[3] - P[1-1] = P[3] - P[0] = 17 - 0 = 17\).
• Truy vấn 2: \(L=4, R=6\). Tổng từ \(E_4\) đến \(E_6\) là \(E_4 + E_5 + E_6 = 8 + (-3) + 15 = 20\). Dùng mảng cộng dồn: \(P[6] - P[4-1] = P[6] - P[3] = 37 - 17 = 20\).
• Truy vấn 3: \(L=2, R=2\). Tổng từ \(E_2\) đến \(E_2\) là \(E_2 = -5\). Dùng mảng cộng dồn: \(P[2] - P[2-1] = P[2] - P[1] = 5 - 10 = -5\).