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

概要

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

出来ること

- $A$ を非負整数の $2$ つ組の列として、データ構造を構築する。
- 時間計算量 $\Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 )$
- 空間計算量 $\Theta ( \lvert A \rvert ( \log ( \sigma ) ) ^ 2 / w )$
- $\sigma$ は各成分の最大値
- $A \lbrack l , r )$ で第 $0$ 成分が $\lbrack d , u )$ かつ第 $1$ 成分が $\lbrack s , t )$ のものの個数を出力する。
- 時間計算量 $\Theta ( ( \log ( \sigma ) ) ^ 2 )$
- $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$ 成分を考慮した値を足し上げます。