问题
在这一章节中，我们经常看到y总在实现各种数据结构中经常用到idx这个变量，这个变量到底有什么用呢？
为什么链表，Trie树和堆会用到idx来维护这个数据结构，而栈和队列就不用idx来维护，而是用hh和tt来维护呢？
解答
可以看出不管是链表，Trie树还是堆，他们的基本单元都是一个个结点连接构成的，可以成为“链”式结构。这个结点包含两个基本的属性：本身的值和指向下一个结点的指针。按道理，应该按照结构体的方式来实现这些数据结构的，但是做算法题一般用数组模拟，主要是因为比较快。
那就有个问题，原来这两个属性都是以结构体的方式联系在一起的，现在如果用数组模拟，如何才能把这两个属性联系起来呢，如何区分各个结点呢？
这就需要用到idx这个东东啦！
从y总给出的代码可以看出，idx的操作总是idx++，这就保证了不同的idx值对应不同的结点，这样就可以利用idx把结构体内两个属性联系在一起了。因此，idx可以理解为结点。
链表：
链表中会使用到这几个数组来模拟：
// head存储链表头指向的节点，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
h, e[N], ne[N], idx;
h表示头结点指针，一开始初始化指向-1，每次插入x的操作idx++。利用idx联系结构体本身的值和next指针，因此e[idx]可以作为结点的值，ne[idx]可以作为next指针。同理可以理解双链表。
//单链表
void add_to_head (int x)
{
e[idx] = x;
ne[idx] = h;
h = idx ++ ;
}
//双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a;
r[idx] = r[a];
l[r[a]] = idx;
r[a] = idx ++;
}
Trie树
Trie树中有个二维数组 son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：son[1][0]=2表示1结点的一个值为a的子结点为结点2;如果son[1][0] = 0，则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。
void insert(char str[])
{
int p = 0; //从根结点开始遍历
for (int i = 0; str[i]; i ++ )
{
int u =str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx; //没有该子结点就创建一个
p = son[p][u]; //走到p的子结点
}
cnt[p] ++; // cnt相当于链表中的e[idx]
}
堆
堆中的每次插入都是在堆尾，但是堆中经常有up和down操作。所以结点与结点的关系并不是用一个ne[idx][2]可以很好地维护的。但是好在堆是个完全二叉树。子父节点的关系可以通过下标来联系（左儿子2n，右儿子2n+1）。就数组模拟来说，知道数组的下标就知道结点在堆中的位置。所以核心就在于即使有down和up操作也能维护堆数组的下标（k）和结点（idx）的映射关系。 比如说：h[k] = x, h数组存的是结点的值，按理来说应该h[idx]来存，但是结点位置总是在变的，因此维护k和idx的映射关系就好啦，比如说用ph数组来表示ph[idx] = k, 那么结点值为h[ph[idx]], 儿子为ph[idx] * 2和ph[idx] * 2 + 1, 这样值和儿子结点不就可以通过idx联系在一起了吗？
详细请见https://www.acwing.com/solution/AcWing/content/5661/
if (op == "I")
{
scanf("%d", &x);
size ++ ;
idx ++ ;
ph[idx] = size, hp[size] = idx;//每次插入都是在堆尾插入
h[size] = x;//h[k], k是堆数组的下标，h存储的是结点的值，也就是链表中的e[idx]
up(size);
}
由于idx只有在插入的时候才会更新为idx ++，自然idx也表示第idx插入的元素
我感觉idx相当于一个分配器，如果需要加入新的结点就用++idx分配出一个下标
一句点破，胜过万言。
太帅了，恍然大悟
我还有个疑问：idx是分配器，如果输入26个首字母不一样的长度接近10的5次方的字符串，son[N][26]的N不是会不够用吗？
idx就会远超N，那 p = son[p][u]的p就可能爆了啊
题目给的是所有总的字符长度不超过10的5次方
明白啦，感谢！
你真的，我哭死
为啥idx++不行啊，不就相当与下标从0开始还是从1开始吗
说白了
就是一个就是一个邻接表
而insert操作就是一个尾插法，有头节点的链表尾插就要遍历到最后一个元素。这个for循环就是在做这个操作
而每次查询
就是一次邻接表的遍历过程，如果路径不通就返回0
透彻！
不用呀，最多就N个节点
00
个人感觉，第 i 列只能存对应的字母。而第０行的第 i 列，存的是以26个字母开头的单词。所以每次搜索要从 P = 0开始。
至于 idx 就相当于一个单词前后字母指向后面字母的指针一样。不知这样理解对否？
yes
真的透彻！
通透
厉害
int u=str[i] - ‘a’;是干什么的呀
取字符型的str[i]与字符’a’在ASCII码上的差值
我一开始就感觉这东西很像邻接表，但是又一直想不明白怎么用二维数组模拟出来，直到看到大佬的文章才瞬间懂了，大佬牛逼
取str[i]与字符在ascii码上的差值
谢谢你，我已经知道了，这个是我刚学算法时提出的问题，现在已经八个月前了，要是我这八个月一直在学算法多好啊，你们不要跟我学，我中途荒废了好长时间 现在还没有学完算法基础课。你们一定不要好高骛远 要多刷题引以为戒，然后欢迎大家在我的评论下面留言，我会一条一条看的，也可以发出你们目前的进度，互相监督，我这次不会在摆烂了
xd，一起加油就完事了
佬，一开始懵懵懂懂的怎么解决
我现在也还在学算法基础课 我的建议是先打好语言基础STL那些，和那个数据结构课听一听，不然y总讲的会有点懵，y总的算法基础课适合有一点点数据结构基础的人，0基础有点吃力 不懂的数据结构去b站或者其他地方搜一搜，其次就是刷题了，量到了自然就会了 熟能生巧 没什么其他经验 就是要多练，不能知识死背代码
感谢大佬指导
我不是大佬，只是希望你不要像我一样学到最后什么都没学好~少走点弯路
赞
共有 N 个操作，【 所有输入的字符串总长度 】不超过 10^5，所以Trie树最多N个节点
有良好表达能力的程序员真是不可多得的人才
给博主点赞，idx也就是没有此结点开创一个
这个idx为什么不会超了数组的范围呢
题目保证输入字符串总长度不超过N，节点个数不会超过N。
可是他不是有多次插入吗
总长度
那为什么不能用第一维去表示第几层呢，这样的话感觉更好理解
# 牛逼
//我感觉或许类比于地址更为合适//
讲的太好了
佬，太细了
我觉得这个整个写的都特别好。但是这个N的理解是不是不对？N不应该代表N个操作？当然这个题目也说了输入的总字符不超过10的5次方
Son[N][26]相当于链表中的next指针数组ne[N]，指向的是（提供的是）p的下一跳位置，insert函数中，如果p没有下一跳（p=0）则添加一个下一跳idx，如果有则跳到下一跳，idx更突出一种唯一性，独一无二性，即某一点的分支下不会有两个一样的字母
idx相当于是一个独一无二的编号了
一个不为0的递增编号
idx为什么不能为0啊
对答主关于用数组维护堆的讲法，理解为因为堆中的数据在down和up的操作中是不断移动的，所有不能象单链表和双链表那样处理，数组中的大量插入移动非常耗时。所有需要用另一个数组在维护这种位置变化的映射关系。比如：h[idx] = x，因为在堆中x的位置也就是idx是需要不断变化的，所以就用一个指向堆的数组ph[k] = idx来记录第k个插入值在堆中的变化位置；同时，我们还需要一个hp[idx] = k来记录堆中某个idx位置是第k插入的值
这里的idx不会超过const int N的大小吗？
题目的意思是所有的输入字符不会超过100000？
idx不会超const int N的，因为只有在创建一个新节点时idx会增加，如果有一个长度为1e5 - 1的字符串（题目说字符串输入总长度最大为1e5 - 1），那么存完这个字符串后idx正好是1e5-2
tql
只能说nb
透彻！！！
太牛了，醍醐灌顶
orz