サイズ N の配列と、同じくサイズ N の間隔の配列があり、それぞれが最初の配列の連続するセグメントである場合、配列の要素を更新し、セグメントの合計を求める Q クエリを処理する必要があります。 2 番目の配列 (iTH 間隔から jTH 間隔までの要素の合計)。
これで、最初のクエリを簡単に処理できます。配列からセグメント ツリーを構築できます。これを使用して、最初の配列 (2 番目の配列の要素) の間隔の合計を計算できます。しかし、O(log n) で 2 番目のクエリを処理するにはどうすればよいですか? 最悪の場合、更新する要素は 2 番目の配列のすべての間隔に含まれます。
O(Q log N) または O(Q (logN)^2) ソリューションが必要です。
これがO((Q + N) * sqrt(Q))解決策です (sqrt-decomposition の非常に標準的な考え方に基づいています):
1. 配列が更新されないと仮定しましょう。次に、問題は非常に簡単になります。プレフィックスサムを使用するとO(N)、事前計算とO(1)クエリごとにこの問題を解決することができます (ここでは、2 つのプレフィックスサム配列が必要です。1 つは元の配列用で、もう 1 つは間隔の配列用です)。
2. 次に、クエリを size のブロックに分割しましょうsqrt(Q)。各ブロックの開始時に、1. と同じことを行うことができます。このブロックの開始前に発生した更新のみを考慮に入れます。線形時間で実行できます (プレフィックスの合計を 2 回使用)。そのような計算の総数はQ / sqrt(Q) = sqrt(Q)回（これは私たちが持っているブロックの数であるため）。これまでのところ、O((N + Q) * sqrt(Q))合計で時間がかかります。
3. タイプ 2 のクエリを取得すると、現在のブロックの外側にあるすべての更新が既に考慮されています。sqrt(Q)したがって、答えに影響を与える可能性のある更新はせいぜいあります。このクエリの前に発生した現在のブロック内のすべての更新を繰り返し処理し、回答を更新します。iこれを行うには、配列内の特定の位置が からまでの間隔で何回存在するかを知る必要がありますj。この部分は、時間と空間を使用したスイープ ライン アルゴリズムでオフラインで解決できますO(Q * sqrt(N + Q))(基数ソートが使用できるため、追加の対数係数は表示されません)。
したがってO((N + Q) * sqrt(Q))、合計で最悪の場合の時間と空間が得られます。もちろん、より悪いですが、クエリと配列要素O(Q * log N)についてはうまくいくはずです。10^5