4

次の問題があります: 整数配列 (最大サイズ 50000) が与えられた場合、次のような最大 X を見つける必要があります。

X = a[p] ^ a[p+1] ^ ... ... ^ a[q] for some p,q (p<=q)

また、Xの最小値を見つける必要があります。

私はこのプロセスを試しました、

sum[i] = a[0] ^ a[1] ^ ... ... ^ a[i] for some i .

O（n）で事前に計算し、

次に、一部の X の値p,q(p<=q)は、

X = sum[q] ^ sum[p-1]

MaxAns = Max of X for every pair of p,q (p<=q)

MinAns = Min of X for every pair of p,q (p<=q)

しかし、このプロセスは O(n^2) です。

O(n^2) アルゴリズムなしで、より効率的な方法でそれを行うにはどうすればよいですか?

4

3 に答える 3

4

このアルゴリズムは、ビット幅が制限された符号なし整数に対してのみ機能します。

  1. 各配列要素のプレフィックスの合計を計算します(これは OP で行われるのとまったく同じです)。
  2. 各プレフィックスの合計を基数ツリーに追加します(ルートに対応する最上位ビット、リーフに対応する最下位ビット)。
  3. それを計算sum[q]して基数ツリーに追加する間に、部分的に構築された基数ツリーを検索 sum[q]します (X の最小値を取得するため)。X の最大値については、 を検索して~sum[q]ください。
  4. sum[q](または)のビットが~sum[q]ツリーから欠落している場合は、X の最小/最大値でこのビットを切り替えて、ツリーを下方向に検索し続けます。
  5. 各プレフィックスで見つかったすべての最小値/最大値の最小値/最大値を取得します。

時間計算量は O(N log M) です。ここで、M は配列の要素の最大値です。

于 2012-12-28T08:07:01.597 に答える
1

これは明らかに間違っています。理由はわかりませんが、少しテストしたところ、間違っていることがわかりました。

問題が基本的にある「プログラミングパール」の列8からインスピレーションを得ることができると思います：「実ベクトルx [n]が与えられた場合、隣接するサブベクトルで見つかった最大合計を計算します」。

加算と減算を排他的論理和に置き換えて、さまざまなアルゴリズムを再利用できると思います (ほとんどの興味深いプロパティはプロセス中に保持されます: 0 は依然として中立的な要素であり、排他的論理和は独自の逆、可換性です)。

スライドはhttp://cs.bell-labs.com/cm/cs/pearls/s08.pdfにありますが、この本を強くお勧めします。

于 2012-12-28T03:49:53.513 に答える