Courses

データ構造

ルート分解

Module: ルート分解

Problem

1 /6

セグメントの合計 - 1

Theory Click to read/hide

静的配列 a の区間 l...r の合計を O(n) 未満の漸近線で素早く計算する方法に関する問題があります。

配列 a を同じサイズの k 個のブロックに分割し、最初にそれぞれの要素の合計を計算しましょう。

リクエストに応答するとき、配列 a の要素を調べて結果に追加できます。また、ブロックの 1 つがセグメント内にある場合は、その合計を結果に追加して、結果をスキップできます。このブロックの要素。

このアルゴリズムでのクエリあたりの最大操作数は n / k + k であるため、最適な k は n の平方根に等しくなります。

Problem

長さ 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 までの数値の合計を出力します。要素には 1 から n へ。



 

例


<頭>

<本体>

                                      
                                       1000
                                             ms
                                        
 
                                            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!
                                     
                                 
                                 
                                     
                                 
                                 
                                     
                                 
                             
                             
                                
                                     

	
                                
                             
                         
                        
                     

#
入力
出力


1

4

1 2 3 4

2

1 4

1 1

10

1


2

5

5 5 5 5 5

1

5 5

5

Courses データ構造 ルート分解

Module: ルート分解

1 /6

セグメントの合計 - 1

Theory Click to read/hide

Problem

例

Teacher commentary

Your Program

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

Courses

データ構造

ルート分解