相思只在，丁香枝上，豆蔻梢头。

# 概述

线性表是一些数据元素的有限序列，这些数据元素称为节点。根据存储方式的不同可以分为顺序表示和链式表示。不论是链式表示还是顺序表示，所需要的基本功能都是类似的。两者的区别在于对不同功能的执行效率不同。对于线性表，一般情况下需要的主要操作为插入 / 删除数据和读取数据。此外，辅助的操作还包括获取线性表的长度、判断线性表是否为空、创建 / 删除整个线性表、线性表扩容等。

顺序表通过数组进行实现，其特点在于存储的空间是物理连续的，因此在读取数据上的时间复杂度仅 $O(1)$ 。而对于插入数据，其操作为将插入点的后的所有节点依次后移 $1$ 个单位，然后将数据插入到空余的位置中。删除数据的操作也是同理的。容易看出，若插入的数据不在顺序表的结尾，则插入删除数据的时间复杂度为 $O(n)$ ，若在表尾，则复杂度仅 $O(1)$ 。此外，由于数组的内存分配是在声明开始便给定的，因此在数据过多时，需要对顺序表进行扩容，扩容时需要将全表数据挪移至新表，其时间复杂度为 $O(n)$ 。

对于链表，其特点在于存储空间是物理不连续的，相邻的节点之间通过指针进行关联。因此，要想寻找某个节点，必须从头节点开始依次依次通过指针向下访问。于是，链表在读取数据上的时间复杂度为 $O(n)$ 。对于插入数据和删除数据，链表需要先找到对应的节点，耗费时间复杂度 $O(n)$ ，之后进行指针修改和数据读写，复杂度为 $O(1)$ ，于是插入数据和删除数据的时间复杂度为 $O(n)$ 。除非链表在头节点或尾节点进行插入删除数据，此时时间复杂度显然为 $O(1)$ 。注意到，尽管链表和数组在插入删除数据上的时间复杂度均为 $O(n)$ 级别，但链表耗费 $O(n)$ 级别的操作为读取，在寄存器中进行，而数组耗费 $O(n)$ 级别的操作为数据移动，本质是数据写入，在内存中进行，速度远慢于在寄存器中进行的读取操作。此外数组有时需面对数组扩容的问题，同样是 $O(n)$ 级别操作。因此面对频繁的数据增删问题，采用链表进行实现是效率远高于采用数组进行实现的。

# 单链表

# 声明

单链表是最基本的链表，其每个节点分为数据域和指针域。其中数据域包括一个变量，用于储存链表希望保存的数据，而指针域有一个变量，用于储存指向链表下一个节点的指针。

单链表的结构声明

	typedef struct ListNode{
	int data; // 数据域，用于保存数据
	ListNode *next; // 指针域，变量为指向下一个节点的指针。
	}ListNode, *List;

# ST 表

用来解决区间最值问题 (RMQ) 的数据结构，复杂度为 $O(n \log n)$ 预处理， $O(1)$ 查询。

P3865 【模板】ST 表

板子如下：

ST表

	// from https://www.cnblogs.com/zwfymqz/p/8581995.html
	#include <cstdio>
	#include <cmath>
	#include <algorithm>
	using namespace std;

	const int MAXN = 1e6+10;

	inline int read() {
	char c=getchar();int x=0,f=1;
	while(c<'0'\|\|c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
	}

	int Max[MAXN][21];

	int Query(int l,int r) {
	int k=log2(r-l+1);
	return max(Max[l][k],Max[r-(1<<k)+1][k]);// 把拆出来的区间分别取最值
	}

	int main() {
	#ifdef WIN32
	freopen("a.in","r",stdin);
	#endif
	int N=read(),M=read();
	for(int i=1;i<=N;i++) Max[i][0]=read();
	for(int j=1;j<=21;j++)
	for(int i=1;i+(1<<j)-1<=N;i++)// 注意这里要控制边界
	Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);// 如果看不懂边界的话建议好好看看图
	for(int i=1;i<=M;i++) {
	int l=read(),r=read();
	printf("%d\n",Query(l,r));
	}
	return 0;
	}

可以看到，核心代码就是创建 ST 表的两个 for 循环：

	for(int i=1;i<=N;i++) Max[i][0]=read();
	for(int j=1;j<=21;j++)
	for(int i=1;i+(1<<j)-1<=N;i++)// 注意这里要控制边界
	Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);// 如果看不懂边界的话建议好好看看图

# 树状数组

# 概述

支持单点修改和区间查询的，代码量小的数据结构。

普通树状数组维护的信息及运算要满足结合律且可差分，如加法、乘法、异或等。

结合律： $(x \circ y) \circ z = x \circ (y \circ z)$ , 其中 $\circ$ 是一个二元运算符。
可差分：具有逆运算的运算，即已知 $x \circ y$ 和 $x$ 可以求出 $y$ .

# 基本操作

# 区间查询

转化成前缀和查询。

	int getsum(int x) { //a [1]..a [x] 的和
	int ans = 0;
	while (x > 0) {
	ans = ans + c[x];
	x = x - lowbit(x);
	}
	return ans;
	}

复杂度 $O(\log n)$ .

# 单点修改

	void add(int x, int k) {
	while (x <= n) { // 不能越界
	c[x] = c[x] + k;
	x = x + lowbit(x);
	}
	}

复杂度 $O(\log n)$ .

# 建树

一般可以直接转化为 $n$ 次单点修改，时间复杂度 $\Theta (n \log n)$ .

# 题目

例 1 寻找两个正序数组的中位数 (LeetCode 4)
给定两排好序的数组 A, B , 求两者所有元素中第 $k$ 大的元素。

复杂度 $O(\log k)$ , 方法是二分。由于 $k \leq m+n$ , 因此复杂度是 $O(\log m+n)$ 级别的。

# 概述

# 单链表

# 声明

# ST 表

# 树状数组

# 概述

# 基本操作

# 区间查询

# 单点修改

# 建树

# 题目

积分重修指南(雾)