本文对区间查询问题常用的数据结构方法进行总结
1. 前缀和
前缀和是降低区间查询问题复杂度的一种常见预处理方法，对数组a进行前缀和初始化需要O(n)时间：新建数组b，将数组a的累加依次放入数组b中
b[0] = a[0]
b[i] = b[i-1] + a[i]
- 使用前缀和可在O(1)时间计算区间和：
由通项公式可得sum[i, j] = b[j] - b[i-1]
- 但前缀和单点修改：
void modify(int pos, int d) {
for (int i = pos; i <=n; ++i) {
b[i] += d;
}
}
时间复杂度为O(n)，即前缀和不支持单点修改和区间修改
二维/多维前缀和
前缀和基于容斥原理，下面以二维前缀和为例说明前缀和扩展到多维的方式。
例如一个二维数组
1 2 4 3
5 1 2 4
6 3 5 9
前缀和矩阵即
1 3 7 10
6 9 15 22
12 18 29 45
二维前缀和的初始化即递推求
- 使用二维前缀数组可在O(1)时间求左上(x1,y1) - 右下(x2,y2) 子矩阵的和：
同理即
树上前缀和
设 表示结点
到根节点的权值总和。
若是点权， 路径上的和为
；
若是边权， 路径上的和为
。
LCA 最近公共祖先
2. 差分
差分可看作前缀和的逆操作 对原数组a求差分数组b，则a也是b的前缀和数组。
b[1] = a[1]
b[i] = a[i] - a[i-1]
则
a[i] = b[1] + b[2] + ... + b[i]
=a[1] + a[2] - a[1] +...+ a[i] - a[i-1] = a[i]
差分数列不能提供O(1)时间的区间和查询，但可以提供O(1)时间的单点修改和区间修改， 例如对区间[l, r]内所有的数都加d只需
void add (int l, int r, int d) {
b[l] += d;
b[r+1] -= d;
}
则原数组 a[1]...a[l-1]间的数均无影响，a[l]...a[r]间的数均增加d，a[r+1]后的数又抵消不变。
适用于区间修改、单点查询类问题
- 差分例题：
- 差分+贪心
求区间内所有值通过区间加1/减1全部相等的最小变换次数 - 差分+前缀和
满足互相看见约束的序列各位置的最高可能高度
树上差分
基于子树和而非节点到根的和
如果使 路径上的点权增加
，
如果是边权
3. 倍增法 ST表
定义：倍增是指在状态空间很大线性递推无法满足要求时，成倍增长只递推状态空间中在2的整数次幂位置上的值，其他值由于任意整数可表示为若干2的次幂项的和可以由上述代表值拼加而成。
应用：
- 快速幂基于倍增和二进制划分的思想
- RMQ（Range Maximum/Minimum Query）问题，解决RMQ主要方法即ST表和线段树。ST表基于倍增思想，可以通过O(nlogn)时间预处理，以O(1)时间解决每次重复区间对结果无影响的区间查询问题，例如区间最大值最小值，但不支持修改操作
- LCA问题
4. 树状数组
树状数组是支持区间单点修改的前缀和。不同于前缀和，树状数组求原数组2的幂次长度的和，即前1个，前2个，前4个和前8个的和，但这样我们无法求出[3,3]区间和[5.8]区间的子区间的和，因此我们需要对[5,8]区间也按照2的幂的长度划分即[5], [5,6], [5,6,7,8]，类似[3,3]我们仍无法求[7,7]，因此补上{3}和{7}，如下图所示：
由于所有的区间长度都是2的幂次，即1,10,100,1000
将上图所有区间从左至右按序排列，其区间长度的二进制表示为：
1,10,1, 100, 1, 10, 1, 1000
而图中区间标号对应的二进制表示为：
1,10,11,100,101,110,111,1000
可以发现区间长度即区间标号二进制表示从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数，用lowbit函数将区间标号映射为区间长度：
int lowbit (int x) {
return x & (-x);
}
- 单点修改操作需要更新所有包含它的区间，时间复杂度O(log n)：
void modify(int pos, int d) {
while(pos <= n) {
b[pos] += d;
pos += lowbit(pos);
}
}
- 区间和
// a[1]...a[x]
int presum(int x) {
int ans = 0;
while(x >= 1) {
ans += b[x];
x -= lowbit(x);
}
}
// a[i]...a[j]
int sum(int i, int j)
return presum(j) - presum(i-1);
扩展：
- 使用差分转换 树状数组也可以支持区间修改、单点查询或区间修改、区间查询
-
二维树状数组
BIT例题：
5. 线段树
线段树能解决综合上述所有需求的区间问题。
6. 莫队算法
用于离线区间
