Problem

1 /6


جمع در بخش - 1

Theory Click to read/hide

ما در مورد نحوه محاسبه سریع مجموع بازه l...r در یک آرایه استاتیک a در مجانبی کمتر از O(n) مشکل داریم.
بیایید آرایه a را به k بلوک هم اندازه تقسیم کنیم و ابتدا مجموع عناصر هر یک از آنها را محاسبه کنیم.
حالا هنگام پاسخ دادن به درخواست، می‌توانیم عناصر آرایه a را مرور کنیم و آنها را به نتیجه اضافه کنیم، همچنین اگر یکی از بلوک‌ها در داخل سگمنت قرار داشته باشد، می‌توانیم مجموع آن را به نتیجه اضافه کنیم و از آن بگذریم. عناصر این بلوک.
حداکثر تعداد عملیات در هر پرس و جو با این الگوریتم n / k + k است، بنابراین k بهینه برابر با جذر n است.
 

Problem

با توجه به یک آرایه a به طول n (\(1 <= n <= 2 \cdot 10^6\ )< /span>، \(1 <= a_i <= 10^9\)). همچنین درخواست‌های m (\(1 <= m <= 500\)) مانند l داده می‌شود، r (\(1 <= l <= r <= n\)).

برای هر درخواست، مجموع اعداد بین l و r را چاپ کنید. code> به n.

 

نمونه‌ها
<سر> <بدن>
# ورودی خروجی
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5

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!