c++ - バイナリ配列に対するクエリへの回答

Question

長さ<=10^5のバイナリ配列と、クエリの数がほぼ等しい場合。各クエリは、範囲[l,r]内の連続する0と1の総数を計算する必要があるクエリごとに2 つの整数(l,r)で指定されます。

nが配列の長さの場合、 1 <= l < r <= nです。

例えば：

バイナリ配列 ( 1 -indexed) が " 011000 " で、5 つのクエリがあるとします。

1 3
5 6
1 5
3 6
3 4

次に、必要な答えは

1
1
2
2
0

これは、クエリごとに線形時間 (最悪の場合) アルゴリズムで解決できることは承知していますが、クエリの数が多いため、実行できません。

これを達成するための最も効率的な方法はどれですか？

Answer 1

各クエリの O(n) スペースの複雑さと O(log(n)) 検索時間でそれを行うことができます。サイズ 1、2、4、... のウィンドウのカウントを計算します。特定のクエリに対して、O(log(n)) ウィンドウ (特定のサイズの最大 2 つのウィンドウ) を見つけることができ、合計すると答えを見つけることができます。 .