Problem

1 /6


مجموع الجزء - 1

Theory Click to read/hide

لدينا مشكلة حول كيفية حساب المجاميع بسرعة على الفاصل الزمني l ... r في مصفوفة ثابتة a في أقل من O (n) مقارب.
دعنا نقسم المصفوفة a إلى كتل k من نفس الحجم ونحسب أولاً مجموع العناصر لكل منها.
الآن ، عند الإجابة على الطلب ، يمكننا استعراض عناصر المصفوفة a وإضافتها إلى النتيجة ، أيضًا إذا كانت إحدى الكتل موجودة داخل المقطع ، فيمكننا إضافة مجموعها إلى النتيجة وتخطي عناصر هذه الكتلة.
الحد الأقصى لعدد العمليات لكل استعلام بهذه الخوارزمية هو n / k + k ، وبالتالي فإن k الأمثل يساوي الجذر التربيعي لـ n.
& nbsp؛

Problem

إعطاء صفيف بطول n ( \ (1 & lt؛ = n & lt؛ = 2 \ cdot 10 ^ 6 \ ) ، \ (1 & lt؛ = a_i & lt؛ = 10 ^ 9 \) ). قدم أيضًا m ( \ (1 & lt؛ = m & lt؛ = 500 \) ) طلبات بحث مثل l ، r ( \ (1 & lt؛ = l & lt؛ = r & lt؛ = n \) ).

لكل استعلام ، اطبع مجموع الأرقام بين l و r شاملًا. & nbsp؛ يتم ترقيم العناصر بدءًا من 1 إلى 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!