Tổng đoạn với nhiều truy vấn

Dễ

mảngtổng tiền tố3 test · 3 giây

Cho dãy n số nguyên và q truy vấn, mỗi truy vấn gồm l r: in tổng a_l + … + a_r.

Cộng lại từ đầu cho mỗi truy vấn là O(n·q) — quá chậm với n, q = 10⁵. Hãy dùng mảng tổng tiền tố.

Dữ liệu vào

Dòng 1: n q (1 ≤ n, q ≤ 10⁵).

Dòng 2: n số nguyên (|aᵢ| ≤ 10⁹).

q dòng tiếp: l r (1 ≤ l ≤ r ≤ n).

q dòng, mỗi dòng một tổng (có thể vượt 32-bit).

Input

Output

15
9
3

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.