区间加与单点查询

1 问题模型

给定数组 a1,…,ana_1,\ldots,a_n,交替执行:

  • 区间加:将 [l,r][l,r] 内每个数增加 vv。
  • 单点查询:查询当前 axa_x。

树状数组基础 支持单点修改。若逐个修改区间内的元素,一次区间加最坏仍需 O(nlog⁡n)O(n\log n)。

差分 能把区间加变成两个边界的修改。将它交给树状数组维护,就能处理修改与查询交替出现的情况。

2 维护差分

令 a0=0a_0=0,定义:

di=ai−ai−1,ax=∑i=1xdi. d_i=a_i-a_{i-1},\qquad a_x=\sum_{i=1}^{x}d_i.

给 [l,r][l,r] 加上 vv 后:

  • dld_l 增加 vv,因为 ala_l 改变而 al−1a_{l-1} 不变。
  • 对 l<i≤rl<i\le r,相邻两项都增加 vv,差值不变。
  • 若 r<nr<n,dr+1d_{r+1} 减少 vv,因为 ara_r 增加而 ar+1a_{r+1} 不变。

因此,只需:

dl+=v,dr+1−=v. d_l\mathrel{+}=v,\qquad d_{r+1}\mathrel{-}=v.

第二处边界超出数组时可以忽略。

例如 a=[2,−1,3,4,5]a=[2,-1,3,4,5],对 [2,4][2,4] 加 33。原数组有三项改变,差分只有两项改变。

对原数组区间 2 到 4 加 3,差分仅在位置 2 加 3、位置 5 减 3

树状数组的底层对象变成 dd,所以其节点含义为:

c[i]=∑j=i−lowbit⁡(i)+1idj. c[i]=\sum_{j=i-\operatorname{lowbit}(i)+1}^{i}d_j.

同一个 sum(x) 接口,现在求的是差分前缀和,因此结果是原数组单点值 axa_x。 它不再表示原数组的前缀和。

3 操作实现

3.1 初始化

读入数组时,用相邻两项之差初始化树状数组:

long long previous = 0;
for (int i = 1; i <= n; ++i) {
    long long value;
    cin >> value;
    add(i, value - previous);
    previous = value;
}

不能直接执行 add(i, value),否则维护的仍是原数组。

3.2 区间加

void range_add(int l, int r, long long v) {
    add(l, v);
    if (r < n) add(r + 1, -v);
}

第一处修改让所有 x≥lx\ge l 的差分前缀和增加 vv;第二处从 r+1r+1 开始抵消这个增量。因此只有 l≤x≤rl\le x\le r 的值改变。

3.3 单点查询

long long point_query(int x) {
    return sum(x);
}

初始化后,树状数组保存正确的差分。每次区间加恰好修改两个差分边界,继续保持该含义;单点查询再由差分前缀和恢复 axa_x,所以整个过程正确。

4 代码实现

输入输出采用 luogu P3368: 【模板】树状数组 2 的格式:

  • 第一行 n,mn,m,第二行为初始数组。
  • 1 l r v:区间加。
  • 2 x:查询当前位置的值。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 500000 + 5;
int n, m;
long long c[maxn];

int lowbit(int x) { return x & -x; }

void add(int p, long long v) {
    for (int i = p; i <= n; i += lowbit(i)) c[i] += v;
}

long long sum(int x) {
    long long res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) res += c[i];
    return res;
}

void range_add(int l, int r, long long v) {
    add(l, v);
    if (r < n) add(r + 1, -v);
}

long long point_query(int x) { return sum(x); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    long long previous = 0;
    for (int i = 1; i <= n; ++i) {
        long long value;
        cin >> value;
        add(i, value - previous);
        previous = value;
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            long long v;
            cin >> l >> r >> v;
            range_add(l, r, v);
        } else {
            int x;
            cin >> x;
            cout << point_query(x) << '\n';
        }
    }
    return 0;
}

初始化为 O(nlog⁡n)O(n\log n),一次区间加至多进行两次单点修改,一次查询进行一次前缀查询,均为 O(log⁡n)O(\log n)。有效存储为 O(n)O(n),定长数组按 maxn 预留容量。

4.1 示例

输入:
5 5
2 -1 3 4 5
2 2
1 2 4 3
2 2
2 5
2 4

输出:
-1
2
5
7

修改后数组为 [2,2,6,7,5][2,2,6,7,5]。位置 55 不在修改区间内,其值仍为 55。

5 边界

  • l=1l=1 时正常修改 d1d_1,不能使用下标 00 更新树状数组。
  • r=nr=n 时跳过 r+1r+1,不需要额外存储这一项差分。
  • 区间长度为 11、增量为负数时,公式仍然成立。
  • 原值、差分、增量和累计值均使用 long long,并保证中间结果在其范围内。
  • sum(r)-sum(l-1) 现在求的是 dl+⋯+dr=ar−al−1d_l+\cdots+d_r=a_r-a_{l-1},不能用来求原数组的区间和。

6 练习

完成 luogu P3368: 【模板】树状数组 2,再检查以下操作:

初始数组为 [1,2,3][1,2,3],先给 [1,3][1,3] 加 22,再给 [3,3][3,3] 加 −5-5。写出最终数组和差分数组。

参考结果

最终数组为 [3,4,0][3,4,0],差分为 [3,1,−4][3,1,-4]。第一次修改只改变有效范围内的 d1d_1;第二次修改只改变有效范围内的 d3d_3。

下一篇:区间加与区间求和,进一步恢复原数组的前缀和。

7 相关题解

暂无相关题解