UNDER CONSTRUCTION.
本文总结经典的区间第k小值数据结构题。 给定一个长为n的数组。有m个询问：求区间[l,r)中第k小的元素。
一些方法支持扩展问题：有m个操作，或者修改某个位置上的元素，或者询问区间[l,r)中第k小的元素。
归并树(merge sort tree)
用O(n*log(n))时间构建线段树，每个节点存储对应区间的有序数组。 对于一个询问，二分搜索答案ans转化为计数问题：区间[l,r)内小于ans的元素个数是否大于等于k。 对于这个计数问题，把区间[l,r)解构为不超过log(n)个线段树节点。对于每个节点，二分查找这个节点存储的有序数组里小于ans的元素数。
- static:
O(n*log(n)+m*log(n)^3), space complexity:O(n*log(n)), not recommended
若要支持修改元素，把每个节点存储的有序数组改成一棵binary search tree，这种嵌套树形解构俗称树套树。
描述值域的线段树
用O(n*log(n))时间构建一棵线段树，每个节点描述一个值域区间，存储出现的元素的位置序列。 对于静态问题，位置序列可以是一个有序数组。若要支持修改元素，位置序列得是线段树或binary search tree。
询问使用的区间查询支持区间减法，因此外层的线段树也可改成Fenwick tree，减少一半节点。
- static:
O(n*log(n)+m*log(n)^2), space complexity:O(n*log(n)), not recommended
划分树(range tree with functional cascading)
这是描述值域的线段树的一种优化。用O(n*log(n))时间构建一个描述值域的线段树，每个节点存储值域区间里按顺序出现的元素数组，和一个辅助数组表示分到左孩子的元素个数。 对于一个询问，可以O(1)知道[l,r)中落在左孩子值域的元素个数，判断要在左孩子或在右孩子找答案。
- static:
O((n+m)*log(n)), space complexity:O(n*log(n))
整体二分(parallel binary search)
有多组修改和询问。每个询问会受到时间序之前的修改的影响，询问目标可以二分搜索。 这类算法将二分答案应用到多组修改和询问上。
在二分答案后，单点修改的影响为commutative monoid，区间询问的目标也是一个commutative monoid。
- static:
O((n+m)*log(n)^2), space complexity:O(n+m) - dynamic:
O((n+m)*log(n+m)*log(n)), space complexity:O(n+m)
1 |
|
1 | // parallel binary search, dynamic |
可持久化线段树(persistent segment tree)
用O(n*log(n))时间构建n+1棵描述值域的线段树。每棵线段树表示一个原数组的一个前缀(共n+1个)。在每棵线段树中，每个节点存储一个值域区间里的元素数。 相邻两棵线段树描述的区间只相差一个元素，它们可以共用大部分节点，只有ceil(log(n))个节点有差异。
- static:
O((n+m)*log(n)), space complexity:O(n*log(n)) - dynamic:
O((n+m)*log(n)^2)
1 | // persistent segment tree |
莫涛算法(Mo's algorithm)
- static:
O(n*log(n)+m*sqrt(n)+m*log(m)) - dynamic (binary search on the value, 二分答案):
O(n*log(n)+m*sqrt(n)*log(n)*log(n+m)) - dynamic (区间 [l,r] 内所有的 x 变成 y, P4119):
静态情形：维护两个频度数组，一个表示元素x的频度，另一个表示元素区间(如[i,i+block_size))的频度。区间长度加减一时，O(1)修改频度。 1
2c1[a[i]] += d;
c2[block[a[i]]] += d;
询问时O(sqrt(n))扫描频度数组得到答案。 1
2
3
4
5
6
7int x = 0, k = qs[i].k;
while (c2[x] < k) k -= c2[x++];
for (int j = x*block_size; ; j++)
if ((k -= c1[j]) <= 0) {
qs[i].ans = j;
break;
}
要点在于不要用有序数据结构维护区间内的元素，会不必要增大修改的时间复杂度。
要支持修改元素，可在每个分块里里维护一个有序数组。 修改时重建有序数组。 询问时二分答案ans。在包含的分块里二分搜索小于ans的元素数。在分块外线性遍历至多2*block_size个元素
1 | // Mo's algorithm |