Tổng đoạn tĩnh (Static Range Sum Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có một mảng gồm $n$ số nguyên

Bạn cần xử lý $q$ truy vấn độc lập. Mỗi truy vấn cho hai chỉ số $a,b$ và yêu cầu tính tổng tất cả phần tử có vị trí từ $a$ đến $b$, tính cả hai đầu mút.

Nói cách khác, với mỗi truy vấn $[a,b]$, cần tính

Input

• Dòng đầu chứa hai số nguyên $n,q$: số phần tử của mảng và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\ldots,x_n$.
• Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $a,b$, mô tả một đoạn chỉ số $[a,b]$.

Output

Với mỗi truy vấn, in trên một dòng tổng các phần tử của mảng trong đoạn $[a,b]$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n,q\le 2\cdot10^5$

• $1\le x_i\le10^9$

• $1\le a\le b\le n$

• Subtask 1 — 20%: $n,q\le40$

• Subtask 2 — 30%: Mọi truy vấn có dạng $[1,r]$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3

Output

11
2
24
4

Giải thích

Mảng trong ví dụ là

• Truy vấn $[2,4]$ lấy các giá trị $2,4,5$, nên tổng là $2+4+5=11$.
• Truy vấn $[5,6]$ lấy hai giá trị $1,1$, nên tổng là $2$.
• Truy vấn $[1,8]$ lấy toàn bộ mảng, có tổng $24$.
• Truy vấn $[3,3]$ chỉ chứa phần tử thứ $3$, nên kết quả là $4$.