线段树：区间修改、区间查询与懒标记

问题#

维护一个数组，支持：

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

树状数组擅长前缀型信息；线段树则显式保存一棵区间二叉树，能维护更一般的可合并信息， 也能通过懒标记高效处理整段修改。

核心思想#

每个节点对应一个区间 $[s,t)$：

• 叶子对应单个元素；
• 非叶节点把区间从中点分成两个不相交子区间；
• 当前节点的和等于两个孩子的和。

查询时：

• 若节点区间被询问完全覆盖，直接返回节点信息；
• 若只部分相交，递归到相交的孩子并合并；
• 若不相交，返回加法单位元 0。

懒标记#

若一次加法完整覆盖节点区间，无需立刻访问所有叶子。设节点长度为 $\text{len}=t-s$，直接执行：

$$\text{sum}\mathrel{+}=\Delta\cdot\text{len}, \qquad \text{lazy}\mathrel{+}=\Delta.$$

只有之后需要访问孩子时，才把 lazy 下传给两个孩子。

不变量#

• tree[node] 始终是该节点整个区间的真实元素和。
• lazy[node] 表示该节点的两个孩子尚未吸收、但已经计入当前节点和的 统一增量。
• 每次递归返回前，父节点重新由两个孩子合并；完整覆盖时则直接更新当前节点。

复杂度#

• 建树：$O(n)$
• 区间加：$O(\log n)$
• 区间和：$O(\log n)$
• 空间：$O(n)$，数组式实现通常分配约 $4n$

单次区间操作最多在每一层访问常数个边界节点，完整覆盖的中间区间会被整段接收。

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

接口统一使用 0-based 半开区间。空区间查询返回 0，空区间修改不产生效果。

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

class LazySegmentTree {
public:
    explicit LazySegmentTree(const std::vector<long long>& values)
        : size_(values.size()),
          tree_(size_ == 0 ? 1 : size_ * 4, 0),
          lazy_(size_ == 0 ? 1 : size_ * 4, 0) {
        if (size_ != 0) {
            build(1, 0, size_, values);
        }
    }

    void range_add(
        std::size_t l,
        std::size_t r,
        long long delta
    ) {
        validate_range(l, r);
        if (l == r) {
            return;
        }
        range_add(1, 0, size_, l, r, delta);
    }

    long long range_sum(
        std::size_t l,
        std::size_t r
    ) {
        validate_range(l, r);
        if (l == r) {
            return 0;
        }
        return range_sum(1, 0, size_, l, r);
    }

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

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

    void build(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        const std::vector<long long>& values
    ) {
        if (right - left == 1) {
            tree_[node] = values[left];
            return;
        }

        const std::size_t middle = left + (right - left) / 2;
        build(node * 2, left, middle, values);
        build(node * 2 + 1, middle, right, values);
        pull(node);
    }

    void pull(std::size_t node) {
        tree_[node] = tree_[node * 2] + tree_[node * 2 + 1];
    }

    void apply(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        long long delta
    ) {
        tree_[node] +=
            delta * static_cast<long long>(right - left);
        lazy_[node] += delta;
    }

    void push(
        std::size_t node,
        std::size_t left,
        std::size_t right
    ) {
        if (lazy_[node] == 0 || right - left == 1) {
            return;
        }

        const std::size_t middle = left + (right - left) / 2;
        apply(node * 2, left, middle, lazy_[node]);
        apply(node * 2 + 1, middle, right, lazy_[node]);
        lazy_[node] = 0;
    }

    void range_add(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        std::size_t query_left,
        std::size_t query_right,
        long long delta
    ) {
        if (query_right <= left || right <= query_left) {
            return;
        }
        if (query_left <= left && right <= query_right) {
            apply(node, left, right, delta);
            return;
        }

        push(node, left, right);
        const std::size_t middle = left + (right - left) / 2;
        range_add(
            node * 2,
            left,
            middle,
            query_left,
            query_right,
            delta
        );
        range_add(
            node * 2 + 1,
            middle,
            right,
            query_left,
            query_right,
            delta
        );
        pull(node);
    }

    long long range_sum(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        std::size_t query_left,
        std::size_t query_right
    ) {
        if (query_right <= left || right <= query_left) {
            return 0;
        }
        if (query_left <= left && right <= query_right) {
            return tree_[node];
        }

        push(node, left, right);
        const std::size_t middle = left + (right - left) / 2;
        return
            range_sum(
                node * 2,
                left,
                middle,
                query_left,
                query_right
            ) +
            range_sum(
                node * 2 + 1,
                middle,
                right,
                query_left,
                query_right
            );
    }
};

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;
    }

    LazySegmentTree segment_tree(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;
            segment_tree.range_add(l, r, delta);
        } else if (operation == "sum") {
            std::cout << segment_tree.range_sum(l, r) << '\n';
        }
    }
}

示例#

输入：

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

输出：

21
26
40

两次修改后数组变为 $1,12,11,12,13,4$，最后查询的是 $11+12+13+4=40$。

易错点#

• 相交判断写错：半开区间不相交条件是 query_right <= left || right <= query_left。
• 完整覆盖后仍向下递归：应直接更新当前节点并返回。
• lazy 已计入当前节点却重复计算：标记表示“孩子尚未吸收”，当前节点和已经更新。
• 访问孩子前忘记下传：局部查询或修改前必须 push。
• 下传后忘记清空父标记：否则下一次会重复下传。
• 长度差一位：半开区间节点长度是 right - left。
• 单位元错误：求和的不相交返回 0；求最大值时不能在全负数组中也返回 0。
• 溢出：节点和以及 delta * length 都用 64 位。

边界测试#

• 单元素数组；$n$ 不是 2 的幂。
• 空区间、单点区间、整个数组、跨中点区间。
• 更新首尾、完整覆盖根节点、只覆盖一个叶子。
• 多次更新同一区间；嵌套、相邻、互不相交的更新。
• 整段更新后做局部查询，局部更新后做整段查询。
• 全负数、大增量与大区间。
• 随机生成修改/查询序列，与朴素数组对拍。

常见变体#

点改、区查#

不需要 lazy。沿根到叶子的路径修改一个位置，再逐层 pull；区间查询与正文 相同。可维护和、最值、最大公约数等满足结合律的信息。

区改、点查#

若只需要单点值，区间完整覆盖时累积 lazy，查询位置时沿根到叶把路径上的标记相加。 实现比区改区查更简单，但正文完整模板同样能回答单点区间。

区改、区查与 lazy 组合#

• 区间加 + 区间和：正文中标记相加即可。
• 区间赋值 + 区间和：可令标记表示 $T(x)=(\text{has\_assign}?\text{assign}:x)+\text{add}$。新赋值 $v$ 到来时设为 {true, v, 0}；新加法 $d$ 到来时只执行 add += d。节点和分别 更新为 $v\cdot\text{len}$ 与 $\text{sum}+d\cdot\text{len}$。下传时必须先给孩子赋值， 再给孩子加法。
• 仿射变换 $f(x)=ax+b$：节点和更新为 $a\cdot\text{sum}+b\cdot\text{len}$。若节点旧标记为 $g(x)=a_0x+b_0$，随后又完整覆盖一个新操作 $f$，应保存的是“新在外、旧在内”的 $f\circ g$：

$$(a_0,b_0)\leftarrow(aa_0,\;ab_0+b).$$

下传到已有标记 $h$ 的孩子时同样调用一次上述“应用新操作”过程，使孩子标记变成 $g\circ h$。若题目要求取模，节点和与两个标记分量的每一步乘加都必须取模；恒等标记是 $(1,0)$，而区间赋值 $x\leftarrow v$ 正好是仿射标记 $(0,v)$。

设计 lazy 时必须明确“新操作与旧标记如何复合”，再决定下传顺序。

第 $k$ 个 1：完整模板#

节点只保存区间内 1 的个数。kth(k) 中的 $k$ 从 0 开始：若左孩子包含的 1 数量大于 $k$，答案在左侧；否则令 $k$ 减去左孩子计数并进入右侧。点修改和查找都是 $O(\log n)$。

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

class KthOneSegmentTree {
public:
    explicit KthOneSegmentTree(const std::vector<int>& bits)
        : size_(bits.size()),
          tree_(size_ == 0 ? 1 : size_ * 4, 0) {
        if (size_ != 0) {
            build(1, 0, size_, bits);
        }
    }

    void set(std::size_t index, int value) {
        if (index >= size_ || (value != 0 && value != 1)) {
            throw std::out_of_range("invalid point update");
        }
        set(1, 0, size_, index, value);
    }

    int count() const {
        return size_ == 0 ? 0 : tree_[1];
    }

    std::size_t kth(std::size_t k) const {
        if (size_ == 0 || k >= static_cast<std::size_t>(tree_[1])) {
            throw std::out_of_range("there are fewer than k + 1 ones");
        }

        std::size_t node = 1;
        std::size_t left = 0;
        std::size_t right = size_;
        while (right - left > 1) {
            const std::size_t middle =
                left + (right - left) / 2;
            const int left_count = tree_[node * 2];
            if (k < static_cast<std::size_t>(left_count)) {
                node *= 2;
                right = middle;
            } else {
                k -= static_cast<std::size_t>(left_count);
                node = node * 2 + 1;
                left = middle;
            }
        }
        return left;
    }

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

    void build(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        const std::vector<int>& bits
    ) {
        if (right - left == 1) {
            if (bits[left] != 0 && bits[left] != 1) {
                throw std::invalid_argument("input must contain only 0 or 1");
            }
            tree_[node] = bits[left];
            return;
        }
        const std::size_t middle = left + (right - left) / 2;
        build(node * 2, left, middle, bits);
        build(node * 2 + 1, middle, right, bits);
        tree_[node] = tree_[node * 2] + tree_[node * 2 + 1];
    }

    void set(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        std::size_t index,
        int value
    ) {
        if (right - left == 1) {
            tree_[node] = value;
            return;
        }
        const std::size_t middle = left + (right - left) / 2;
        if (index < middle) {
            set(node * 2, left, middle, index, value);
        } else {
            set(node * 2 + 1, middle, right, index, value);
        }
        tree_[node] = tree_[node * 2] + tree_[node * 2 + 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 || operation_count < 0) {
        return 0;
    }

    std::vector<int> bits(static_cast<std::size_t>(n));
    for (int& bit : bits) {
        std::cin >> bit;
    }

    KthOneSegmentTree tree(bits);
    while (operation_count-- > 0) {
        std::string operation;
        std::cin >> operation;
        if (operation == "set") {
            std::size_t index = 0;
            int value = 0;
            std::cin >> index >> value;
            tree.set(index, value);
        } else if (operation == "kth") {
            std::size_t k = 0;
            std::cin >> k;
            std::cout << tree.kth(k) << '\n';
        } else if (operation == "count") {
            std::cout << tree.count() << '\n';
        }
    }
}

最大连续子段和：完整模板#

每个节点维护四个量：总和 sum、最大非空前缀 prefix、最大非空 后缀 suffix、最大非空子段 best。左右节点 $L,R$ 的合并式为：

$$\begin{aligned} \text{sum}&=L.\text{sum}+R.\text{sum},\\ \text{prefix}&=\max(L.\text{prefix},L.\text{sum}+R.\text{prefix}),\\ \text{suffix}&=\max(R.\text{suffix},R.\text{sum}+L.\text{suffix}),\\ \text{best}&=\max(L.\text{best},R.\text{best},L.\text{suffix}+R.\text{prefix}). \end{aligned}$$

叶子的四个量都等于元素本身，因此全负数组会返回最大的那个负数，而不是错误地返回 0。 查询函数用 std::optional 表示“不相交”，避免伪造一个容易溢出的负无穷 单位元。

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

struct MaximumSubarrayNode {
    long long sum = 0;
    long long prefix = 0;
    long long suffix = 0;
    long long best = 0;
};

MaximumSubarrayNode merge(
    const MaximumSubarrayNode& left,
    const MaximumSubarrayNode& right
) {
    return {
        left.sum + right.sum,
        std::max(left.prefix, left.sum + right.prefix),
        std::max(right.suffix, right.sum + left.suffix),
        std::max({
            left.best,
            right.best,
            left.suffix + right.prefix
        })
    };
}

class MaximumSubarraySegmentTree {
public:
    explicit MaximumSubarraySegmentTree(
        const std::vector<long long>& values
    )
        : size_(values.size()),
          tree_(size_ == 0 ? 1 : size_ * 4) {
        if (size_ != 0) {
            build(1, 0, size_, values);
        }
    }

    void set(std::size_t index, long long value) {
        if (index >= size_) {
            throw std::out_of_range("index out of range");
        }
        set(1, 0, size_, index, value);
    }

    long long range_best(
        std::size_t l,
        std::size_t r
    ) const {
        if (l >= r || r > size_) {
            throw std::out_of_range("query must be non-empty");
        }
        return query(1, 0, size_, l, r)->best;
    }

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

    static MaximumSubarrayNode leaf(long long value) {
        return {value, value, value, value};
    }

    void build(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        const std::vector<long long>& values
    ) {
        if (right - left == 1) {
            tree_[node] = leaf(values[left]);
            return;
        }
        const std::size_t middle = left + (right - left) / 2;
        build(node * 2, left, middle, values);
        build(node * 2 + 1, middle, right, values);
        tree_[node] = merge(tree_[node * 2], tree_[node * 2 + 1]);
    }

    void set(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        std::size_t index,
        long long value
    ) {
        if (right - left == 1) {
            tree_[node] = leaf(value);
            return;
        }
        const std::size_t middle = left + (right - left) / 2;
        if (index < middle) {
            set(node * 2, left, middle, index, value);
        } else {
            set(node * 2 + 1, middle, right, index, value);
        }
        tree_[node] = merge(tree_[node * 2], tree_[node * 2 + 1]);
    }

    std::optional<MaximumSubarrayNode> query(
        std::size_t node,
        std::size_t left,
        std::size_t right,
        std::size_t query_left,
        std::size_t query_right
    ) const {
        if (query_right <= left || right <= query_left) {
            return std::nullopt;
        }
        if (query_left <= left && right <= query_right) {
            return tree_[node];
        }

        const std::size_t middle = left + (right - left) / 2;
        const auto left_result = query(
            node * 2,
            left,
            middle,
            query_left,
            query_right
        );
        const auto right_result = query(
            node * 2 + 1,
            middle,
            right,
            query_left,
            query_right
        );
        if (!left_result.has_value()) {
            return right_result;
        }
        if (!right_result.has_value()) {
            return left_result;
        }
        return merge(*left_result, *right_result);
    }
};

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;
    }

    MaximumSubarraySegmentTree tree(values);
    while (operation_count-- > 0) {
        std::string operation;
        std::cin >> operation;
        if (operation == "set") {
            std::size_t index = 0;
            long long value = 0;
            std::cin >> index >> value;
            tree.set(index, value);
        } else if (operation == "best") {
            std::size_t l = 0;
            std::size_t r = 0;
            std::cin >> l >> r;
            std::cout << tree.range_best(l, r) << '\n';
        }
    }
}

其他复合节点信息#

• 区间最大值及其出现次数：节点保存最大值和计数；相同最大值时计数相加。

延伸阅读（非课程主线）：持久化与动态开点#

• 持久化线段树在修改时复制根到叶路径，可查询历史版本。
• 坐标范围极大但实际访问点少时，可按需创建节点，避免按整个坐标域分配数组。