Problem

1 /6


Tổng trên đoạn - 1

Theory Click to read/hide

Chúng ta gặp vấn đề về cách tính nhanh các tổng trên khoảng l...r trong một mảng tĩnh a với số tiệm cận nhỏ hơn O(n).
Hãy chia mảng a thành k khối có cùng kích thước và trước tiên hãy tính tổng các phần tử của mỗi khối.
Bây giờ, khi trả lời yêu cầu, chúng ta có thể duyệt qua các phần tử của mảng a và thêm chúng vào kết quả, đồng thời nếu một trong các khối nằm bên trong phân đoạn, thì chúng ta có thể cộng tổng của nó vào kết quả và bỏ qua các phần tử của khối này.
Số lượng thao tác tối đa cho mỗi truy vấn với thuật toán này là n / k + k, vì vậy k tối ưu bằng căn bậc hai của n.
 

Problem

Cho một mảng a có độ dài n (\(1 <= n <= 2 \cdot 10^6\ ), \(1 <= a_i <= 10^9\)). Cũng đưa ra các truy vấn m (\(1 <= m <= 500\)) như l, r (\(1 <= l <= r <= n\)).

Đối với mỗi truy vấn, hãy in tổng các số giữa l và r. Các phần tử được đánh số bắt đầu bằng 1 thành n.

 

Ví dụ
<đầu>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Đầu vào Đầu ra
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5