树状数组区间修改（2026.3.22）

本文章将从一维到二维讲解树状数组如何实现区间修改 + 区间查询。

一维树状数组本身原生只支持“单点修改 + 区间查询”。

要实现区间修改 + 区间查询，必须引入 差分（Difference Array） 的思想。

---

一维：区间修改 + 区间查询

如果你需要给区间 $[l, r]$ 加上 $v$，并且查询区间 $[l, r]$ 的和，需要维护两个树状数组。

核心推导

我们要查询原数组 $a$ 的前缀和 $S[x] = \sum_{i=1}^x a[i]$。
已知 $a[i] = \sum_{j=1}^i d[j]$（$d$ 是差分数组）。

代入展开 $S[x]$：

$$\begin{aligned} S[x] &= \sum_{i=1}^x \sum_{j=1}^i d[j] \\ &= \sum_{i=1}^x d[i] \times (x - i + 1) \quad \text{(统计每个 } d[i] \text{ 被加了多少次)} \\ &= (x+1) \sum_{i=1}^x d[i] - \sum_{i=1}^x (d[i] \times i) \end{aligned}$$

结论：
要计算 $S[x]$，我们需要维护两个前缀和：

1. $\sum d[i]$
2. $\sum (d[i] \times i)$

因此，我们需要两个树状数组：

• bit1：维护 $d[i]$
• bit2：维护 $d[i] \times i$

操作逻辑

1. 区间修改 $[l, r]$ 加 $v$：

   • 对 $d[l]$ 加 $v$，对 $d[r+1]$ 减 $v$。
   • 同时更新 bit1 和 bit2：
     • bit1 在 $l$ 加 $v$，在 $r+1$ 减 $v$。
     • bit2 在 $l$ 加 $v \times l$，在 $r+1$ 减 $v \times (r+1)$。

2. 前缀和查询 $S[x]$：

   • 公式：query1(x) * (x + 1) - query2(x)

3. 区间和查询 $[l, r]$：

   • S[r] - S[l-1]

完整代码模板

// https://www.luogu.com.cn/problem/P3372
#include <bits/stdc++.h>
#define int long long

class BIT {
public:
    BIT(std::vector<int>& a) : tr(a), n(a.size()) {
        for (int i = 1; i < n; i++) {
            int j = i + (i & -i);
            if (j < n) tr[j] += tr[i];
        }
    }

    void update(int x, const int v) {
        for (; x < n; x += x & -x) {
            tr[x] += v;
        }
    }

    [[nodiscard]] int query(int x) const {
        int res = 0;
        for (; x; x -= x & -x) {
            res += tr[x];
        }
        return res;
    }

    [[nodiscard]] int query(const int l, const int r) const {
        return query(r) - query(l - 1);
    }
private:
    std::vector<int> tr;
    size_t n;
};

signed main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = n; i >= 1; i--) a[i] -= a[i - 1];
    BIT tr1(a);
    for (int i = 1; i <= n; i++) a[i] = a[i] * i;
    BIT tr2(a);
    while (m--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int x, y, k;
            std::cin >> x >> y >> k;
            tr1.update(x, k), tr1.update(y + 1, -k);
            tr2.update(x, k * x), tr2.update(y + 1, -k * (y + 1));
        } else {
            int x, y;
            std::cin >> x >> y;
            std::cout << (y + 1) * tr1.query(y) - tr2.query(y) - (x * tr1.query(x - 1) - tr2.query(x - 1)) << "\n";
        }
    }
    return 0;
}

---

二维：区间修改 + 区间查询

下面是二维树状数组实现区间修改、区间查询的完整数学推导过程。

1. 基础定义

设原二维数组为 $a[i][j]$。
我们要支持的操作是：给矩形区域 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的所有元素加上 $v$。
为了利用树状数组，我们引入二维差分数组 $d[i][j]$。

差分定义：

$$a[x][y] = \sum_{i=1}^{x} \sum_{j=1}^{y} d[i][j]$$

(即：原数组的值等于差分数组的二维前缀和)

差分更新逻辑：
若要将 $a$ 中矩形 $(x_1, y_1) \sim (x_2, y_2)$ 加 $v$，只需对 $d$ 进行四次单点修改：

1. $d[x_1][y_1] \ += v$
2. $d[x_1][y_2+1] \ -= v$
3. $d[x_2+1][y_1] \ -= v$
4. $d[x_2+1][y_2+1] \ += v$

---

2. 目标推导

我们的目标是求原数组 $a$ 的二维前缀和 $S(x, y)$：

$$S(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} a[i][j]$$

将 $a[i][j]$ 用差分 $d$ 替换：

$$S(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} \left( \sum_{p=1}^{i} \sum_{q=1}^{j} d[p][q] \right)$$

第一步：交换求和顺序（统计贡献次数）

现在的式子是四层循环。我们需要思考：每一个差分项 $d[p][q]$ 在这个大求和中被计算了多少次？

• $d[p][q]$ 会被计入 $a[i][j]$ 的条件是：$p \le i$ 且 $q \le j$。
• 在外层求和 $\sum_{i=1}^x \sum_{j=1}^y$ 中，满足 $i \ge p$ 的 $i$ 有 $(x - p + 1)$ 个（即 $p, p+1, \dots, x$）。
• 同理，满足 $j \ge q$ 的 $j$ 有 $(y - q + 1)$ 个。

因此，$d[p][q]$ 总共被累加了 $(x - p + 1) \times (y - q + 1)$ 次。

公式重写为：

$$S(x, y) = \sum_{p=1}^{x} \sum_{q=1}^{y} d[p][q] \times (x - p + 1) \times (y - q + 1)$$

(注：为了代码习惯，下文将求和变量 $p, q$ 换回 $i, j$)

$$S(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} d[i][j] \times (x - i + 1) \times (y - j + 1)$$

第二步：展开多项式

将系数 $(x - i + 1)(y - j + 1)$ 展开：

$$(x - i + 1)(y - j + 1) = [(x+1) - i] \cdot [(y+1) - j]$$

$$= (x+1)(y+1) - (x+1)j - (y+1)i + i \cdot j$$

将这个展开式代回 $S(x, y)$ 的求和公式中：

$$\begin{aligned} S(x, y) = \sum_{i=1}^{x} \sum_{j=1}^{y} d[i][j] \cdot \Big[ & (x+1)(y+1) \\ & - (x+1)j \\ & - (y+1)i \\ & + i \cdot j \Big] \end{aligned}$$

第三步：拆分求和项

利用求和的线性性质，将上式拆分为四部分。注意 $(x+1)$ 和 $(y+1)$ 对于内部的 $i, j$ 求和来说是常数，可以提取到求和符号外面。

$$\begin{aligned} S(x, y) = \quad & (x+1)(y+1) \sum_{i=1}^{x} \sum_{j=1}^{y} d[i][j] \\ & - (x+1) \sum_{i=1}^{x} \sum_{j=1}^{y} (d[i][j] \cdot j) \\ & - (y+1) \sum_{i=1}^{x} \sum_{j=1}^{y} (d[i][j] \cdot i) \\ & + \sum_{i=1}^{x} \sum_{j=1}^{y} (d[i][j] \cdot i \cdot j) \end{aligned}$$

---

3. 最终结论与数据结构设计

观察上面的四项，每一部分都是一个二维前缀和的形式。我们需要维护四个不同的二维树状数组（BIT），分别存储以下内容：

序号	树状数组名称	存储内容 (Value at $i, j$)	对应求和项
1	bit0	$d[i][j]$	$\sum \sum d[i][j]$
2	bit1	$d[i][j] \cdot i$	$\sum \sum (d[i][j] \cdot i)$
3	bit2	$d[i][j] \cdot j$	$\sum \sum (d[i][j] \cdot j)$
4	bit3	$d[i][j] \cdot i \cdot j$	$\sum \sum (d[i][j] \cdot i \cdot j)$

(注：代码实现中 bit1 和 bit2 的顺序可以互换，只要公式对应即可。上文代码中 bit1 对应乘 $i$，bit2 对应乘 $j$)

最终计算公式

设 $Q_k(x, y)$ 为第 $k$ 个树状数组的前缀和查询结果，则：

$$S(x, y) = (x+1)(y+1)Q_0(x,y) - (y+1)Q_1(x,y) - (x+1)Q_2(x,y) + Q_3(x,y)$$

其中：

• $Q_0(x,y) = \text{query}(\text{bit0}, x, y)$
• $Q_1(x,y) = \text{query}(\text{bit1}, x, y)$ （存的是 $d \cdot i$）
• $Q_2(x,y) = \text{query}(\text{bit2}, x, y)$ （存的是 $d \cdot j$）
• $Q_3(x,y) = \text{query}(\text{bit3}, x, y)$ （存的是 $d \cdot i \cdot j$）

区间修改时的更新操作

当我们要对差分数组 $d[x][y]$ 加上 $v$ 时，需要同步更新这四个树状数组：

1. bit0.update(x, y, v)
2. bit1.update(x, y, v * x)
3. bit2.update(x, y, v * y)
4. bit3.update(x, y, v * x * y)

4. 完整代码模板

// https://www.luogu.com.cn/problem/P4514
#include <bits/stdc++.h>
#define int long long

class BIT {
public:
    // 本题初始数组就是全0，所以不需要在构造函数中建树
    explicit BIT(const std::vector<std::vector<int>>& a) : tr(a), n(a.size()), m(a[0].size()) { }

    void update(int x, int y, const int v) {
        for (; x < n; x += x & -x) {
            for (int j = y; j < m; j += j & -j) {
                tr[x][j] += v;
            }
        }
    }

    [[nodiscard]] int query(int x, int y) const {
        int res = 0;
        for (; x; x -= x & -x) {
            for (int j = y; j; j -= j & -j) {
                res += tr[x][j];
            }
        }
        return res;
    }

private:
    std::vector<std::vector<int>> tr;
    size_t n;
    size_t m;
};

signed main() {
    char cha;
    int n, m;
    std::cin >> cha >> n >> m;
    const std::vector x(n + 1, std::vector<int>(m + 1));
    BIT bit0(x), bit1(x), bit2(x), bit3(x);
    auto sum = [&](const int x_, const int y) -> int {
        return (x_ + 1) * (y + 1) * bit0.query(x_, y) - (x_ + 1) * bit2.query(x_, y) - 
            (y + 1) * bit1.query(x_, y) + bit3.query(x_, y);
    };
    while (std::cin >> cha) {
        if (cha == 'L') {
            int a, b, c, d, delta;
            std::cin >> a >> b >> c >> d >> delta;
            bit0.update(a, b, delta);
            bit0.update(a, d + 1, -delta);
            bit0.update(c + 1, b, -delta);
            bit0.update(c + 1, d + 1, delta);

            bit1.update(a, b, a * delta);
            bit1.update(a, d + 1, -a * delta);
            bit1.update(c + 1, b, -(c + 1) * delta);
            bit1.update(c + 1, d + 1, (c + 1) * delta);

            bit2.update(a, b, b * delta);
            bit2.update(a, d + 1, -(d + 1) * delta);
            bit2.update(c + 1, b, -b * delta);
            bit2.update(c + 1, d + 1, (d + 1) * delta);

            bit3.update(a, b, a * b * delta);
            bit3.update(a, d + 1, -a * (d + 1) * delta);
            bit3.update(c + 1, b, -(c + 1) * b * delta);
            bit3.update(c + 1, d + 1, (c + 1) * (d + 1) * delta);
        } else {
            int a, b, c, d;
            std::cin >> a >> b >> c >> d;
            std::cout << sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1) << "\n";
        }
    }
    return 0;
}

---

最后更新于：2026-03-22