第 30 章　序列与数组

配套例题：BISHI1 【模板】序列操作（题解已通过官方样例） 来源：S2 1-Linear List/1.Sequence_List_Static.cpp、2.Sequence_List_Dynamic.cpp；S3 day1《栈　队列》vector 均摊分析 前置：05-列表、21-复杂度与Python性能

学 C 的人写线性表要先写 struct { ElemType *data; int maxsize; int length; }， 再手写 IncreaseList 做扩容。Python 的 list 把这一整套都封装好了—— 但封装不等于免费。这一章讲清楚 list 底下到底是什么， 哪些操作是 \(O(1)\)、哪些是 \(O(n)\)，以及为什么二维数组不能用 [[0] * m] * n 建。

---

30.1　list 是动态数组，不是链表

这是第一个必须校准的认知。很多人从「Python 的列表可以随便插入删除」推出「它像链表」， 完全错了。CPython 的 list 内部就是 S2 里那个 SqList：

typedef struct {
    ElemType *data;   // 指向一块连续内存
    int maxsize;      // 已申请的容量
    int length;       // 实际元素个数
} SqList;

区别只有两点：

1. data 存的是指向 Python 对象的指针（每个 8 字节），不是值本身；
2. 扩容由解释器自动完成，不需要你调 IncreaseList。

由此直接推出全部性能特征：

事实	后果
内存连续	a[i] 是 \(O(1)\)，指针算术一步到位
内存连续	中间插入/删除要 memmove，是 \(O(n)\)
存的是指针	[0] * n 里的 \(n\) 个 0 是同一个对象（小整数缓存）
存的是指针	一个 \(10^6\) 的 int 列表约占 8MB 指针 + 对象本身，比 C 数组胖很多

一句话：list = C++ 的 std::vector，不是 std::list。 想要 \(O(1)\) 的两端操作请用 deque（33-队列与双端队列）， 想要 \(O(1)\) 的任意位置删除请用「数组模拟链表」（31-链表）。

---

30.2　append 为什么是均摊 \(O(1)\)

S3 day1 用「记账法」讲得非常清楚，这里搬过来。

设数组已申请容量 \(s\)，实际元素数 \(n\)，装填率 \(\alpha = n/s\)。 动态数组维持 \(\alpha \in [1/4, 1]\)：一旦 \(\alpha = 1\) 还要插入，就把容量翻倍并重设 \(\alpha = 1/2\)。

单次扩容要复制 \(s\) 个元素，是 \(O(s)\)。但扩容很稀疏：

假设一次插入/删除本身花 1 块钱，重新分配数组花 \(2s\) 块钱。 现在规定每次插入实际收费 5 块，其中 4 块存进银行。 上一次扩容之后至少发生了 \(s/2\) 次插入，存下 \(4 \times (s/2) = 2s\) 元， 恰好够付这次扩容。所以扩容可以视作免费，每次操作的平均代价不超过 \(5 = \Theta(1)\)。

这就是「均摊（amortized）\(O(1)\)」的含义：单次可能很慢，但连续 \(n\) 次总共是 \(O(n)\)。

说法	含义	例子
最坏 \(O(1)\)	每一次都快	a[i] 读取
均摊 \(O(1)\)	单次可能 \(O(n)\)，\(n\) 次总共 \(O(n)\)	a.append(x)
平均 \(O(1)\)	对随机数据快，可被构造数据卡	d[k] 字典查询

陷阱：均摊分析只对「连续做同一类操作」成立。 如果你在循环里 a.append(x) 然后立刻 a.pop()，卡在 \(\alpha\) 的临界点上反复扩容缩容， 理论上会退化。CPython 实际上只扩容不缩容（pop 到很小时才释放），所以不必担心。

CPython 的实际增长率不是翻倍，而是约 \(1.125\) 倍加常数（newsize + (newsize >> 3) + 6）， 更省内存，均摊复杂度不变。

---

30.3　list 操作复杂度全表

这张表决定了你的代码会不会 TLE，必须背下来。

操作	复杂度	说明
len(a)	\(O(1)\)	长度是存好的字段
a[i]、a[i] = x	\(O(1)\)
a.append(x)	\(O(1)\) 均摊
a.pop()	\(O(1)\)	从尾部弹
a.pop(0)	\(O(n)\)	后面全体前移 ← 队列千万别用
a.insert(i, x)	\(O(n)\)
del a[i]、a.remove(x)	\(O(n)\)
x in a	\(O(n)\)	← Python 算法题最高频 TLE 原因
a.index(x)、a.count(x)	\(O(n)\)
a[i:j]	\(O(j-i)\)	会复制出新列表
a[i:j] = b	\(O(n)\)	长度变化时要搬移
a + b	\(O(n+m)\)	新建列表
a * k	\(O(nk)\)
a.extend(b) / a += b	\(O(m)\) 均摊	就地追加，比 a = a + b 快
a.sort() / sorted(a)	\(O(n \log n)\)	Timsort，C 实现，常数极小
a.reverse()	\(O(n)\)	就地
a[::-1]	\(O(n)\)	复制一份新的
min/max/sum(a)	\(O(n)\)	C 层循环，很快
list(a) / a.copy()	\(O(n)\)	浅拷贝

三条会咬人的推论

1. 用 list 当队列 = \(O(n^2)\)。

# ❌ 1e5 次操作直接 TLE
q = []
q.append(x)
front = q.pop(0)          # O(n)！

# ✅ 用 deque 或头指针
from collections import deque
q = deque()
q.append(x)
front = q.popleft()       # O(1)

2. 循环里 in list = \(O(n^2)\)。

# ❌
seen = []
for x in a:
    if x not in seen:     # O(len(seen))
        seen.append(x)

# ✅
seen = set()
for x in a:
    if x not in seen:     # O(1)
        seen.add(x)

3. 「边遍历边删除」既慢又错。

# ❌ 每次 remove 是 O(n)，而且删除会让迭代器跳过元素
for x in a:
    if bad(x):
        a.remove(x)

# ✅ 重建列表，O(n)
a = [x for x in a if not bad(x)]

通用原则：需要频繁删除时，不要真的删——打个标记，最后一次性重建。 这个思路在堆里叫「懒删除」（35-优先队列与堆）， 在链表里叫「逻辑删除」（31-链表）。

---

30.4　序列的八类通用操作

S2 那份 SqList 定义了 12 个函数接口，Python 里全部有对应写法。 下表把「教科书线性表 ADT」和 Python 对上，顺便标出复杂度。

教科书操作	含义	Python 写法	复杂度
InitList	建空表	a = []	\(O(1)\)
ClearList	清空	a.clear() 或 a[:] = []	\(O(n)\)
ListEmpty	判空	if not a:	\(O(1)\)
ListLength	求长	len(a)	\(O(1)\)
GetElem(i)	取第 \(i\) 个	a[i]	\(O(1)\)
LocateElem(e)	求 \(e\) 的位置	a.index(e)	\(O(n)\)
PriorElem(e)	求前驱	a[a.index(e) - 1]	\(O(n)\)
NextElem(e)	求后继	a[a.index(e) + 1]	\(O(n)\)
ListInsert(i, e)	在 \(i\) 前插入	a.insert(i, e)	\(O(n)\)
ListDelete(i)	删第 \(i\) 个	del a[i]	\(O(n)\)
ListPrint	输出	" ".join(map(str, a))	\(O(n)\)

判空一律写 if not a:，不要写 if len(a) == 0:（多一次函数调用）， 更不要写 if a == []:（要构造一个空列表再比较）。

PriorElem/NextElem 在教科书里是「按值找前驱」，是 \(O(n)\) 的。 如果题目要求的是有序集合意义下的前驱后继（BISHI4、BISHI5）， 那就完全是另一个数据结构了，见 34-集合与多重集合。

---

30.5　二维数组：唯一正确的初始化方式

这是 Python 算法题最经典的低级错误，没有之一。

# ❌ 灾难写法
g = [[0] * m] * n
g[0][0] = 1
print(g)          # 每一行的第 0 个都变成了 1！

原因回到 30.1：list 存的是指针。[x] * n 复制的是 \(n\) 份同一个对象的引用。 外层的 * n 让 \(n\) 行指向同一个内层列表，改一行等于改全部。

内层的 [0] * m 为什么没事？因为 int 不可变，g[i][j] = 1 是重新绑定下标， 不是修改那个 0 对象。所以「一维乘法安全，二维乘法致命」。

四种正确写法

g = [[0] * m for _ in range(n)]          # ✅ 标准写法，最快
g = [[0 for _ in range(m)] for _ in range(n)]   # ✅ 正确但慢一点
g = [[0] * m for _ in [0] * n]           # ✅ 等价
import copy; g = copy.deepcopy(proto)    # ⚠️ 能用，但慢，竞赛别用

推荐第一种：外层用推导式保证每行是新对象，内层用 * m 走 C 层复制。

三维及以上

f = [[[0] * c for _ in range(b)] for _ in range(a)]     # a × b × c

陷阱：三维 DP 数组 \(100 \times 100 \times 100 = 10^6\) 个元素， Python 里光建数组就要几百毫秒，且占约 40MB。 高维 DP 优先考虑滚动数组降维，见 100-DP入门。

一维展平：高维数组的性能写法

当维度固定且性能吃紧时，用一维 list + 手算下标比嵌套列表快约 2 倍 （少一次指针解引用、少一次边界检查）：

g = [0] * (n * m)
# g[i][j]  ->  g[i * m + j]
g[i * m + j] = v

网格 BFS/DP 的热循环里这个技巧很有用，见 61-BFS广度优先搜索。

---

30.6　除了 list，还有哪些「数组」

容器	元素类型	单元素内存	随机访问	适用场景
list	任意	8 字节指针 + 对象	\(O(1)\)	默认选择
bytearray	0–255 整数	1 字节	\(O(1)\)	布尔标记、筛法、01 串
bytes	0–255 整数	1 字节	\(O(1)\)	只读，可当字典键
array.array	同类型数值	2/4/8 字节	\(O(1)\)	大规模数值数组省内存
int（当位图）	单个 bit	1/8 字节	\(O(n)\) 取单位	集合的位运算
deque	任意	8 字节指针	\(O(n)\)	两端操作
str	字符	—	\(O(1)\)	不可变，不能改单字符

bytearray 是被低估的武器

\(10^7\) 规模的布尔数组，[False] * 10**7 要 80MB（指针）， bytearray(10**7) 只要 10MB。而且它支持切片步长赋值，能把内层循环压进 C 层：

is_p = bytearray([1]) * (n + 1)      # 下标 0..n 先全标成质数，每格只占 1 字节
is_p[0:2] = b"\x00\x00"              # 切片 0:2 覆盖下标 0 和 1，右端开区间不含 2
for i in range(2, isqrt(n) + 1):     # 筛到根号 n 即可：合数必有不超过根号 n 的质因子
    if is_p[i]:                      # i 还活着说明它是质数，才需要划掉它的倍数
        # 步长切片整段赋 0，内层循环下沉到 C 层；右值长度必须与切片元素个数相等
        is_p[i * i::i] = bytearray(len(range(i * i, n + 1, i)))   # 从 i*i 起步，更小的倍数已被筛掉

详见 21-复杂度与Python性能 与 80-数论基础。

大整数当位图

Python 的 int 是任意精度的，可以当超高效位图用：\(10^6\) 个 bit 只要 125KB， 且 &、|、>> 全是 C 层的多字长运算。 BISHI4 / BISHI5 的正解就建立在这个技巧上，见 34-集合与多重集合。

s = 0                    # 空集合：一个 bit 都没置 1
s |= 1 << x              # 插入 x：把第 x 位置 1，或运算不动其他位
s &= ~(1 << x)           # 删除 x：~(1 << x) 是仅第 x 位为 0 的全 1 掩码
(s >> x) & 1             # 查询 x：右移把第 x 位挪到最低位，再与 1 取出
s.bit_length() - 1       # 最大元素：位数减 1 就是最高位的下标
(s & -s).bit_length() - 1   # 最小元素：s & -s 借补码取出最低位的 1（lowbit）

代价：大整数的位运算是 \(O(\text{位数}/64)\)，不是 \(O(1)\)。 \(10^6\) 位的整数做一次 |= 约 \(1.5 \times 10^4\) 个机器字， 所以不能在循环里对整个大位图反复做全局运算——要分块。

---

30.7　例题

BISHI1 【模板】序列操作（简单）

维护一个初始为空的整数序列，\(q \le 7 \times 10^3\) 次操作： 1 x 尾部追加；2 删尾；3 i 输出下标 \(i\) 的元素（下标从 0 开始）； 4 i x 在下标 \(i\) 与 \(i+1\) 之间插入 \(x\)；5 升序排序；6 降序排序； 7 输出长度；8 输出整个序列。 题面见 BISHI1 原题（牛客）。

这题就是把 30.4 那张表逐行翻译成代码，八个操作全部有原生方法对应：

操作	Python	复杂度
1 尾插	a.append(x)	\(O(1)\)
2 尾删	a.pop()	\(O(1)\)
3 下标查	a[i]	\(O(1)\)
4 中间插	a.insert(i + 1, x)	\(O(n)\)
5 升序	a.sort()	\(O(n \log n)\)
6 降序	a.sort(reverse=True)	\(O(n \log n)\)
7 求长	len(a)	\(O(1)\)
8 打印	" ".join(map(str, a))	\(O(n)\)

为什么 \(O(n)\) 的 insert 不会超时？ \(q \le 7 \times 10^3\)，最坏 \(7\times10^3\) 次插入 每次搬 \(7 \times 10^3\) 个元素 \(\approx 5 \times 10^7\) 次元素搬移——但这是 memmove， 在 C 层一次搞定，实测毫秒级。判断能否用 \(O(n)\) 操作时，要区分「Python 层循环次数」和 「C 层元素搬移次数」，后者的常数小两个数量级。

为什么反复排序不会超时？ 最坏 \(7\times10^3\) 次 \(O(n\log n)\) 排序看着是 \(10^8\)， 但 Timsort 会识别已有序的 run：连续的 5 5 5（重复升序）或 5 6 5 6（升降交替） 都只需 \(O(n)\) 就能确认，退化不了。

三个坑：

1. 操作 4 是「在下标 \(i\) 与 \(i+1\) 之间插入」，即 insert(i + 1, x)，不是 insert(i, x)；
2. 操作 2/5/6/7/8 这几行只有一个 token，不能按「每行两个数」读，必须用游标逐 token 取；
3. 操作 8 要 join 成一行，逐个 print 会被 IO 打爆。

import sys


def main():
    # 每条操作的 token 数不固定，整读后按游标逐个消费，比按行解析稳
    data = sys.stdin.buffer.read().split()
    q = int(data[0])            # 操作条数
    i = 1                       # token 游标，data[0] 已被 q 取走
    a = []                      # 被维护的序列本体
    out = []                    # 输出先攒着，结尾一次写出
    for _ in range(q):
        op = data[i]            # 操作码保持 bytes，直接与 b"..." 比较，省一次解码
        i += 1                  # 操作码消费掉，游标停在它的参数位上
        if op == b"1":
            a.append(int(data[i])); i += 1      # 尾插均摊 O(1)；吃掉 1 个参数
        elif op == b"2":
            a.pop()                             # 删尾不搬移元素，O(1)；本操作无参数
        elif op == b"3":
            # 题面下标从 0 起，与 Python 一致，取值不需要 ±1 偏移
            out.append(str(a[int(data[i])])); i += 1
        elif op == b"4":
            p = int(data[i])                    # 参照位置的下标
            # 「在下标 p 与 p+1 之间插入」落到 Python 就是插到位置 p+1 上
            a.insert(p + 1, int(data[i + 1])); i += 2   # 位置与数值共 2 个参数
        elif op == b"5":
            a.sort()                            # Timsort 能识别已有序的 run，反复排序不退化
        elif op == b"6":
            a.sort(reverse=True)                # 降序同理，仍是就地排序，不新建列表
        elif op == b"7":
            out.append(str(len(a)))             # 长度是存好的字段，O(1)
        else:                       # op == b"8"
            out.append(" ".join(map(str, a)))   # 整段拼成一行；逐个 print 会被 IO 拖垮
    sys.stdout.write("\n".join(out) + "\n")     # 全部输出一次落盘


main()

完整题解（含全部注释）：solutions/BISHI1.py。

反面教材：如果 \(q\) 开到 \(10^5\)，insert 就会变成 \(10^5 \times 10^5 = 10^{10}\) 次搬移，memmove 也救不了。那时候需要块状链表或平衡树—— 而 Python 里这两者都很难写快，实战中通常要换思路（离线、分治）。 好在笔试模板题的数据规模是有意留出余量的。

---

30.8　本章速查

要点	结论
list 的本质	动态数组（std::vector），不是链表
append	均摊 \(O(1)\)，记账法保证
pop() vs pop(0)	\(O(1)\) vs \(O(n)\)
insert / del / remove	都是 \(O(n)\)
x in list	\(O(n)\)，改用 set
切片 a[i:j]	\(O(j-i)\)，会复制
二维数组	[[0] * m for _ in range(n)]，绝不用 [[0]*m]*n
判空	if not a:
高维/热循环	一维展平 g[i * m + j] 快约 2 倍
布尔数组	bytearray，省 8 倍内存且支持切片步长赋值
位集合	大整数 int，省 64 倍内存
\(O(n)\) 操作能否用	看它是Python 层循环还是 C 层 memmove

想做的事	该用什么
随机下标访问	list
两端插入删除	deque（33 章）
任意位置 \(O(1)\) 删除	数组模拟链表（31 章）
判存在 / 去重	set（34 章）
取最值	heapq（35 章）
区间和 / 区间改	树状数组（39 章）