数列a,数b,l,rに対し,区間[l,r)でのmin{a[i] xor b}(max{a[i] xor b})を高速に求める

こんにちは。heno239です。

タイトル通りですが、

• 数列aが与えられたとき、クエリ「数b,l,rに対し、区間l<=i<rにおけるa[i]^bの最小値(最大値)を返す」を割と高速にこなすtri木

について書きます。ある問題を解いていた時に必要に駆られて書いたので、ついでにあげとくか、みたいなノリです。

• 計算量

数列aの最大値をAとし、数列の長さをNとします。

初期化でO(NlogA),クエリ毎の計算量はO(logNlogA)です。(クエリ数が2*10^5,N=2*10^5,A=2^30ぐらいなら2秒以内に通ると思います)

適当に書いたので、定数倍が結構重そうです。

• 説明

ソースコードを見ればわかります(過激な主張)

• ソースコード

• 使い道

ごくたまに出てきそう

• いま食べたい寿司のネタ

穴子