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

# 概述

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

顺序表通过数组进行实现，其特点在于存储的空间是物理连续的，因此在读取数据上的时间复杂度仅$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 表

板子如下：

// 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)$ 级别的。