Cho một dãy gồm n số nguyên dương. Dãy không thay đổi trong suốt quá trình xử lý. Bạn cần trả lời q truy vấn; mỗi truy vấn yêu cầu tổng các phần tử từ vị trí l đến vị trí r, tính cả hai đầu mút.
Input
Dòng đầu chứa hai số nguyên n và q.
Dòng thứ hai chứa n số nguyên x1,x2,…,xn.
Mỗi trong q dòng tiếp theo chứa hai số nguyên l và r.
Output
Với mỗi truy vấn, in tổng xl+xl+1+⋯+xr trên một dòng.
Constraints
1≤n,q≤2⋅105.
1≤xi≤109.
1≤l≤r≤n.
Scoring
Subtask 1 (50% số điểm): n,q≤2000.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
7 4
4 2 7 1 3 5 6
1 1
2 5
4 7
1 7
Output
4
13
15
28
Giải thích: Bốn đoạn có tổng lần lượt là 4,2+7+1+3=13,1+3+5+6=15 và tổng cả dãy bằng 28.
Lời giải tóm tắt
Ý tưởng: Xây dựng mảng tổng tiền tố P, trong đó P_0 = 0 và P_i = x_1 + x_2 + ... + x_i. Tổng của đoạn đóng [l, r] là
Ý tưởng:P_r - P_{l-1}.
Ý tưởng: Các tổng có thể lớn hơn miền số nguyên 32 bit, nên dùng số nguyên 64 bit.
Chứng minh đúng:P_r chứa tổng của các phần tử từ 1 đến r, còn P_{l-1} chứa đúng phần đứng trước đoạn truy vấn. Khi trừ hai giá trị, mọi phần tử từ 1 đến l-1 bị triệt tiêu và chỉ còn x_l + ... + x_r. Do đó công thức trả lời đúng từng truy vấn.
Độ phức tạp: Tiền xử lý O(n), mỗi truy vấn O(1), tổng thời gian O(n+q) và bộ nhớ O(n).