区間和の和

Tester解 みどりむし：セグ木を使った解法

解説

考えやすくするためクエリ２の区間を半開区間$[L,R)$としておきます。

$\sum_{j = L}^{i}$の部分を$S_i$とします。

$S_i$はそれぞれ以下のようになります。

$$\begin{aligned} S_L &= A_L \\ S_{L+1} &= A_L + A_{L+1}\\ \vdots \\ S_{R-1} &= A_L + A_{L+1} + \cdots + A_{R-1} \end{aligned}$$

よって、

$$\begin{aligned} \sum_{i = L}^R S_i &= \sum_{i=L}^R(R-i) \times A_i \\ &= R\sum_{i=L}^{R}A_i - \sum_{i=L}^{R}iA_i \end{aligned}$$

となります。それそれの総和はFenwick Treeで管理すれば総和の取得、要素の更新が高速に行えます。

実装