字典树Trie 最后更新于 2025-05-01 18:42:41

```cpp struct node { int nxt[2];//nxt[0] nxt[1] 代表从当前点走0和1会走到哪里 走到0的话代表这个节点不存在 node() { nxt[0] = nxt[1] = 0; } }z[23333]; void insert(int x) { int p=root; for (int i=30;i>=0;i--) { int y=(x>>i)&1;//取出x二进制的第i位 if (z[p].nxt[y] == 0) {; cnt++; z[p].nxt[y] = cnt; } p = z[p].nxt[y]; } } int query(int x)//从trie中找一个数 使得他和x异或之后最大 { int p=root,ans=0; for (int i=30;i>=0;i--) { int y=(x>>i)&1; if (z[p].nxt[y^1] != 0) ans=ans|(1<<i),p=z[p].nxt[y^1]; else p=z[p].nxt[y]; } return ans; } int main() { root = 1; } ```