Tổng Mưa Vùng Đê Sông Hồng

Mô tả

Mỗi mùa mưa, các cán bộ quản lý đê điều dọc sông Hồng lại theo dõi sát sao lượng mưa tại các trạm quan trắc đặt liền nhau theo tuyến đê. Có n trạm đánh số từ 1 đến n, lượng mưa ghi nhận trong ngày hôm nay tại trạm thứ i là a[i] milimét. Người chỉ huy cần trả lời q truy vấn, mỗi truy vấn cho hai chỉ số L và R (1 ≤ L ≤ R ≤ n), yêu cầu tính tổng lượng mưa từ trạm L đến trạm R. Vì số truy vấn rất lớn, bạn cần trả lời cực kỳ nhanh, không được duyệt lại từng trạm trong mỗi truy vấn.

Đầu vào

• Dòng đầu chứa hai số nguyên n và q (1 ≤ n ≤ 100000, 1 ≤ q ≤ 100000).
• Dòng thứ hai chứa n số nguyên a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 1000).
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R (1 ≤ L ≤ R ≤ n).

Đầu ra

• Với mỗi truy vấn, in ra một dòng là tổng lượng mưa từ trạm L đến trạm R.

Ràng buộc

• 1 ≤ n, q ≤ 100000.
• 0 ≤ a[i] ≤ 1000.
• 1 ≤ L ≤ R ≤ n.
• Tổng lớn nhất cho một truy vấn: 100000 × 1000 = 10^8, an toàn với số nguyên 32 bit.

Ví dụ

Đầu vào:

5 3 10 20 30 40 50 1 3 2 5 4 4

Đầu ra:

60 140 40

Giải thích:

• Mảng: [10, 20, 30, 40, 50].
• Mảng tiền tố tổng P: P[0] = 0, P[1] = 10, P[2] = 30, P[3] = 60, P[4] = 100, P[5] = 150.
• Truy vấn 1 3: tổng = P[3] - P[0] = 60 - 0 = 60.
• Truy vấn 2 5: tổng = P[5] - P[1] = 150 - 10 = 140.
• Truy vấn 4 4: tổng = P[4] - P[3] = 100 - 60 = 40 (chỉ trạm thứ 4).