4

整数の配列とその配列の範囲 (間隔) のリストが与えられ、各間隔の個別の要素の数を返すアルゴリズムを実装しようとしています。つまり、配列 A と範囲 [i,j] を指定すると、集合 {A[i],A[i+1],...,A[j]} のサイズが返されます。

明らかに、単純なアプローチ (i から j まで反復し、重複を無視してカウントする) は遅すぎます。AUB - B が常に B と等しいとは限らないため、Range-Sum は適用できないようです。

ウィキペディアで Range Queries を調べたところ、Yao ('82 年) が線形の前処理時間と空間、およびほぼ一定のクエリ時間で半群演算子 (和集合のようです) に対してこれを行うアルゴリズムを示したことを示唆しています。残念ながら、記事は無料で入手できません。

編集：この正確な問題はhttp://www.spoj.com/problems/DQUERY/で入手できるようです

4

3 に答える 3

3

前処理に O(N log N) 時間と空間を使用し、クエリごとに O(log N) 時間を使用するかなり単純なアルゴリズムがあります。最初に、範囲合計クエリに応答するための永続セグメント ツリーを作成します (最初は、すべての位置にゼロが含まれている必要があります)。次に、指定された配列のすべての要素を反復処理し、各数値の最新の位置を保存します。各反復で、各要素の最新の位置に 1 を配置して、永続セグメント ツリーの新しいバージョンを作成します (各反復で 1 つの要素の位置のみを更新できるため、セグメント ツリー内の 1 つの位置の値のみが変更されるため、更新はO(log N))。クエリ (l, r) に答えるには、最初の配列の r の要素を反復処理するときに作成されたツリーのバージョンの (l, r) セグメントの合計を見つけるだけです。このアルゴリズムが十分に高速であることを願っています。更新。私の説明には少し誤りがあります: 各ステップで、セグメント ツリー内の最大 2 つの位置の値が変更される可能性があります (数値が更新された場合、数値の前の最新の位置に 0 を配置する必要があるため)。ただし、複雑さは変わりません。

于 2013-02-04T16:33:55.493 に答える
0

二次時間の事前計算を実行することで、任意のクエリに一定時間で答えることができます。

For every i from 0 to n-1
    S <- new empty set backed by hashtable;
    C <- 0;
    For every j from i to n-1
        If A[j] does not belong to S, increment C and add A[j] to S.
        Stock C as the answer for the query associated to interval i..j.

このアルゴリズムは、間隔ごとに制限された数の操作を実行し、それぞれに一定の時間がかかり (セット S はハッシュテーブルによってサポートされていることに注意してください)、2 次数の間隔があるため、2 次時間がかかります。

クエリに関する追加情報 (クエリの総数、間隔の分布) がない場合は、間隔の総数が既に 2 次であるため、本質的により適切に行うことはできません。

nオンザフライの線形計算によって二次事前計算をトレードオフすることができます。形式 A[i..j] のクエリを受け取った後O(n)、すべての間隔A[i..k],の答えを (時間内に) 事前計算しますk>=i。これにより、償却された複雑さが 2 次のままであることが保証され、最初に完全な 2 次事前計算を実行する必要がなくなります。

すべての間隔を完全にスキャンするため、明白なアルゴリズム (ステートメントで自明と呼ぶもの) は 3 次であることに注意してください。

于 2013-02-04T17:13:22.690 に答える
0

これは、セグメント ツリーに非常に密接に関連している別のアプローチです。配列の要素は、完全な二分木の葉と考えてください。配列に 2^n 個の要素がある場合、その完全なツリーの n レベルがあります。ツリーの各内部ノードには、その下にある葉にあるポイントの和集合が格納されます。配列内の各数値は、各レベルで 1 回出現する必要があります (重複がある場合は少なくなります)。したがって、スペースのコストは log n 倍になります。

長さ K の範囲 A..B を考えてみましょう。葉とノードに関連付けられたセットの和集合を形成し、下のサブツリーが続く限り、ツリーのできるだけ上のノードを選択することによって、この範囲内のポイントの和集合を計算できます。これらのノードは完全に範囲に含まれます。可能な限り大きなサブツリーを選択する範囲に沿って進むと、サブツリーのサイズが最初に増加し、次に減少し、必要なサブツリーの数が範囲のサイズの対数でのみ増加することがわかります-最初はサイズ 2^k のサブツリーしか取得できない場合、2^(k+1) で割り切れる境界で終了し、次のサイズが少なくとも 2^(k+1) のサブツリーの可能性があります。範囲が十分に大きい場合はステップします。

したがって、クエリに答えるために必要な半群操作の数は O(log n) です。ただし、2 つの大きな集合の和集合を形成する可能性があるため、半群操作は高価になる可能性があることに注意してください。

于 2013-02-04T21:20:05.787 に答える