区间问题常常是对某一个数组的指定区间进行查询、更改和维护某些属性。如果不采用高效算法的话每次的查询都将是遍历查询，而且如果要维护某个区间的属性的话那就更加的困难。这里对于区间问题主要采用的是树状数组、线段树和ST 表等方法来完成区间操作，还有一种思想比较简单的分块法和前缀和来处理区间数据。
树状结构处理
很多区间问题都可以利用树中子节点和父节点之间的关系来进行区间统计，那么如何使用树来处理数据呢？
树状数组
树状数组全称叫做二叉索引树，其是利用了一个特殊的 lowbit() 操作来处理不同区间的角标，来获得查询区间和还有单点修改的效果，有模板题 https://www.luogu.com.cn/problem/P3368 可以帮助理解。
查询区间和：$O(\log n)$
单点修改：$O(\log n)$
首先应该理解的是 lowbit() 操作，它的作用是将二进制下的某数除了其最后一个 $1$ 以外都置 $0$，利用这一个运算的特性我们可以知道树形结构中的 tree[p] 的父节点是 tree[p+lowbit(p)]。这样就可以通过角标的运算在数组构建出的树状结构中获取每一个子节点的父节点的角标，每一个区间的加和或者说是各种属性都可以在父节点中储存。
int lowbit(int val) { return val & -val; }
- 单点修改和初始化
修改数组中某个值，那么需要考虑到的是它自身的值的修改以及其父节点所代表的区间和的修改。这时采用 lowbit() 操作就可以在实现从下到上的爬树过程的同时更改所有包含该点的所有区间的“和”。
void Update(int pos, int val) {
for (int i = pos; i <= maxSize; i += lowbit(i)) {
// every interval that have this point add this value
tree[i] += val;
}
}
void Init() {
for (int i = 1; i <= maxSize; i++) {
Update(i, base[i]);
}
}
- 区间查询
利用二叉索引树的特性可以轻松在 $O(\log n)$ 复杂度下得到前 n 项和，两区间和相减就可以获得一个中间区间的区间和。当然对于区间的查询并不只是一维的，对于二维的树状数组应该如这道题 https://www.luogu.com.cn/problem/P4054 去做，这之中的查询为了避免过多的参数退化为了前缀和，所以结果应该去扣除非指定的区间和。
// Prefix subtract to get the sum of intervals.
int Query(int left, int right) {
int ans = 0;
for (int i = right; i != 0; i -= lowbit(i)) {
ans += tree[i];
}
for (int i = left; i != 0; i -= lowbit(i)) {
ans -= tree[i];
}
return ans;
}
有时候数据较大，需要去离散化才能存储在树状数组中，但做完 https://www.luogu.com.cn/problem/P2344 还是不太理解。
线段树
之前的树状数组只能实现 $O(\log n)$ 的单点修改和区间查询，而线段树则用更多的空间消耗来换取了二叉树支持下的区间修改的较低复杂度。
查询区间和：$O(\log n)$
单点修改和区间修改：$O(\log n)$
对于线段树来说应该要通过树状架构省略掉一些不必要的操作来保持较低的时间复杂度，所以说相当关键的就是它的 Lazy 的标记。虽然很多时候需要维护五花八门的运算，但是记住对于多个不同运算的标记，生效和下推的时候都应该遵循这些运算的运算顺序的诀窍就好。比如这一道题 https://www.luogu.com.cn/problem/P3373 运用到了线段树的区间乘法这时候就需要特殊标记了。还有的时候线段树需要经过一定的修改来维护不同的值如 https://acm.hdu.edu.cn/showproblem.php?pid=6992，这时要特别注意 Lazy 标记和 Push 操作，但其余的代码框架则具有通用性。
- 搭建线段树
这是一种典型的牺牲空间换取时间优势的结构，在耗费更短时间的同时相当的获得了查询和修改的优势。由于二叉树的性质，维护这一结构的数组要是原数组四倍。即便如此，花费常数倍的空间换来了对数级的时间优化，还是挺划算的。
void Build(int left, int right, int pos) {
if (left == right) {
// leaf node of line segment tree is value of original array
tree[pos] = base[left];
} else {
int mid = (left + right) / 2;
// recursively build left and right subtrees
Build(left, mid, pos * 2);
Build(mid + 1, right, pos * 2 + 1);
tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
}
}
如何进行下推是解决相关问题的关键
对于线段树来说最难理解和最难操作的是这个 Push 的下推操作，它将存在当前节点但却没有实效在以下节点的 Lazy 推向子节点来让修改运算对区间的影响真正生效。
void Push(int left, int right, int pos) {
// push lazy tag down
lazy[pos * 2] = lazy[pos * 2] + lazy[pos];
lazy[pos * 2 + 1] = lazy[pos * 2 + 1] + lazy[pos];
int len = right - left + 1;
// lazy tag apply on node
tree[pos * 2] += lazy[pos] * (len - len / 2);
tree[pos * 2 + 1] += lazy[pos] * (len / 2);
// clear tag in current node
lazy[pos] = 0;
}
以上的只是加法区间修改，真实的情况并没有那么简单，不同的修改运算对应的是不同的标记方法和下推。有一道题 https://www.luogu.com.cn/problem/P2574 是每次异或某区间的值，那么每次都将该区间的 0 变成 1 原来的 1 都变成 0，对于区间的和来说就是长度减去原来这个区间的值也就是值的反转。
- 查询和修改
查询和修改的代码基本相同，因为他们的逻辑也是相似的，都是递归查看区间是否完全包含在所查询的区间内，至于剩余的不在大区间内的单个的节点也会在最后的时候由叶子节点的值直接代表并递归传递。还有的情况需要总结规律比如这道题前缀和嵌套前缀和 https://www.luogu.com.cn/problem/P4868 就很有意思。
void Update(int left, int right, int curLeft, int curRight, int pos, int val) {
if (curRight < left || curLeft > right) {
return;
} else if (left <= curLeft && curRight <= right) {
int len = curRight - curLeft + 1;
tree[pos] += len * val;
// If it is not the leaf node, then first mark the impact on the child node
// and calculate it when it is used later, instead of directly calculating.
if (curLeft != curRight) {
lazy[pos] += val;
}
} else {
// If the current interval is not completely within the modification
// interval, then the interval needs to be subdivided.
int mid = (curLeft + curRight) / 2;
Push(curLeft, curRight, pos);
Update(left, right, curLeft, mid, pos * 2, val);
Update(left, right, mid + 1, curRight, pos * 2 + 1, val);
tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
}
}
int Query(int left, int right, int curLeft, int curRight, int pos) {
if (curRight < left || curLeft > right) {
return 0;
} else if (left <= curLeft && curRight <= right) {
// return sum of completely contained interval
return tree[pos];
} else {
// push down marked interval and divide it to continue searching
int mid = (curLeft + curRight) / 2;
Push(curLeft, curRight, pos);
return Query(left, right, curLeft, mid, pos * 2) + Query(left, right, mid + 1, curRight, pos * 2 + 1);
}
}
理论上所有用树状数组解决的问题都可以用线段树来解决，比如这题 https://www.luogu.com.cn/problem/P3374 完全可以用线段树来做，但是为了快速给出答案和节省空间一般采用树状数组就可以满足题中的条件了。
分块处理
有时候可以把区间直接无脑分成各个块也可以对区间问题的时间复杂度一定程度上的优化，最重要的是分块的方法可以维护更丰富的区间属性比如这个题 https://www.luogu.com.cn/problem/P2801 通过对分块的排序来维护块中元素超过某一数值的性质。但是分块的区间和和区间修改的时间复杂度都是 $O(\sqrt{n})$，这就需要在维护属性和时间复杂度之间取舍了。
绝大多数分块就是将区间分成 $\sqrt{n}$ 个区间，其中最多包含 $\sqrt{n}$ 个元素。前几个分块都是满的，最后一个分块可能会有点不同而已。
| 数组 | 作用 |
|---|---|
| belong | 记录元素属于哪一个分块 |
| st/ed | 记录每个区间的开始和结束 |
- 建立分块
建立分块就是获得分块的大小、标记区间开始结束和设置元素的归属几个步骤。有时候还可以直接使用标准库中的 vector 来进行分块也很方便，分块很多时候是兜底的区间问题解法。
void Init() {
int perSize = sqrt(n);
nums = n / perSize;
// If there are rest elements, they are divided into independent blocks to
// be cauculate.
if (n > perSize * nums) {
nums++;
}
// divide beginning and end of an interval
for (int i = 1; i <= nums; i++) {
st[i] = (i - 1) * perSize + 1;
ed[i] = i * perSize;
if (i == nums) {
ed[i] = n;
}
}
// set attribution of each interval element
for (int i = 1; i <= nums; i++) {
for (int j = st[i]; j <= ed[i]; j++) {
belong[j] = i;
}
}
// record size of these blocks
for (int i = 1; i <= nums; i++) {
size[i] = ed[i] - st[i] + 1;
}
// initializes interval sum of blocks
for (int i = 1; i <= nums; i++) {
for (int j = st[i]; j <= ed[i]; j++) {
block[i] += base[j];
}
}
}
- 区间修改查询
同线段树和一样，区间的查询还是在不断的细分区间直到符合分块的范围来快速的获取值或者修改值。也是同样的，分块也可以采用 Lazy 标记的办法节省一部分的不必要操作。
分块中的
Lazy要方便的多，因为分块只有两层
void Update(int left, int right, int val) {
if (belong[left] == belong[right]) {
for (int i = left; i <= right; i++) {
base[i] += val;
block[belong[i]] += val;
}
} else {
// change both ends, complete block can be marked with lazy
for (int i = left; i <= ed[belong[left]]; i++) {
base[i] += val;
block[belong[i]] += val;
}
for (int i = st[right]; i <= right; i++) {
base[i] += val;
block[belong[i]] += val;
}
for (int i = belong[left] + 1; i <= belong[right] - 1; i++) {
lazy[i] += val;
}
}
}
int Query(int left, int right) {
int ans = 0;
// Don't forget to validate the lazy tag during the query and modify it to
// the correct value.
if (belong[left] == belong[right]) {
for (int i = left; i <= right; i++) {
ans += base[i] + lazy[belong[i]];
}
} else {
for (int i = left; i <= ed[belong[left]]; i++) {
ans += base[i] + lazy[belong[i]];
}
for (int i = st[right]; i <= right; i++) {
ans += base[i] + lazy[belong[i]];
}
for (int i = belong[left] + 1; i <= belong[right] - 1; i++) {
ans += block[i] + lazy[i] * size[i];
}
}
}
通过 DP 预加载
由上面的代码可以看出，一个数组首先要经过很多处理才能够被快捷的操作，这也是这些数据结构存在的意义。可能预操作要花费一定的时间，但是却可以带来之后所有操作的效率提升还是值得的。
浅析 ST 表
这种表实际上还是采用了一定的动态规划的思想来预处理数据，模板题 https://www.luogu.com.cn/problem/P3865 中ST 表在 $O(n\log n)$ 的预处理复杂度的情况下获得对于区间 RMQ 问题即区间最大最小值问题查询的 $O(1)$ 的查询速度。
首先应该说明的是这个表每一项所代表的意义，只有理解了之后才能够变通的将它运用在各种情况上。其中 st[i][j] 表示在 $i$ 位置开始到 $i+2^{j}$ 的元素中的最大值，所以可以每次把区间分成两个区间并且分别求取最大值或者是其他维护的属性。通过实践发现，表中可以维护很多的区间内属性，比如这一道题 https://codeforces.com/contest/1549/problem/D 维护的是区间内所有元素的 GCD，在通过 $O(n\log n)$ 的预处理后就可以实现对区间内所维护值的 $O(1)$ 查询。
- 初始化
根据表的定义来通过倍增的思想去预加载当前数组的查询表，表中的 st[i][0] 是原数组中的第 i 个数据，初始化时的边界和倍增时角标的含义有关。
void Init() {
for (int i = 1; i <= n; i++) {
st[i][0] = base[i];
}
for (int j = 1; j <= 22; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
// state transition
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
RMQ查询
通过预加载之后的查询复杂度是恐怖的 $O(1)$，过程中需要用到 log2() 函数取整后获取角标。
int Query(int left, int right) {
int pos = log2(right - left + 1);
return max(st[left][pos], st[right - (1 << pos) + 1][pos]);
}
这种表可以用来处理区间的最大最小值问题，但也有其他变形。比如最大字符串的题 https://www.luogu.com.cn/problem/P2412 和查询角标的题 https://www.luogu.com.cn/problem/P2311。这些有的是需要在状态转移的时候采取不同的比较函数，有的是需要改变 ST 表中存储的值。很多时候 ST 表中维护的值类型取决于它的倍增 DP 运算的种类，需要更改的只有初始化和查询中的倍增计算行的运算就可以维护一些除最大最小值以外的值。
算法的工程意义
在打 ACM 竞赛的时候不是很理解区间和分块算法的实际用途，近来发现这些东西都是分布式计算中最巧妙的部分。通过这些算法我们可以把很多计算转化为树上计算，而树上计算的每个节点又可以是一个实例的独立计算资源。通过递归或者递推的方式将问题拆解，能够在众多节点中按照一定规则 Map Reduce 得出最终结果，正是一种分布式计算的思想。对于分块这种算法来说，很粗暴但是确实一定程度降低了复杂度，也是一种分而治之的思想。