本解説は公式解説と本質的に等価なアルゴリズムを少し異なる視点から着想するものです。

\(x, y\) を形式的な不定元として、\(\sum A _ i B _ i\) の代わりに \(\sum (x + A _ i) (y + B _ i)\) を計算することを考えます。 これは \(x, y\) についての \(1\) 次式なので \(c _ 0 + c _ 1 x + c _ 2 y + c _ 3 x y\) の形で表され、\(c _ 0\) が本来のクエリの答えとなります。 一見すると問題を複雑にしただけですが、「\(A _ i\) に一様に \(s\) を加算する」という操作を「\(x\) に \(x + s\) を代入する」と言い換えることができます。同様に、\(B _ i\) への加算も \(y\) への代入とい換えられ、それらの合成も \(x\) と \(y\) への代入としてまとめられることが分かります。

以上の考察により、これは遅延セグメント木のフレームワークに乗り、\(\mathrm O (N + Q \log N)\) の時間計算量で問題を解くことができます。