n 個の空の箱が一列に並んでいるとしましょう。コインのm 個のグループを、事前にわかっているいくつかの連続したボックスに入れます。コインの最初のグループをi_1からj_1までのボックスに入れ、2 番目のグループをi_2からj_2までのボックスに入れます。
すべてのコインをボックスに入れた後、ボックスiのコインの数をc_iとする。インデックス i = s, s + 1, ... e - 1, eのボックスにいくつのコインがあるかをすばやく判断できるようにしたい、つまり、合計を計算したい
c_s +c_(s+1) + ... + c_e
効率的。これはFenwick treeを使用して行うことができます。改善がなければ、Fenwick ツリーはc_iを格納するためのO(n)スペース(実際には、tree[i] != c_i、値はよりスマートに格納されます) と、上限の合計を計算するための O(log n) 時間を必要とします。
場合があれば
- nは、長さnのテーブルを作成するには大きすぎます(たとえば、〜 10 000 000 000 としましょう)
- mは十分に小さい (たとえば ~ 500 000 としましょう)
ボックスの座標 (インデックス) を何らかの形で圧縮する方法があります。つまり、インデックスi_1、i_2、... 、i_mを持つボックスだけを格納するだけで十分です。tree[i]に格納される値はiのバイナリ表現に依存するため、インデックスi_1、j_1、i_2、j_2、 ... 、i_m、j_mをソートし、長さO(m)のツリーを作成します。ツリーに新しい値を追加するのは簡単です。また、その合計を計算するには、 eより大きくない最初のインデックスを見つけるだけです。sよりも小さくない最後のもの。どちらもバイナリ検索で実行できます。その後、合計は簡単に計算できます。
問題は 2D の場合に発生します。ここで、平面内に点(x,y)の領域0 < x,y < n があります。その領域にはm 個の長方形があります。それらの左下隅と右上隅の座標がわかっているので、点(a,b) を含む四角形の数を計算したいと考えています。最も単純な (そして私の唯一の) アイデアは、1D の場合の方法に従うことです。コーナーの座標x_iごとに、コーナーのすべての座標y_iを格納します。O(m^2) =あまりにも多くのスペースが必要なので、このアイデアはあまり賢くありません。私の質問は
How to store coordinates in the tree in a more efficient way?
フェンウィック ツリーを使用した問題の解決策が推奨されますが、すべての解決策を歓迎します。