noshi91のメモ

データ構造のある風景

3 次元空間のクエリを処理する Wavelet Matrix

概要

Wavelet Matrix は 2 次元空間の点群に関するクエリを処理するデータ構造と見ることが出来ます。 これを発展させて 3 次元空間の点群に関するクエリを  \Theta ( ( \log ( \sigma ) ) ^ 2 ) で処理するデータ構造が存在します。

出来ること

  •  \mathtt { new } ( A )
    •  A を非負整数の  2 つ組の列として、データ構造を構築する。
    • 時間計算量  \Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 )
    • 空間計算量  \Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 / w )
    •  \sigma は各成分の最大値
  •  \mathtt { count } ( l , r , d , u , s , t )
    •  A \lbrack l , r ) で第  0 成分が  \lbrack d , u ) かつ第  1 成分が  \lbrack s , t ) のものの個数を出力する。
    • 時間計算量  \Theta ( ( \log ( \sigma ) ) ^ 2 )
  •  \mathtt { quantile } ( l , r , d , u , k )
    •  A \lbrack l , r ) で第  0 成分が  \lbrack d , u ) のもののうち、第  1 成分が  k 番目に小さいものを出力する。
    • 時間計算量  \Theta ( ( \log ( \sigma ) ) ^ 2 )

アルゴリズム

通常の Wavelet Matrix における  \mathtt { quantile } ( l , r , k ) の処理は以下のような具合でした。

int ret = 0;
for (int p = matrix.size(); p-- != 0;) {
    bit_vector &vec = matrix[p];
    int zeros = vec.rank0(l, r); // この段の [l, r) における 0 の個数
    if (zeros <= k) { // 答えの p bit 目は 1
        ret |= 1 << p;
        k -= zeros;
        l = vec.rank0(0, n) + vec.rank1(0, l);
        r = vec.rank0(0, n) + vec.rank1(0, r);
    } else {
        l = vec.rank0(0, l);
        r = vec.rank0(0, r);
    }
}
return ret;

 1 成分についての Wavelet Matrix を構築して、 \mathtt { quantile } ( l , r , d , u , k ) のクエリを処理することを考えます。  \mathtt { quantile } ( l , r , k ) と異なるのは、zeros を計算する部分のみです。 この部分を、第  0 成分が  \lbrack d , u ) の要素に限定して数えることが出来れば、全く同様の処理を行うことが出来ます。 格段について、bitvector が 0 の成分だけ抜き出して第  0 成分についての Wavelet Matrix を構築すれば、求める値を計算することが可能です。

 \mathtt { count } ( l , r , d , u , s , t ) もほとんど同様です: 第  1 成分について通常の処理をしながら、答えに加算する時だけ第  0 成分を考慮した値を足し上げます。

実装例

Submission #23120967 - AtCoder Beginner Contest 203(Sponsored by Panasonic)

ABC203 D - Pond に提出して TLE したものです。