f(⋯f(f(Al,Al+1),Al+2),⋯ ,Ar)f(\cdots f(f(A_l, A_{l+1}), A_{l+2}), \cdots, A_r)f(⋯f(f(Al,Al+1),Al+2),⋯,Ar) を求めたいとします。
各要素が答えに寄与する分を考えると、ArA_rAr は 12\frac{1}{2}21 倍、Ar−1A_{r-1}Ar−1 は 14\frac{1}{4}41 倍、…\ldots… となります。
したがって各 AiA_iAi に 12n−i\frac{1}{2^{n-i}}2n−i1 をかけておき、区間和取得したあとに適切に 222 の累乗をかけることで求める答えを得ることができます。