遅延伝播による配列の特定のセグメントへの定数の追加または AP の追加を含むセグメント ツリーで範囲更新を行う方法と、特定のセグメントの合計についての後続のクエリを作成する方法を知っていますが、幾何級数。
同じ漸近時間複雑度でセグメントツリーを使用することで、これをどのように達成できます(log(N))か?
たとえば、配列が :
a[1], a[2], .... , a[l],a[l+1]...a[r-1], a[r] ... a[n - 1], a[n]
で、[l, r] を公比 d で更新すると、更新された配列は次のようになります。
a[1], a[2], .... , a[l] + d, a[l+1] + d^2 ...a[r-1] + d^(l-r), a[r] + d^(l-r+1) ... a[n - 1], a[n]
また、log(n) の任意のセグメントの合計についてもクエリを実行できるはずです。