セグメントツリーで範囲更新を適用する方法は？

Question

私はすでにパーシスタンスセグメントツリーを作っていますが、現在はあるインデックスからあるインデックスへの範囲の更新があります。永続性セグメントツリーを複雑さを少なくして更新するには？ 私はちょうど

Answer 1

永続セグメントツリーを再構築しかし、今、元の配列要素は、配列の要素を今すぐ同じクエリが再び3 6 2 4 5頼まれている今、1から3に更新されていることを言うことができますしています。ですから、パーシスタンスセグメントツリー全体を再構築する必要があります。

範囲の更新では、範囲内の各要素を非数式で変更することを意味する場合、最適なオプションは、指定された範囲内の各要素に単一要素の更新を適用することです。これはO(range_sz * log n)になります。nはツリー内の要素の数です。

O(log n)で単一要素の更新を実行する方法を知っていることを前提としています。

"範囲内のすべての要素を指定した値v"にするなど、更新が制限されている場合、関連する範囲が更新に含まれているセグメントツリーのすべてのノードに対して遅延更新を使用できます一部のカスタムフィールドを値vに設定します。次に、照会するときに、ノードの範囲（照会範囲にその範囲が含まれている場合）を受け入れるたびにこのフィールドをチェックし、値がある場合はその値をmin/maxまたは照会しているものにします。

これにより、更新とクエリの両方がO(log n)に保持されます。