Module: Kök ayrışması


Problem

1 /6


Segmentteki toplam - 1

Theory Click to read/hide

O(n)'den küçük asimptotiklerde a statik dizisindeki l...r aralığındaki toplamları hızlı bir şekilde hesaplama konusunda bir sorunumuz var.
a dizisini aynı büyüklükteki k bloğa bölelim ve önce her birinin eleman toplamını hesaplayalım.
Artık talebe cevap verirken a dizisinin elemanlarını gözden geçirip sonuca ekleyebiliriz, ayrıca bloklardan biri segmentin içindeyse onun toplamını sonuca toplayıp sonucu atlayabiliriz. bu bloğun öğeleri.
Bu algoritma ile sorgu başına maksimum işlem sayısı n / k + k'dir, yani optimal k, n'nin kareköküne eşittir.
 

Problem

n uzunluğunda bir a dizisi verildi (\(1 <= n <= 2 \cdot 10^6\ )< /span>, \(1 <= a_i <= 10^9\)). Ayrıca l gibi m (\(1 <= m <= 500\)) sorguları verildi, r (\(1 <= l <= r <= n\)).

Her sorgu için l ve r dahil olmak üzere sayıların toplamını yazdırın. Öğeler 1 ile n arasında.

 

Örnekler

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!

# Girdi Çıktı
1
4
1 2 3 4
2
1 4
1 1
 10
1
2
5
5 5 5 5 5
1
5 5
 5