树状数组：动态前缀和

问题#

维护一个数组，支持：

1. 把单个元素 $a_i$ 增加 $\Delta$；
2. 查询半开区间 $[l,r)$ 的元素和。

普通前缀和可以 $O(1)$ 查询，但一次修改会影响后续所有前缀。树状数组把前缀拆成若干个 长度为 2 的幂的区间，使修改和查询都只访问 $O(\log n)$ 个节点。

核心思想#

树状数组内部使用 1-based 下标。定义：

$$\operatorname{lowbit}(x)=x\mathbin{\&}(-x),$$

它取出 $x$ 二进制表示中最低位的 1。节点 tree[x] 管辖区间：

$$(x-\operatorname{lowbit}(x),x],$$

长度恰为 lowbit(x)。

前缀查询#

查询前 $x$ 个元素时，累加 tree[x]，然后执行 x -= lowbit(x)。每次都会清除一个二进制 1，直到变成 0。

单点修改#

修改位置 $x$ 时，所有包含它的树状数组节点依次为 x、x + lowbit(x)……，直到超过 $n$。

不变量#

tree[x] 始终等于其管辖区间内所有数组元素之和。单点修改沿父节点方向 更新所有包含该位置的管辖区间；前缀查询选择的管辖区间互不重叠，且恰好覆盖目标前缀。

复杂度#

• 单点增加：$O(\log n)$
• 前缀和、区间和：$O(\log n)$
• 空间：$O(n)$
• 正文用逐点增加建树，复杂度 $O(n\log n)$；可优化到 $O(n)$

可独立编译的 C++17 模板#

对外接口使用 0-based 半开区间；1-based 细节封装在类内部。

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class FenwickTree {
public:
    explicit FenwickTree(std::size_t size)
        : size_(size), tree_(size + 1, 0) {}

    explicit FenwickTree(const std::vector<long long>& values)
        : FenwickTree(values.size()) {
        for (std::size_t i = 0; i < values.size(); ++i) {
            add(i, values[i]);
        }
    }

    // values[index] += delta
    void add(std::size_t index, long long delta) {
        if (index >= size_) {
            throw std::out_of_range("index out of range");
        }

        for (
            std::size_t i = index + 1;
            i <= size_;
            i += lowbit(i)
        ) {
            tree_[i] += delta;
        }
    }

    // 返回 values[0, end) 的和，允许 end == 0。
    long long prefix_sum(std::size_t end) const {
        if (end > size_) {
            throw std::out_of_range("prefix end out of range");
        }

        long long answer = 0;
        for (std::size_t i = end; i > 0; i -= lowbit(i)) {
            answer += tree_[i];
        }
        return answer;
    }

    long long range_sum(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
        return prefix_sum(r) - prefix_sum(l);
    }

private:
    std::size_t size_;
    std::vector<long long> tree_;

    static std::size_t lowbit(std::size_t value) {
        return value & (~value + 1);
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    FenwickTree fenwick(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::cin >> operation;

        if (operation == "add") {
            std::size_t index = 0;
            long long delta = 0;
            std::cin >> index >> delta;
            fenwick.add(index, delta);
        } else if (operation == "sum") {
            std::size_t l = 0;
            std::size_t r = 0;
            std::cin >> l >> r;
            std::cout << fenwick.range_sum(l, r) << '\n';
        }
    }
}

示例#

输入：

5 4
1 2 3 4 5
sum 0 5
add 2 10
sum 1 4
sum 2 3

输出：

15
19
13

修改后第三个元素从 3 变为 13，因此区间 $[1,4)$ 的和是 $2+13+4=19$。

易错点#

• 内部下标从 0 开始：若更新循环从 0 开始，lowbit(0)=0 会导致死循环。 模板只在类内部使用 1-based 下标。
• 把赋值当成增量：add(i, delta) 表示增加。若要赋成 $x$，需先知道 旧值并增加 $x-a_i$。
• 区间端点混乱：正文接口是 $[l,r)$，区间和等于 prefix_sum(r) - prefix_sum(l)。
• 和类型过小：即使单个元素是 int，总和也可能需要 64 位。
• 操作不满足可逆性：普通树状数组用两个前缀相减得到区间和。对没有逆运算的 min/max，不能直接套用。
• 无符号下标下溢：不要在公开接口中计算 l - 1；半开区间可以避免。

边界测试#

• 单元素数组；更新和查询首、末位置。
• 空前缀 prefix_sum(0) 与空区间 $[i,i)$。
• 查询整个数组和长度 1 区间。
• 同一位置多次正负更新。
• 数组总和超过 32 位整数范围。
• 随机生成单点增加和区间查询，与朴素数组对拍。

常见变体#

点改、区查#

正文模板就是这一形式。区间和由两个前缀和相减：

$$\operatorname{sum}(l,r) =\operatorname{prefix}(r)-\operatorname{prefix}(l).$$

若需要单点赋值，额外保存原数组并调用 add(index, new_value - old_value)。

区改、点查#

维护差分数组 $d_i=a_i-a_{i-1}$。给 $[l,r)$ 加 $x$ 等价于：

$$d_l\mathrel{+}=x,\qquad d_r\mathrel{-}=x$$

第二项只在 $r<n$ 时存在。把差分数组放进一棵树状数组后， $a_i=\sum_{j=0}^{i}d_j$，所以区间修改与单点查询都是 $O(\log n)$。

下面的完整模板支持 add l r delta 与 get index。差分 BIT 只需覆盖原数组的 $n$ 个位置，因此右端点 $r=n$ 时不写入哨兵；空区间直接返回，避免 尝试修改不存在的下标 $n$。

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class FenwickDifference {
public:
    explicit FenwickDifference(std::size_t size)
        : size_(size), tree_(size + 1, 0) {}

    void add(std::size_t index, long long delta) {
        if (index >= size_) {
            throw std::out_of_range("difference index out of range");
        }
        for (
            std::size_t i = index + 1;
            i <= size_;
            i += lowbit(i)
        ) {
            tree_[i] += delta;
        }
    }

    long long prefix_sum(std::size_t end) const {
        if (end > size_) {
            throw std::out_of_range("prefix end out of range");
        }
        long long answer = 0;
        for (std::size_t i = end; i > 0; i -= lowbit(i)) {
            answer += tree_[i];
        }
        return answer;
    }

private:
    std::size_t size_;
    std::vector<long long> tree_;

    static std::size_t lowbit(std::size_t value) {
        return value & (~value + 1);
    }
};

class RangeAddPointQuery {
public:
    explicit RangeAddPointQuery(
        const std::vector<long long>& values
    )
        : size_(values.size()), difference_(size_) {
        long long previous = 0;
        for (std::size_t i = 0; i < size_; ++i) {
            difference_.add(i, values[i] - previous);
            previous = values[i];
        }
    }

    void range_add(
        std::size_t l,
        std::size_t r,
        long long delta
    ) {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
        if (l == r) {
            return;
        }
        difference_.add(l, delta);
        if (r < size_) {
            difference_.add(r, -delta);
        }
    }

    long long point(std::size_t index) const {
        if (index >= size_) {
            throw std::out_of_range("index out of range");
        }
        return difference_.prefix_sum(index + 1);
    }

private:
    std::size_t size_;
    FenwickDifference difference_;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    RangeAddPointQuery structure(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::cin >> operation;
        if (operation == "add") {
            std::size_t l = 0;
            std::size_t r = 0;
            long long delta = 0;
            std::cin >> l >> r >> delta;
            structure.range_add(l, r, delta);
        } else if (operation == "get") {
            std::size_t index = 0;
            std::cin >> index;
            std::cout << structure.point(index) << '\n';
        }
    }
}

区改、区查#

使用两棵维护差分的树状数组 $B_1,B_2$。对 0-based 半开区间 $[l,r)$ 增加 $x$， 在“允许更新到哨兵位置 $n$”的内部 BIT 上执行：

$$\begin{aligned} B_1[l]&\mathrel{+}=x,&B_1[r]&\mathrel{-}=x,\\ B_2[l]&\mathrel{+}=lx,&B_2[r]&\mathrel{-}=rx. \end{aligned}$$

前 $p$ 个元素之和为：

$$\operatorname{prefix}(p) =p\cdot\operatorname{sum}(B_1,p)-\operatorname{sum}(B_2,p).$$

于是 $[l,r)$ 的区间和仍是 prefix(r) - prefix(l)。实现时两棵 BIT 的容量应至少覆盖哨兵下标 $n$， 并始终使用 64 位乘法。

下面的完整模板让内部 BIT 覆盖位置 $0$ 到 $n$。函数 Fenwick::prefix_sum(p) 统计位置 $[0,p)$，所以求原数组前 $p$ 项时，恰好 不会把哨兵位置 $p$ 的差分算进去。

#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

class Fenwick {
public:
    explicit Fenwick(std::size_t size)
        : size_(size), tree_(size + 1, 0) {}

    void add(std::size_t index, long long delta) {
        if (index >= size_) {
            throw std::out_of_range("Fenwick index out of range");
        }
        for (
            std::size_t i = index + 1;
            i <= size_;
            i += lowbit(i)
        ) {
            tree_[i] += delta;
        }
    }

    long long prefix_sum(std::size_t end) const {
        if (end > size_) {
            throw std::out_of_range("prefix end out of range");
        }
        long long answer = 0;
        for (std::size_t i = end; i > 0; i -= lowbit(i)) {
            answer += tree_[i];
        }
        return answer;
    }

private:
    std::size_t size_;
    std::vector<long long> tree_;

    static std::size_t lowbit(std::size_t value) {
        return value & (~value + 1);
    }
};

class RangeAddRangeSum {
public:
    explicit RangeAddRangeSum(
        const std::vector<long long>& values
    )
        : size_(values.size()),
          coefficient_(size_ + 1),
          constant_(size_ + 1) {
        for (std::size_t i = 0; i < size_; ++i) {
            range_add(i, i + 1, values[i]);
        }
    }

    void range_add(
        std::size_t l,
        std::size_t r,
        long long delta
    ) {
        validate_range(l, r);
        add_difference(l, delta);
        add_difference(r, -delta);
    }

    long long range_sum(
        std::size_t l,
        std::size_t r
    ) const {
        validate_range(l, r);
        return prefix_sum(r) - prefix_sum(l);
    }

private:
    std::size_t size_;
    Fenwick coefficient_;
    Fenwick constant_;

    void add_difference(std::size_t position, long long delta) {
        coefficient_.add(position, delta);
        constant_.add(
            position,
            delta * static_cast<long long>(position)
        );
    }

    long long prefix_sum(std::size_t end) const {
        const long long coefficient_sum =
            coefficient_.prefix_sum(end);
        const long long constant_sum = constant_.prefix_sum(end);
        return static_cast<long long>(end) * coefficient_sum -
               constant_sum;
    }

    void validate_range(
        std::size_t l,
        std::size_t r
    ) const {
        if (l > r || r > size_) {
            throw std::out_of_range("invalid range");
        }
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int operation_count = 0;
    std::cin >> n >> operation_count;
    if (n < 0 || operation_count < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    RangeAddRangeSum structure(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::size_t l = 0;
        std::size_t r = 0;
        std::cin >> operation >> l >> r;
        if (operation == "add") {
            long long delta = 0;
            std::cin >> delta;
            structure.range_add(l, r, delta);
        } else if (operation == "sum") {
            std::cout << structure.range_sum(l, r) << '\n';
        }
    }
}

延伸阅读（非课程主线）：线性建树与二维树状数组#

• 线性建树可先令 tree[i] += a[i]，再把它贡献给 i + lowbit(i)，总时间 $O(n)$。
• 二维树状数组把两层下标都按 lowbit 跳转，可处理点修改与矩形前缀和，复杂度 $O(\log^2 n)$。