Range Add

クエリについてそれぞれ愚直に加算を行っていては、実行制限時間に間に合いません。

ここで、いもす法というアルゴリズムを利用しましょう。

例えば、配列の $[2, 5]$ に加算を行いたい場合は、図１のような加算を行った後に、右方向に累積和をとる (図２) ことにより区間の加算を行うことができます。

0 1 0 0 0 -1 0

0 1 1 1 1 0 0

しかし、図２の累積和をとる処理をクエリのたびに行っていては結局は愚直に処理を行うのと同じです。
ここで、Binary Indexed Tree や Segment Tree などのデータ構造を用いることによって、高速に処理を行うことができます。

具体的には、区間を加算するクエリは図１のような加算をします。そうすると、$A_x$ の値は、$[1, x]$ の区間和を取ることにより得ることができます。

よって、この問題を $O(Q \log N)$ で解くことができ、十分に高速です。