找树的直径

定义:树中距离最远的两点

1.任取一点作为起点，找到距离该点最远的一个点u

2.再找到距离u最远的一点v

u和v之间的路径就是一条直径

树状数组

树状数组能处理的是下标为1~n的数组

考虑使用的情况：求前缀和、修改区间中的某个数，时间复杂度均为logn

基本思想

将x分解为二进制x = 2ⁱ¹ + 2ⁱ²+…+2^im (i1 > … > im)

则可以将[1,x]的区间划分为[1, 2ⁱ¹],[2ⁱ¹+1,2ⁱ¹+2ⁱ²],[2ⁱ¹+2ⁱ²+1, 2ⁱ¹+2ⁱ²+2ⁱ³] …,[2ⁱ¹+2ⁱ²+…+2^im-1 +1,2ⁱ¹+2ⁱ²+…+2^im ]这些区间

c[x]保存序列a区间[x-lowbit(x) + 1, x]中所有数的和

C[i] = A[i - 2^k+1] + A[i - 2^k+2] + … + A[i]; //k为i的二进制中从最低位到高位连续零的长度

该结构满足以下性质：

（1）每个内部节点c[x]保存以他为根的子树中所有叶节点的和

（2）每个内部节点c[x]的子节点数等于lowbit(x)的大小

（3）除数根外，每个内部节点c[x]的父节点是c[x+lowbit(x)]

（4）树的深度为O(logN)

基本思想

高效地存储和查找字符串集合的数据结构，存储的字母或者数字种类不能太多

LCA

朴素作法

对于每次询问，分别从两点出发，遍历所有祖先节点找到相同的节点

SHELL编程

零碎知识点

• echo -e "lbh666\tyzsb" -e使字符串可以转义
• printf命令类似C语言，printf "%d %d" 1 2

《IDT R30xx Family Software Reference Manual》阅读笔记

使用

1

make

makefile的规则

1
2
3
4

target ... : prerequisites ...
    command
    ...
    ...

过程

C 或者 C++ 程序从源代码生成可执行程序的过程，需经历 4 个过程，分别是预处理、编译、汇编和链接

参数

gcc -E

1

-E（大写）	预处理指定的源文件，不进行编译。

• gcc -E 指令只会将预处理操作的结果输出到屏幕上，并不会自动保存到某个文件。因此该指令往往会和 -o 选项连用，将结果导入到指令的文件中