01字典樹在異或問題的查詢上十分高效。

01字典樹是按位插入和查詢的。因為如果一個數，它的高位值較大，那么這個數的值較大。所以我們插入和查詢時是從最高位開始進行的。

可以開一個輔助數組val來記錄原數值。

插入：

#define ll long long int n,m; int trie[32*MAXN][2]; ll val[32*MAXN]; int tot; void insert(ll d) {int root=0;for(int i=32;i>=0;i--){int id=(d>>i)&1;//獲得這一個bit位的值if(!trie[root][id]) trie[root][id]=++tot;root=trie[root][id];}val[root]=d; }

查詢：

ll query(ll d) {int root=0;for(int i=32;i>=0;i--){int id=(d>>i)&1;if(trie[root][id^1]) root=trie[root][id^1];else root=trie[root][id];}return val[root]; }

?

總結

以上是生活随笔為你收集整理的01字典树模板~的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。