たとえば、関数の値またはインデックス i の f (i) は i ^ k であると言われ、k> = 0 の場合、常にこの問題にとどまります。次のようなクエリを指定します。
すべての a <= i <= b に対して、値配列 [i] を v として追加します。 a <= i <= b ごとに、合計配列 [i] f (i) を決定します (前の関数値の説明を思い出してください)。
To work on this matter, can be formed into Query (x) = m * g (x) - c,
where g (x) is f (1) + f (2) + ... + f (x).
これを達成するには、m と c の値を知る必要があります。そのためには、2 つの個別の BIT が必要です。ab v の形式での各更新に関する以下の観察。m の値を計算するには、Range Update - Point Query と実質的に同じです。i の各値について、次の観測結果を得ることができます。
i <a, m = 0
a <= i <= b, m = v
b <i, m = 0
次の観察を使用することにより、Range Update - Point Query を任意の BIT で使用できることは明らかです。c の値を計算するには、i の各値の可能性を観察する必要があります。
i <a, then c = 0
a <= i <= b, then c = v * g (a - 1)
b <i, c = v * (g (b) - g (a - 1))
ここでも、Range Update - Point Query が必要ですが、BIT が異なります。大谷、ちょっとした助けとして、k <= 3 の場合の g (x) の値を書きました はい: p:
k = 0 -> x
k = 1 -> x * (x + 1) / 2
k = 2 -> x * (x + 1) * (2x + 1) / 6
k = 3 -> (x * (x + 1) / 2) ^ 2
さて、問題の例 SPOJ - Horrible Queries 。この問題は、k = 0 で説明した問題と似ています。また、関数が 1 つのタイプの k ではなく、その多項式の形状である可能性があるという、非常に極端な問題があることにも注意してください。例：LA - エイリアン・アブダクション・アゲイン。この問題を解決するには、ランクごとに BIT カウンターをそれぞれ m にします。BIT を組み合わせてカウンターをクリアしました c 問題ありませんでした。
次の場合、この概念をどのように使用できますか。
整数の配列 A1、A2、…AN が与えられます。
与えられた x,y: Ax に 1×2 を足し、Ax+1 に 2×3 を足し、Ax+2 に 3×4 を足し、Ax+3 に 4×5 を足し、というように Ay まで続けます。
次に、範囲 [Ax,Ay] の合計を返します。