東京海上日動プログラミングコンテスト2022 (AtCoder Beginner Contest 256) F - Cumulative Cumulative Cumulative Sum (500)
コンテスト中の考察
式変形を考えるとある要素が変わったときのある別の位置への影響度合いが計算できる
出力クエリ毎にそれまでの更新クエリを適用する必要があり間に合わない
解説の解法
$ D_x = \sum_i \frac{(x-i+1)(x-i+2)}{2} A_iとなる
これは$ A_i, iA_i, i^2A_iの和の和に分解できる
3種類のBITを持ってクエリ毎に更新する
最初の要素を$ i = 0ではなく$ i = 1にする必要があるのに注意が必要