C语言差分数组实现区间修改和单点查询

在算法竞赛和实际应用中，我们经常需要对数组进行区间修改和单点查询操作。例如，给定一个数组，要求将区间 [l, h] 内的每个元素都加上一个值 s，然后查询某个位置的元素值。

如果采用朴素的遍历方法，每次区间修改的时间复杂度为 O(n)，其中 n 为数组长度。当修改操作频繁时，效率会非常低下。为了提高效率，我们可以使用差分数组来优化操作。

什么是差分数组？

差分数组是一个与原数组等长的辅助数组，用于记录原数组相邻元素之间的差值。具体来说，对于原数组 a[1], a[2], ..., a[n]，其对应的差分数组 b[1], b[2], ..., b[n] 定义如下：

b[1] = a[1]
b[i] = a[i] - a[i-1]  (2 <= i <= n)

如何利用差分数组进行区间修改和单点查询？

区间修改: 要将区间 [l, h] 内的每个元素都加上 s，只需要对差分数组进行如下操作：

b[l] += s b[h+1] -= s

   这是因为，b[l] 的增加会导致 a[l] 及其之后的元素都增加 s，而 b[h+1] 的减少则会抵消 a[h+1] 及其之后的元素的增加，从而实现了只对区间 [l, h] 内元素进行修改的效果。

2. **单点查询:**
   要查询位置 i 的元素值，可以使用如下公式：

a[i] = b[1] + b[2] + ... + b[i]

   这是因为，根据差分数组的定义，a[i] 可以表示为 a[1] 加上 a[1] 到 a[i] 之间的差值之和。

### 代码示例

以下是使用C语言实现差分数组的代码示例：

```c
#include <stdio.h>

int main()
{
    int n, m;
    int i;
    const int N = 1000100;
    int a[N], b[N], c[N];
    scanf('%d %d', &n, &m);
    for (i = 1; i <= n; i++) {
        scanf('%d', &a[i]);
    }
    // 初始化差分数组
    for (i = 1; i <= n; i++) {
        b[i] = a[i] - a[i - 1];
    }
    // 处理 m 次区间修改操作
    while (m--) {
        int l, h, s;
        scanf('%d %d %d', &l, &h, &s);
        b[l] += s;
        b[h + 1] -= s;
    }
    // 计算原数组的值
    for (i = 1; i <= n; i++) {
        c[i] = c[i - 1] + b[i];
        printf('%d ', c[i]);
    }
    return 0;
}

总结

使用差分数组可以将区间修改操作的时间复杂度降低到 O(1)，而单点查询的时间复杂度仍然保持在 O(1)。这使得差分数组成为处理区间修改和单点查询问题的有效工具。