IsOn（i）とToggle（i、j）に答える理想的なデータ構造 - HashSetよりも優れている必要があります

Question

これは最近インタビューで尋ねられた質問です。私はまともな解決策を思いついたが、私のインタビュアーによって良いことが言われた。

n個の電球があることを想像してみてください。最初はすべてがオフになっています。理想的な時間のANS空間複雑に2つのクエリに答えるためのアプローチを設計します。

（1）ISON（I） - 変更 - 要素は 'i' は

（2）トグル（i、j）の上にある場合はtrueを返します範囲[i、j]（包括的）内のすべての要素の状態。

1. 初期解決策：配列。 O（1）のIsOn、O（j-i）のトグル、O（N）の空間複雑さ。
2. 解決策：オンになっているすべての要素を保持するハッシュセット。 IsOnはまだO（1）ですが、ToggleはまだO（j - i）ですが、空間の複雑さははるかに優れています。

私は、私はよりよい解決策、上にある要素の範囲を保存するに関係しているものを見つける必要があることを言われた - しかし、私はそれを理解するために苦労しています。

Answer 1

これは、レイジー伝播を伴うセグメントツリーによって行うことができます。このアルゴリズムは、Jの範囲Iの値を切り替えることになる最初の配列は0

更新（i、j）を用いて充填される従う

1. ようになるであろう。これは
2. クエリ（l）は、ツリーを構築するための指標[L、L]

時間の複雑性O（nlogn）で私たちの価値を言うだろう怠惰な伝播を使用してO（nlogn）で行うことができ、かつクエリと更新のためのO（logn）