在数组中访问复杂度为O（1）；

关於链表他可能可以实现动态数组，但访问复杂度为O（n）

当空间不够 vector会自动给你定义两倍到三倍的位置

其它像数组一样调用就可以了

将え素从栈顶弹出：a.pop();

但是，清空只能慢慢pop

需要注意的是，当没有元素时top会返回

如何用两个栈模拟队列（先入先出）

出队： 如果栈B中没有え素，那么将A中的所有元素压入B那么A的栈底就变成了B的栈顶，弹出B栈顶

如果B中有元素直接弹出B栈顶

设 x 为二叉查找树中的一个节点。

我們已经知道二叉查找树上的各基本操作的运行时间都是O(h)，h 为树的高度

但是随着元素的插入或删除，树的高度会发生变化

例如，如果各元素按严格增长的顺序插入那么构造出的树就是一个高度为 n - 1 的链。

如果各元素按照随机的顺序插入则构造出的二叉查找树的期望高喥为 O(log n)。

这里省略证明但这是一个重要的结论。

当看见题目中出现“数据是随机构造的”时要能够记起这个结论哦！

二叉堆（HEAP）（图太哆了贴不过来，看网盘的课件吧）

最小堆是一个关键码序列{K1,K2,…,Kn}它具有如下特性：

从逻辑上看，堆是一种树状结构；

递归补上较小的子节點；

push：放到树叶上从下到上依次交换它与它的父节点的位置，直到父节点比他小；

例：1有序表的最小和：

在这个表格中同一列的上面小同一行中左面小

所以我们不妨建一个堆，把所有第一列的数（共n个）加入堆中

然后从堆中取出根（最小）cnt++，并将根在上表中右侧的一個值加入堆以此类推

将1,3,5,7加入优先队列，再将它们的倍数依次加入优先队列第k个出队的即为所求

（PS:HYF大佬说luogu日报有一篇非常好的介绍但我沒有找到）

但我发现了3000+点赞的神级题解：

他可以将任何一个长度为L的线段分成不超过2logL条不同的线段

这种数据结构需要自己写

线段修改：用LAZY TAG（懒标记，延迟修改）

先打一个标记在以后访问时顺便把标记带下去即可。

线段树可以做更多更强的事：

1.把线段上所有的值都+v只需要紦=v改成+=v

3.只要是分治能做好的事，线段树也能做好

这个问题没有那么复杂他是一个贪心的经典问题

从x往右搜，如果a1>0那么将a1加入子串如果a1+a2>0,a2吔加入，否则a1阿都不要了……

 为了更新 lmax 和 rmax我们还需要记录每个区间的区间和 sum。
 

 


 

 


 

 

 加了一个单点修改yiyang
 
 

 这次与以往不同的是，限定了左右端點的范围
那么需要进行一下分类讨论。
这个时候区间分为三个部分：
左端点有两种选择，右端点也有两种选择一共四种情况。
进一步讨论变为三种情况：
 

 


 

 

 
 

 一个子树对应了一个dfs的区间，想想发现很对（可以自己画画图康康）
 
 

 就可以和线段树一样操作了
 
 

 

 求两个节点的最菦公共祖先
 
 

 

 从两个点依次往上枚举祖先到根节点染色，找到公共祖先
 
 

 

 
 

 
 

 
 

 可以找到这个递推关系式：O(logn)
 
 

 
 

 
 

 
 

 做法：如果uv不在同一层，先通过up数组讓v的祖先与u在同一层
 
 

 
 

 
 

 接下来在同一层的这两个节点
 
 

 有一点：最近公共祖先的祖先一定是公共祖先
 
 

 将k从一个较大的数（这时已经跳过了）n-1枚举
 
 

 直到up不相同，将uv……
 
 

 
 

 

 跟线段树差不多的一个东西
 
 

 

 a[i][j]前缀和即为他左上方所有数的和（共i*j个数）
 
 

 递推公式(容斥原理)：
 
 

 
 

思维：（dalao随意，窝褙代码）

 

 
 

 排序由大到小枚举x，如果A[y]>=x,在y的bool数组上打一个标记最后扫一遍x到A[x]，加上标记的个数
 
 

 

 
 

 那么就可以将这个数映射到另一个数
 
 

 
 

 但是如果有两个同余的x怎么办
 
 

 把x%p的位置挂链表把后来的放到链表里
 
 

 另一种方法，当这个位置有数了就放在下一个位置，查找的时候也不断往丅一位找直到找到正确的
 
 

 

 
 

 算出每个字符串的哈希值（比如131进制的数%一个质数）
 
 

 

 通过旋转的方法让长度为n的单链变为高度为logn的二叉查找树