概要
固定長二進パトリシアツリー
目標
- 初期化：長さ 2^64 の理想配列 a, 全ての要素は値型の最大値で初期化される
- 更新 (key, value) : a[key] を value に書き換える
- 質問 (left, right) ：min(a[left], ..., a[right]) を出力する
keyが符号なし64bitであるような、大きなセグツリーを作る
トライで実装するとその頂点数は更新の回数と高さの積になってしまう。パトリシアツリーならば頂点数は更新の回数の2倍で抑えられる。
そのような長さが64固定の二進パトリシアツリーを作り、分枝ノードには min を乗せる。
実装
頂点
struct Node { Node *left; Node *right; u64 key; // minimum key; Seg seg; };
left, right はそれぞれ子ノードへのポインタ、key は部分木の中の最小のkeyを持つ。seg は部分木のvalue の最小値を持つ。
葉
left と right が共にNULLのとき、そのときに限り node は葉である。更新ではkeyが葉のkeyと比べて大きい・小さい・等しいの3通りで場合分けする。
分枝
部分木に含まれる key の最小値 left_key と、右の部分木の right_key について、異なる最大のビットを branch_bit と定義する。これはXORの最大set bitであり、floor(log2(left_key ^ right_key)) で求められるが、GCCでは次のように書ける。
int branch_bit = 63 - __builtin_clzll(left_key ^ right_key); // C++ のバージョンが新しいなら 63 - std::countl_zero(left_key ^ right_key) でも良い
分枝ノードは、次の条件を満たすような構造にする「左の部分木に含まれる key は branch_bit が 0」「右の部分木に含まれる key は branch_bit が 1」。
この条件を常に満たすように insert 関数を実装する。新しい key と left_key と right_key を branch_bit で切り落とすと4通りの場合分けをすれば良い。
unsigned b = 63 - __builtin_clzll(node->key ^ node->right->key); new_branch = key >> b; left_branch = node->key >> b; right_branch = node->right->key >> b; if (new_branch < left_branch) { node = new Node(nullptr, node); insert_rec(node->left, key, seg); } else if (new_branch == left_branch) { insert_rec(node->left, key, seg); } else if (new_branch == right_branch) { insert_rec(node->right, key, seg); } else { node = new Node(node, nullptr); insert_rec(node->right, key, seg); } node->key = node->left->key; node->seg = node->left->seg + node->right->seg;
特徴
最大値を見積らなくてもトライと同等以下の高さになる。最悪ケースで簡単に高さ64になるが、これはトライも同じなので許容できるものとする。平衡二分木と比べると回転がないので実装は簡単になる可能性がある。
ビット演算 clz を要求しているのが小さな欠点。
コード
提出結果 judge.yosupo.jp
クラス全体
struct Seg { LL value; Seg(): value(0x3FFFFFFFFFFFFFFFLL) {} Seg(LL x): value(x) {} Seg operator+(const Seg &o) const { return Seg(min(value, o.value)); } static const Seg IDENTITY; }; const Seg Seg::IDENTITY = Seg(); template<class Seg> struct BinaryPatriciaTree { using u64 = unsigned long long; BinaryPatriciaTree() {} ~BinaryPatriciaTree() { destructor(root); } Seg get(u64 key) const { if (!root) { return Seg::IDENTITY; } Node *node = root; while (!node->is_leaf()) { node = (key < node->right->key? node->left: node->right); } return node->key == key? node->seg: Seg::IDENTITY; } void insert(u64 key, const Seg &seg) { insert_rec(root, key, seg); } Seg sum(u64 left_key, u64 right_key_exclusive) const { if (right_key_exclusive <= left_key) { return Seg::IDENTITY; } return sum_rec(root, ~u64(0), left_key, right_key_exclusive - 1); } Seg sum_inclusive(u64 left_key, u64 right_key_inclusive) const { if (right_key_inclusive < left_key) { return Seg::IDENTITY; } return sum_rec(root, ~u64(0), left_key, right_key_inclusive); } private: struct Node { Node *left = nullptr, *right = nullptr; u64 key; // minimum key; Seg seg; Node() {} Node(Node *left_, Node *right_): left(left_), right(right_) {} Node(u64 key_, const Seg &seg_): key(key_), seg(seg_) {} bool is_leaf() const { // assert(bool(left) == bool(right)); return !left; } }; Node *root = nullptr; static void destructor(Node *node) { if (node) { destructor(node->left); destructor(node->right); delete node; } } static void insert_rec(Node *&node, u64 key, const Seg &seg) { if (!node) { node = new Node(key, seg); } else if (node->is_leaf() && node->key == key) { node->seg = seg; } else { u64 new_branch, left_branch, right_branch; if (node->is_leaf()) { new_branch = key; left_branch = right_branch = node->key; } else { unsigned b = 63 - __builtin_clzll(node->key ^ node->right->key); new_branch = key >> b; left_branch = node->key >> b; right_branch = node->right->key >> b; } if (new_branch < left_branch) { node = new Node(nullptr, node); insert_rec(node->left, key, seg); } else if (new_branch == left_branch) { insert_rec(node->left, key, seg); } else if (new_branch == right_branch) { insert_rec(node->right, key, seg); } else { node = new Node(node, nullptr); insert_rec(node->right, key, seg); } node->key = node->left->key; node->seg = node->left->seg + node->right->seg; } } static Seg sum_rec(const Node *node, u64 node_bound, u64 left_key, u64 right_key_inclusive) { if (!node || right_key_inclusive < node->key || node_bound < left_key) { return Seg::IDENTITY; } else if (left_key <= node->key && node_bound <= right_key_inclusive) { return node->seg; } else if (node->is_leaf()) { return left_key <= node->key && node->key <= right_key_inclusive? node->seg: Seg::IDENTITY; } else { return sum_rec(node->left, node->right->key - 1, left_key, right_key_inclusive) + sum_rec(node->right, node_bound, left_key, right_key_inclusive); } } };
