🚀 Quality Resource Sharing 🚀

Learning Route Guidance (click to unlock)	Knowledge Positioning	Population positioning
🧡 Python Actual Wechat Subscription Applet 🧡	Advanced Class	This course is the perfect combination of python flask + WeChat applet, from project building to Tencent cloud deployment online, creating a full stack ordering system.
💛 Python Quantify Trade Actual 💛	beginner	Hand-held to create a scalable, safer and more efficient quantitative trading system

1|001Trie

1|1Section 1: Common Trie

1|0Section 1.1 What is Trie

The Trie tree, or dictionary tree, is a tree structure. Typical applications are to use a large number of string prefixes for statistics and sorting to reduce query time and minimize unwanted string comparisons.

How 1|0Section 1.2 is implemented

Specifically, for each node, there are several pieces of information that we need to store:

• ch[26], save the storage address of the next character of this character (a_z a_z a\sim z) (not 000).
• cnt, how many times has this node been saved.

For the entire Trie tree, we need to save extra

• Tcnt, the number of nodes.
• Endp[], which indicates whether the string ends with this subscript (this array is not needed if it is just a prefix).

1|0 Operations

1. insert: insert a string into the Trie tree.

Specific implementation: Scan the characters in the string once, set the current character a s s s s, if ch[s-'a'] is not equal to 000, jump to the storage subscript of ch[s-'a']. Otherwise, set ch[s-'a'] to one plus the number of nodes in the tree and jump. Add one cntcnt to the current node when jumping.

Jump to the end and set the current node EndpEndp to one.

1. find: Query Trie for this string.

Specific implementation: one jump per character.

If cnt=0cnt=0cnt=0 when jumping, it means No.
If you skip to the end, yes, but EndpnowNode=0EndpnowNode=0Endp_{nowNode}=0 does not end with this character, indicating No.
Otherwise, this string returns true.

1|0Section 1.3 Code Implementation

(Only basic inserts and queries are given)

Click to view the code

#include 
using namespace std;

const int N=3000005;

struct Trie{
 int T[N][63],Tsiz,Endp[N];
 void init(){
 for(int i=0;i<=Tsiz;i++) for(int j=0;j<=62;j++) T[i][j]=0;
 for(int i=1;i<=Tsiz;i++) Endp[i]=0;
 Tsiz=0;
 }
 int gethash(char ch){
 if(islower(ch)) return ch-'a';
 if(isupper(ch)) return ch-'A'+26;
 if(isdigit(ch)) return ch-'0'+26+26;
 }
 void insert(string s){
 int rt=0,len=s.length();
 for(int i=0;i int x=gethash(s[i]);
 if(!T[rt][x]) T[rt][x]=++Tsiz;
 rt=T[rt][x];
 }
 Endp[rt]++;
 }
 int find(string s){
 int rt=0,len=s.length();
 for(int i=0;i int x=gethash(s[i]);
 if(!T[rt][x]) return 0;
 rt=T[rt][x];
 }
 return Endp[rt];
 }
}trie;

int T,n,q;

int main(){
 trie.init();
 cin>>n>>q;
 string s;
 for(int i=1;i<=n;i++){
 cin>>s;
 trie.insert(s);
 }
 for(int i=1;i<=q;i++){
 cin>>s;
 cout<'\n';
 }
}
Fold 

1|0Section 1.4 Template

[Lo Gu Template Title Link]

(Can't pass this topic with the above code, please write cntcnt maintenance prefix)

1|2Section 2: 01Trie

1|0Section 2.1 What is 01Trie?

Similar to a normal Trie, but each node has only two values: 0/10/10/1.

A path from the root node down holds a binary bit of positive integer from high to low.

As follows:

The result of median traversal is (ignoring root node): 00 01 10 1100 01 10 1100\0110\11

We'll find some interesting properties:

• 01Trie is a binary tree with a left son of 000 and a right son of 111 for each node.
• From the root node down, the path value from all left sons is less than that from right sons.

Using these two properties, we can build a balance tree with 01Trie.

1|0Section 2.2 Balanced Tree

For each node, we maintain two pieces of information:

• siz, which maintains the subtree size with the current node as the root node.
• cnt, maintains the number of digits from the current node to the last digit in binary.

In addition, like regular Trie s, we maintain the tree size ppp.

1|0 Operations

1. insert: Balances the insertion of a tree. First, add one sizsizsiz to each passing node to indicate that there is one more node in the subtree. If the current binary digit of the current number is 000, put it in the left son, otherwise put it in the right son. Add 111 to the cntcntnt of the current node when inserted in the last bit.
2. delete: Balanced tree deletion is almost the same as insert except for the last cnt_1cnt_1cnt-1.
3. get_rank: Query the rank of the current number. Starting from the root node, if the current binary bit of the current number is 111, the rank is added to the value of its left subtree (property two).
4. get_kth: Number of queries ranked kkk. From the root node down, if the left subtree sizsizsiz is TMP TMP tmp, if K < TMP K < TMP K \le tmp, then the node ranked k k k is on its left subtree. Otherwise, look to the right subtree and set the current binary bit of the answer to 111.
5. pre: The precursor to the current number. Return get_kth(get_rank(x)) will do.
6. nxt: Find the succession of the current number. Return get_kth(get_rank(x+1)+1) will do.

1|0Section 2.3 Code Implementation

Click to view the code

#include 
using namespace std;

const int MAXLOG=24;
const int N=1e7;

class \_01trie{
private:
 struct node{
 int ch[2];
 int siz,cnt;
 }T[1< int p;
public:
 void update(int x,int offset){
 int now=0;
 for(int i=MAXLOG-1;i>=0;i--){
 bool now\_bit=(x&(1< if(T[now].ch[now\_bit]==0) 
 T[now].ch[now\_bit]=++p;
 now=T[now].ch[now\_bit];
 T[now].siz+=offset;
 }
 T[now].cnt+=offset;
 }
 int get\_rank(int x){
 int now=0,ans=0;
 for(int i=MAXLOG-1;i>=0;i--){
 bool now\_bit=(x&(1< if(now\_bit==1)
 ans+=T[T[now].ch[0]].siz;
 now=T[now].ch[now\_bit];
 if(now==0)
 break;
 }
 return ans;
 }
 int get\_kth(int k){
 int now=0,ans=0;
 for(int i=MAXLOG-1;i>=0;i--){
 int tmp=T[T[now].ch[0]].siz;
 if(k<=tmp)
 now=T[now].ch[0];
 else{
 k-=tmp;
 now=T[now].ch[1];
 ans|=(1< }
 if(now==0)
 break;
 }
 return ans;
 }
 int pre(int x){
 return get\_kth(get\_rank(x));
 }
 int nxt(int x){
 return get\_kth(get\_rank(x+1)+1);
 }
}Trie;

int n;
int opt,x;

int main(){
 scanf("%d",&n);
 for(int i=1;i<=n;i++){
 scanf("%d%d",&opt,&x);
 if(opt==1) Trie.update(x+N,1);
 if(opt==2) Trie.update(x+N,-1);
 if(opt==3) printf("%d\n",Trie.get\_rank(x+N)+1);
 if(opt==4) printf("%d\n",Trie.get\_kth(x)-N);
 if(opt==5) printf("%d\n",Trie.pre(x+N)-N);
 if(opt==6) printf("%d\n",Trie.nxt(x+N)-N);
 }
}

Fold 

1|0Section 2.4 Template

[Lo Gu Template Title Link]

1|3Section 3:01Trie Example

Longest XOR Path for Logu P4551

Description
Given the edge weight of a tree and a tree, the maximum value of the path XOR between two points is obtained.

Solution

Given a prior knowledge first: x_x=0x_x=0x \oplus x=0.

So the XOR value of the two-point path on the tree is equal to the XOR value of the path XOR value from the root node to the two points (root_LCA(x,y)root_LCA(x,y)root\to\operatorname{LCA}(x,y) segment of the root node.

So we can process the edge exclusive or values from the root node to all nodes once by dfs and then throw them into 01Trie. To maximize XOR values, we can enumerate nodes and be greedy on Trie: from high to low, try to choose a different number than the current binary bit, and then select max max\max once again.

Code

Click to view the code

#include 
using namespace std;

const int MAXLOG=31;
const int N=3e5+5;

class \_01trie{
private:
 struct node{
 int ch[2];
 int siz,cnt;
 }T[N<<5];
 int p;
public:
 void update(int x){
 int now=0;
 for(int i=MAXLOG-1;i>=0;i--){
 bool b=(x&(1<<i));
 if(T[now].ch[b]==0) 
 T[now].ch[b]=++p;
 now=T[now].ch[b];
 }
 }
 int query(int x){
 int now=0,ans=0;
 for(int i=MAXLOG-1;i>=0;i--){
 bool b=(x&(1<<i));
 if(T[now].ch[b^1]){
 ans=ans<<1|(b^1);
 now=T[now].ch[b^1];
 }
 else{
 ans=ans<<1|b;
 now=T[now].ch[b];
 }
 }
 return ans;
 }
}Trie;

int n;

struct Graph{
 int to,w,next;
}G[N<<1];
int head[N],cnt;
void addEdge(int u,int v,int w){G[++cnt]=(Graph){v,w,head[u]}; head[u]=cnt;}

int val[N];

void dfs(int x,int fa){
 for(int i=head[x];i;i=G[i].next){
 int t=G[i].to;
 if(t==fa) continue;
 val[t]=val[x]^G[i].w;
 dfs(t,x);
 }
}

int main(){
 cin>>n;
 for(int i=1;i<n;i++){
 int u,v,w;
 cin>>u>>v>>w;
 addEdge(u,v,w);
 addEdge(v,u,w);
 }
 dfs(1,0);
 for(int i=1;i<=n;i++) Trie.update(val[i]);
 int maxx=0;
 for(int i=1;i<=n;i++) maxx=max(maxx,Trie.query(val[i])^val[i]);
 cout<}
Fold 

__EOF__

[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-qicki5uq-1658423572350). ( https://blog.csdn.net/LByte/p/16502346.html )]TheSky233 Text Link: https://blog.csdn.net/LByte/p/16502346.html About bloggers: Comments and private messages will be answered in the first place. perhaps Direct Private Trust I. Copyright Statement: All articles in this blog, except special statements, use BY-NC-SA License agreement. Reprint please indicate the source! Support blogger: If you feel the article is helpful to you, you can click on the bottom right corner of the article ** [Recommended] (javascript:void(0) 😉]** Once. Your encouragement is the blogger's greatest motivation!