CSES - Static Range Sum Queries | Truy vấn tổng mảng tĩnh

Xem PDF



Thời gian:
Pypy 3 2.0s
Python 3 4.0s

Tác giả:
Dạng bài
Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: tổng các phần tử trong đoạn [\(a, b\)] là bao nhiêu?

Input

  • Dòng đầu tiên là hai số nguyên \(n\)\(q\): số phần tử và truy vấn.
  • Dòng thứ hai là \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các phần tử của mảng.
  • \(q\) dòng cuối cùng là các truy vấn. Mỗi dòng là hai số nguyên \(a\)\(b\): tổng các phần tử trong đoạn \([a, b]\) là bao nhiêu?

Output

  • In ra đáp án của mỗi truy vấn.

Constraints

  • \(1 \le n, q \le 2 \cdot 10^5\)
  • \(1 \le x_i \le 10^9\)
  • \(1 \le a \le b \le n\)

Example

Sample input

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

Sample output

11
2
24
4


Bình luận