I hate Associative Property

$f(\cdots f(f(A_l, A_{l+1}), A_{l+2}), \cdots, A_r)$ を求めたいとします。

各要素が答えに寄与する分を考えると、$A_r$ は $\frac{1}{2}$ 倍、$A_{r-1}$ は $\frac{1}{4}$ 倍、$\ldots$ となります。

したがって各 $A_i$ に $\frac{1}{2^{n-i}}$ をかけておき、区間和取得したあとに適切に $2$ の累乗をかけることで求める答えを得ることができます。