o（logn）のrbtreeでアルゴリズムを見つける

Question

次のアクションでできるデータ構造を見つける必要があります。

• ビルド（s、k）-o（nlogn）
• 検索（s、k）-o（logn）
• insert（s、k）-o（logn）
• delete（s、k）-o（logn）
• Decrawes -upto（s、k、d）-o（logn） - この方法は、<= kです。

明らかな最初の選択はredblacktreeでした。

ただし、O（logn）のDecrase-uptoに関する解決策には至ることはできません。 kがツリーの最大キーよりも大きい場合はどうなりますか？その場合、ツリー全体を更新する必要があります。

誰かがそうでなければ提案できますか？多分いくつかのヒント？

Answer 1

ツリーの各ノードに追加の値を保存できます。デルタと呼びましょう。すべての子孫に保存されたキーにノードのデルタを追加して、実際のキーを取得します。したがって、特定のノードでキーの実際の値を取得するには、すべてのデルタをルートからそのノードに合計し、この合計を保存されたキーに追加します。

やる Decrease-Upto, 、ルートから1つのパスでO（log n）ノードのデルタを変更するだけです。

この操作後にツリーの構造を変更する必要はありません。キーの順序付けが変更されないためです。