Question

Array

储存一个数列，直觉的方式是使用一个阵列。

更新第 k 项：O(1)。

插入第 k 项、删除第 k 项：需要挪移资料。O(N)。

区间总和、区间最大值、区间最小值：逐个累计。O(N)。

List

更新第 k 项、插入第 k 项、删除第 k 项：需要定位。O(N)。

区间总和、区间最大值、区间最小值：逐个累计。O(N)。

串列与阵列的步骤数量，相比之下，显然串列小于等于阵列──然而两者的时间複杂度都是 O(N)。可以发现现行的时间複杂度标记方式，不是那麽精准，无法区分两者的快慢差异。

Unrolled Linked List

更新第 k 项：O(A)。

插入第 k 项、删除第 k 项：O(A + 2B) 到 O(2A + B)。

使用 sqrt decomposition，三者皆是 O(sqrtN)。

区间总和、区间最大值、区间最小值：每块额外记录数值，先查询块、再查询元素。O(A) 到 O(A + 2B)。

使用 sqrt decomposition，三者皆是 O(sqrtN)。

如果只需更新、查询，不需插入、删除，此时可以用阵列代替串列，容易实作。

UVa 12003 11922 11990 12345

Sequence 资料结构: Binary Search Tree

粗浅的理解、错误的方式

既然 BST 是储存大量数字的资料结构，我们尝试运用 BST 来储存一个数列。

数列的索引值是有序的，BST 是有序的，我们尝试以索引值大小顺序，做为 BST 的排序依据。BST 的每个节点，额外记录数列的数值。

虽然可以迅速更新第 k 项，但是无法迅速插入第 k 项、删除第 k 项，索引值无法保持连续整数。

深刻的理解、正确的方式

Search Tree、Heap 的功能是排顺序，排序依据不见得得是数字大小顺序，排序依据也不见得要储存于节点之中。比如图论领域的资料结构“ Link-Cut Tree ”所使用的 BST，排序依据是树上节点的父子顺序。

令左子树是索引值较小的项、右子树是索引值较大的项。排序依据，仍是索引值大小顺序，但是排序依据不必储存于节点之中。

更新第 k 项：就是找到 BST 第 k 名。BST 的每个节点，额外记录子树的节点个数，以便快速得到名次。

插入第 k 项：先找到 BST 第 k 名，如果没有右小孩，就挪至右小孩；如果拥有右小孩，就挪至次大节点（即 BST 第 k+1 名）的左小孩。然后原本第 k 名的位置，存入数列第 k 项。最后记得更新扩充资讯，由树叶往树根方向。

删除第 k 项：先找到 BST 第 k 名，如果没有小孩，就直接删除；如果拥有左小孩、没有右小孩，就拿左子树顶替第 k 名；如果拥有左小孩、拥有右小孩，就拿次大节点顶替第 k 名，再拿次大节点的右子树顶替次大节点（此时次大节点无左小孩）。最后记得更新扩充资讯，由树叶往树根方向。

不必死背这些流程。只要细心观察 BST，很容易推理出来。

如果旋转节点、平衡 BST，那麽更新、插入、删除、寻找次大节点的时间複杂度从 O(N) 变成 O(logN)。

区间总和、区间最大值、区间最小值：每个节点额外记录该子树所有节点的总和、最小值、最大值！交给读者。

任意区间的最大（小）区间和：交给读者。

Sequence 资料结构: “Fake” Segment Tree

“Fake” Segment Tree【尚无正式名称】

此资料结构由竞赛选手发明，没有发表为正式的学术论文。目前发现最早出现于 Baltic OI 2001: Mars Maps ，官方解答提供了此资料结构的程式码。

此资料结构最初没有特定名称。传入中国之后，竞赛选手将名称定调为 Segment Tree，创造大量相关题型，例如 SPOJ: GSS3 ，令 Segment Tree 之名称被发扬光大。然而“ Segment Tree ”是既有的资料结构名称，所以此资料结构势必另取他名，以免混淆。

建立资料结构

递迴二分区间，树叶存放数列，一个树叶储存一项；非树叶存放扩充资讯，诸如区间总和、区间最大值、区间最小值。

节点最多是 2N-1 个，空间複杂度为 O(N)，时间複杂度为 O(N)。N 为数列长度。

更新第 k 项、区间总和、区间最大值、区间最小值

类似二元搜寻树，时间複杂度为树的深度 O(logN)。

UVa 11297 12299

插入第 k 项、删除第 k 项

不负责任地交给读者。

任意区间的最大（小）区间和

不负责任地交给读者。

ICPC 3938

推广到高维度

伪线段树可以推广到高维度，从一维数列变成二维阵列、三维阵列。二维伪线段树，是先制作一棵第一维度的伪线段树（称作 X 树），然后每个节点各自接上一棵第二维度的伪线段树（称作 Y 树）。中文网路称作“树套树”。

UVa 12698

更新区间：楔子

伪线段树也可以更新区间。首先简化问题，把数值改成颜色。如果区间不是相同颜色，就继续递迴对半分割下去。如果区间是相同颜色，暂且不分割！

更新第 k 项，有三大步骤：一、搜寻之时，原有颜色分离，挪往下层。二、就位之时，直接覆盖颜色，删除子树（或者无视子树）。三、回溯之时，相同颜色合併，挪往上层。

此番技巧尚未有正式名称，英文网路称作“lazy propagation”，中文网路称作“延迟标记”。

更新区间：视情况左右子树都得走，并分割更新区间。

查询第 k 项：一旦遭遇颜色，即得答案，不必深入子孙。

查询区间颜色是否一致：视情况左右子树都得走，并分割查询区间。当节点区间大于等于查询区间时，一旦遭遇颜色，即可判断异同，不必深入子孙。当节点区间小于等于查询区间时，一旦遭遇无色，即得答案为否，不必深入子孙。不能推广到高维度。

这四项操作的时间複杂度都是 O(logN)。

更新区间：统统改为一数值

更新第 k 项、更新区间：运用“lazy propagation”技巧，凡遭遇已改值的区间，则分离挪往下层。

查询第 k 项、查询区间：凡遭遇已改值的区间，即得答案，不必深入子孙。

查询区间不能推广到高维度。

更新区间：统统增减一数值

更新第 k 项、更新区间：直接在对应区间累计增减值。

查询第 k 项：累加路线上的增减值。

似乎无法查询区间。

这似乎也被归类于“lazy propagation”技巧。

UVa 11402 11992

Bottom-up “Fake” Segment Tree【尚无正式名称】

BST 和 FST 要实作很久，赶时间的竞赛选手避之唯恐不及。如果不需要插入第 k 项、删除第 k 项，只需要更新第 k 项、查询区间，此时就可以採用特殊资料结构，编写较少程式码。

只能更新第 k 项、查询区间：Bottom-up “Fake” Segment Tree
只能更新第 k 项、查询区间总和：Binary Indexed Tree
只能更新第 k 项、查询区间极值：Sparse Table

2010 年由竞赛选手清华大学张昆玮《 统计的力量——线段树全接触 》提出。我不清楚是否已有正式学术论文。

读者须具备“ Bitwise Operation ”基础。

Sequence 资料结构: Binary Indexed Tree

Binary Indexed Tree（Fenwick Tree）

存放一串数列，可以快速算出任意区间的总和。

可以更新数值，但是不能插入、删除数值。

閒置阵列第零格。观察前缀和，切割成数段。切割方向：索引值由小到大。切割长度：二的次方，数量级尽量大。

索引值化作二进位，上述行为即是：索引值逐次删去最低位的 1。

10 的二进位是 1010。
删去最低位的 1，切割成 1010 ~ 1000+1，剩下 1000。
删去最低位的 1，切割成 1000 ~ 0000+1，剩下 0000，结束。

7 的二进位是 111。
删去最低位的 1，切割成 111 ~ 110+1，剩下 110。
删去最低位的 1，切割成 110 ~ 100+1，剩下 100。
删去最低位的 1，切割成 100 ~ 000+1，剩下 000，结束。

每种前缀和，皆实施切割，总共只有 N 种区段！N 个区段和，依序储存于阵列，得到 Binary Indexed Tree。是阵列、不是树。

Binary Indexed Tree 得视作伪线段树的精简版本：扩充资讯是区间总和；移除树根及全部右小孩。

计算第 1 项到第 k 项的总和

挑出对应的区段，进行累加。

更新一项数值

看看哪些区段包含这一项，补上差值。

複杂度

建立时间为 O(NlogN)，建立空间为 O(N)，更新一项数值的时间是 O(logN)，计算任意区间总和的时间是 O(logN)。

注：採用伪线段树的建立手法，建立时间变为 O(N)。

UVa 11423 11610

推广到高维度

Binary Indexed Tree 可以推广到高维度，建立方法是逐步处理各维度。以二维为例：矩阵切成一条一条的横条，每个横条分别建立 BIT，每个横条都有 N 种区段；然后针对每一种区段，再分别建立垂直方向的 BIT。

建立时间为 O(XlogX * YlogY * ...)，建立空间为 O(XY...)，更新一项数值的时间是 O(logX * logY * ...)，计算任意矩形区域总和的时间是 O(2^D * logX * logY * ...)。

UVa 11601

Sequence 资料结构: Sparse Table

Sparse Table【注：古代名称，今日看来词不达意。】

存放一串数列，可以快速算出任意区间，其中一个最小（大）值的所在位置。有人称作 Range Minimum Query 问题。

不能更新、插入、删除数值。

依序求出宽度为 1、2、4、8、……的区间最小值，区间的所有可能位置都要算一遍。两个窄区间可以快速合成出一个宽区间。

将宽度为 1、2、4、8、……的区间最小值，储存于表格。

t(i, j) =
 { min{ t(i-1, j), t(i-1, j+2^(i-1) }  , if i > 0
 { value[j]                            , if i = 0

实作时，通常表格中记录的是索引值、指标，而不是直接记录数值的最小值。

计算区间最小值（的索引值）

查询时，先从表格中找到宽度略短于（相等于）查询区间的区间，以靠左、靠右的两条等宽区间，求得查询区间的最小值：

複杂度

建立时间为 O(NlogN)，建立空间为 O(NlogN)，计算任意区间最小值的时间是 O(1)。

Sequence 资料结构: Cartesian Tree

Cartesian Tree

http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/10-treaps.pdf

Cartesian Tree 是一种 Treap，根的数值小于左右子树，根的索引值介于左右子树。

以 online 方式建立，由左到右读取阵列元素，每读取一个元素，就建立一个节点。整棵树刚好依照 DFS 顺序来回遍历一次。通常使用 stack 实作，确保 stack 的元素依序排好。

All Nearest Smaller Values

http://en.wikipedia.org/wiki/All_nearest_smaller_values

±1 Range Minimum Query

RMQ 问题，以 O(N) 时间建立 Cartesian Tree，便化作 LCA 问题。

LCA 问题，以 O(N) 时间用 DFS 遍历，记下到访次序（作为索引值）、深度（作为元素值），便化作±1RMQ 问题。

±1RMQ 问题有著特殊的演算法，建立时间为 O(N)、查询时间为 O(1)，到达理论下限。然而±1RMQ 规则複杂，实务上效率极差，此处不介绍，请读者自行寻找资料。

RMQ 问题、LCA 问题、±1RMQ 问题的时间複杂度皆相等，而且到达理论下限。也就是说这三个问题已经被彻底解决了。

Sequence 资料结构: Quicksort Tree

Quicksort Tree【尚无正式名称】

http://yueyue1105.blog.163.com/blog/static/431117682010716111425892/

top-down 建立。以中位数作为 pivot，预先排序以求得中位数。

建立 O(NlogN)、修改 O(logN)、无法插入及删除、查询区间内第 k 名元素 O(logN)，查询区间内元素名次 O(logNlogN)。

Wavelet Tree

即是 Succinct Quicksort Tree。

http://alexbowe.com/wavelet-trees/

Sequence 资料结构: Mergesort Tree

Mergesort Tree【尚无正式名称】

http://yueyue1105.blog.163.com/blog/static/431117682010716111425892/

bottom-up 建立。

建立 O(NlogN)、修改 O(logN)、无法插入及删除、查询区间内第 k 名元素 O(logNlogN)，查询区间内元素名次 O(logNlogN)。