2025五一集训营（普转提）Day1下午笔记 最后更新于 2025-05-01 18:35:08

# 数据结构 ### 异或 ###### C++中式子：a^b ###### 性质：将两个数转化为二进制，每两相对位都进行异或运算，如果两位数字不同，值为1，如果相同，值为0 ###### 公式：a[l]^a[l+1]^…^a[r]=(a[1]^a[2]^...^a[l-1])^(a[1]^a[2]^...^a[r]) ### 字典树Trie ###### 字典树指的是某个字符串集合构造的有根树。字典树较好的利用了字符串的公共前缀，因此有效的节约存储空间 ###### 典型应用是统计、排序和保存大量的字符串(不仅局限于字符串) ###### 三个基本性质： ###### 1、根结点不包含字符，除根结点外每一个节点都只包含一个字符 ###### 2、从根结点到某一节点，路径上经过的字符链接起来，为该节点对应的字符串 ###### 3、每个节点的子节点包含的字符都不相同 ###### 建树： ###### 儿子数组 son[][] 存储从节点 p 沿着 j 这条边走到的子节点 ###### 计数数组 cnt[] 存储以节点 p 结尾的单词的个数 ###### 节点编号 idx ###### 建树的逻辑： ###### 1.空Trie 仅有一个根节点，编号为 0，son[][] 初始值都为 0 ###### 2.从根开始插，枚举字符串的每个字符 ###### 如果有儿子，则 p 指针走到儿子 ###### 没有则先创建儿子，p 指针再走到儿子 ###### 3.在单词结束点记录插入次数 ###### 查询： ###### 1.从根开始查询，扫描字符串 ###### 2.有元素 s[i], 则往下继续走, 能走到词尾，则返回插入次数 ###### 3.无元素 s[i]，直接返回 0 ### Σ（Sigma） ###### Σ表示对一系列元素的求和操作。该符号通常用于表示需要对某个集合中的元素进行累加的情况。 ###### 使用方式：Σ（表达式，变量，起始值，结束值）（表达式表示每次累加的具体操作，变量表示循环变量，起始值和结束值表示循环的范围） #### 代码实现Σ： ```cpp #include <bits/stdc++.h> using namespace std; int main(){ int n; long long num=0; cin>>n; for(int i=1;i<=n;i++){ num += i; } cout<<num; return 0; } ``` ##### 小插曲： ###### 按位或：| ###### 按位与：& ###### 按位异或：^（也就是上面的） ### 分块 ###### 注：严格来说，分块是一种思想，不是数据结构 ###### 基本思想：通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。 ###### 分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。 ###### 分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。 ### 莫队 ###### 核心就两个字： #### 暴力！ ###### ~~（别不信，钟神说的）~~ ###### 例：枚举m个数，把数一个一个插入进去，取出左端点和右端点，查某个数共出现了几次 ###### 画图的时候有点像滑动窗口，但是不是哈 ###### 如果上一个左端点位置小于下一个左端点位置，删除两个队左端点空缺的部分，否则，补上两个队左端点空缺的部分 ###### 右端点相反（小于便补，大于便删） ### 逆序对 ###### 枚举n个数，求有多少个i,j能使a[i]>a[j]且i<j ###### 可以用分治做 ###### 给定l,r,找出[l,r]区间有多少个逆序对 ###### 二分找出中间数，分别算两边，找出i在左边，j在右边的答案 ###### 如果左边没数，放入右边 ###### 如果右边没数，放入左边 ##### 全部数的区间——分治