0. 前言

本文介绍值域分块技术，这是一种高效处理集合操作的数据结构方法。在处理带修改莫队算法时，传统的树套树结构可能无法满足时间复杂度要求，而值域分块提供了一种更高效的解决方案。

本文假设读者已掌握莫队算法和序列分块的基础知识。

1. 基本概念

简介

分块本质上是一种算法技巧。以维护序列信息为例，我们将整个数列划分为√n个块，在修改和查询时可以直接利用整块的信息，避免逐个元素的暴力操作，从而保证时间复杂度。

这是对数列进行分块，称为数列分块。而对值域进行分块的技巧，则被称为值域分块。

值域分块维护的是一个集合，需要满足集合内的数据都能映射到一个值域，并且能够反映元素间的大小关系。最常用的方法是配合离散化使用。

值域分块可以实现O(1)的插入、删除操作，O(√n)的查询全局排名、查询第k大元素、查询前驱和后继等操作——在特定条件下，它可以作为平衡树的替代方案，甚至在某些方面优于平衡树。

核心思想

在数列分块中，每个位置维护的是数列上的数值。而在值域分块中，我们维护的是每个值出现的次数！

类比桶排序，我们用count[x]代表当前集合T中x的出现次数。对序列count进行分块，额外维护每个块内（即在某个值域范围内）的所有数的出现次数总和，记为block_count[i]。

显然有∑count=∑block_count=|T|。

此外，记块长为size，belong[i]为值i所处的块编号，first[i]为编号为i的块的第一个值。

2. 基本操作

插入/删除操作

插入或删除一个值为x的数，只需将count[x]和block_count[belong[x]]自增或自减1。

时间复杂度为O(1)。

查询排名操作

对于值为x的数，求出有多少个数比x小，并将结果加1，就是x的排名。

我们只需累计所有小于x的数的出现次数即可。对于整块，优先累加整块，直到x所在的前一块，然后再累加单个值。

公式为：rank(x) = ∑(i=1到belong[x]-1)block_count[i] + ∑(i=first[belong[x]]到x-1)count[i]

该操作的时间复杂度为O(n/size + size)。

查询第k大元素

求出排名为x的数是多少。在出现次数总和不大于x的情况下，累加整块的出现次数，然后继续累加单个值的次数，直到出现次数大于x。

此时的值就是排名为x的数。

时间复杂度为O(n/size + size)。

查询前驱

求x的前驱，即小于x且最大的数。我们可以先利用查询排名操作求出x的排名rank。

rank代表有rank-1个数小于x，那么小于x的最大数自然就是排名为rank-1的数。

因此，getpre(x) = getkth(getrank(x)-1)。

时间复杂度为O(n/size + size)。

查询后继

求x的后继，即大于x且最小的数。类比查询前驱，要求大于x的数，需要先知道小于等于x的数有多少个。

记rank = getrank(x+1)，代表有rank-1个数小于x+1，也就是小于等于x。那么第一个大于x的数自然就是排名为rank的数，即getkth(rank)。

因此，getnxt(x) = getkth(getrank(x+1))。

时间复杂度为O(n/size + size)。

3. 时间复杂度分析

前面的操作，除了插入和删除，块长的取值对这两个操作的复杂度没有影响，所有操作的复杂度都是O(n/size + size)。

根据基本不等式，有n/size + size ≥ √(n/size × size)。

因此，当且仅当n/size = size = √n时，时间复杂度取到最小值O(√n)。

4. 代码实现

初始化

int block_size = max((int)sqrt(n), 1);
for(int i = 1; i <= n; i++) {
  block_id[i] = (i - 1) / block_size + 1;
  if(!first_value[block_id[i]]) first_value[block_id[i]] = i;
}

插入/删除操作

void insert(int v) {
  count[v]++;
  block_count[block_id[v]]++;
}

void remove(int v) {
  count[v]--;
  block_count[block_id[v]]--;
}

查询排名

int query_rank(int v) {
  int rank = 1;
  for(int i = 1; i < block_id[v]; i++) rank += block_count[i];
  for(int i = first_value[block_id[v]]; i < v; i++) rank += count[i];
  return rank;
}

查询第k大元素

int query_kth(int rank) {
  int current_sum = 0, current_block = 1;
  while(block_count[current_block] + current_sum < rank) 
    current_sum += block_count[current_block++];
  int current_pos = first_value[current_block];
  while(count[current_pos] + current_sum < rank) 
    current_sum += count[current_pos++];
  return current_pos;
}

查询前驱/后继

int get_predecessor(int v) {
  return query_kth(query_rank(v) - 1);
}

int get_successor(int v) {
  return query_kth(query_rank(v + 1));
}

5. 边界情况处理

一个数的前驱和后继可能不存在。这种情况可能导致查询出现问题。常用的解决方案是将正无穷和负无穷也加入离散化，并在初始化时提前将这两个数插入集合。

这样，当前驱或后继不存在时，返回的就是负无穷或正无穷，再在后续程序中特殊处理。

6. 实例应用

平衡树模板题

值域分块可以作为平衡树的替代方案，实现插入、删除、查询排名、查询第k大、查询前驱和后继等操作。

实现时需要注意输入输出数据的离散化处理，以及边界条件的处理。

树套树模板题

当使用带修改莫队算法时，如果套用传统的树套树结构，时间复杂度可能无法满足要求。而使用值域分块，可以将修改复杂度降至O(1)，查询复杂度为O(√n)，总复杂度变为O(n^(5/3) + n√n)。

这种用更高的查询复杂度换取更低的修改复杂度的方法，称为根号平衡。在修改次数远多于查询次数的情况下，这种方法特别有效。

7. 其他应用

值域分块还可以用于解决其他问题，如查询mex问题、处理作业问题等。根据具体问题，可能需要对值域分块进行适当的变形和优化。

8. 总结

值域分块是一种强大的算法技巧，通过合理划分值域，可以在保证一定时间复杂度的前提下，高效地处理各种集合操作问题。

分块思想具有广泛的应用价值，不仅限于对序列和值域的分块，还可以对查询进行分块，应用场景灵活多变。

掌握值域分块技术，对于解决各类数据结构问题具有重要意义。