3

私はこの種の問題に直面したことがあります。約100 万Aのn要素の配列が与えられたとします。形式のクエリが与えられます。各クエリでは、要素に対して何らかの操作を実行する必要があります。n1'p q'A[p]A[q]

  • この操作はXOR、何かのような通常の操作です。A のすべての数値 (インデックス p から q まで) と指定された数値 m の XOR を計算します。例のために-A[p]^m,A[p+1]^m..A[q]^m

タイプ 'p q' の何千ものクエリが与えられた場合、重複する範囲 (例: - ) に対して繰り返し計算を行いますp1<p2<q1<q2。スペースと時間のトレードオフがある場合、より多くのスペースが必要になる場合でも、作業をより速く行うことを好みます。ですから、私は空間ではなく時間に集中しています。

私の質問は-これらのタイプのクエリを効率的に処理できるデータ構造はありますか（さらにクエリで繰り返される範囲があります）。私が考えることができるのは、前処理を行い、データ構造に保存するようなものです。そして、さらにクエリを受け取ると、更新と処理が行われます。

一部の範囲に関係するクエリの処理に役立つデータ構造を誰かが提案できますか (特に、範囲がさらに広範囲に繰り返される場合)。

4

2 に答える 2

1

私が最初に考えたのは、遅延伝播を伴うセグメント ツリーでしたが、説明したクエリが実際にテーブルの更新であり、結果を返さない場合にのみ実際に適用されます。したがって、update[pq] 操作と query[pq] があります。最初は説明したような操作を使用して更新するだけで、2番目は範囲から値を返します。

これも参照してください。

于 2012-10-07T13:58:35.827 に答える
0

0 から log(n) の範囲の各 k に対して、長さ n/2**k の配列 A[k] を格納します。

A[k][i] の内容は、インデックス i*2**k から (i+1) 2 *k-1 までの配列の要素を表します。

範囲を操作する場合は、範囲を可能な限り大きなチャンクに分割し、A[k] の対応するエントリを更新します。

たとえば、範囲が 16->33 の場合、A[4][1] (16->31 を表す) と A[1][16] (32->33 を表す) だけを更新します。

要素の結合された値にアクセスする場合は、各 log(n) 配列の操作を結合する必要があります。

たとえば、5 にアクセスするには、A[0][5] と A[1][2] と A[2][1] と A[3][0] などの操作を組み合わせる必要があります。

これにより、範囲の操作ごと、および要素のアクセスごとに O(log(n)) コストがかかるはずです。

于 2012-10-06T21:04:28.360 に答える