线段树 (Segment Tree)¶

线段树是一种二叉搜索树，能够以 \(\mathcal{O}(\log n)\) 的时间复杂度完成区间修改与区间统计查询。引入懒标记 (Lazy Tag) 机制后，可将区间修改的复杂度从 \(\mathcal{O}(n)\) 降至 \(\mathcal{O}(\log n)\)。

区间加与区间和查询 (带懒标记)¶

标准 1-indexed 线段树，数组空间需开 \(4N\)。

#include <vector>

template <typename T = long long>
struct LazySegmentTree {
    int n;
    std::vector<T> sum;
    std::vector<T> lazy;

    LazySegmentTree(int n) : n(n), sum(4 * n + 5, 0), lazy(4 * n + 5, 0) {}

    // 建树
    void build(const std::vector<T> &a, int u, int l, int r) {
        if (l == r) {
            sum[u] = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(a, u << 1, l, mid);
        build(a, u << 1 | 1, mid + 1, r);
        push_up(u);
    }

    void push_up(int u) {
        sum[u] = sum[u << 1] + sum[u << 1 | 1];
    }

    void push_down(int u, int l, int r) {
        if (lazy[u] != 0) {
            int mid = (l + r) >> 1;
            // 下传左子节点
            lazy[u << 1] += lazy[u];
            sum[u << 1] += lazy[u] * (mid - l + 1);
            // 下传右子节点
            lazy[u << 1 | 1] += lazy[u];
            sum[u << 1 | 1] += lazy[u] * (r - mid);
            // 清除当前节点标记
            lazy[u] = 0;
        }
    }

    // 区间加: a[ql...qr] += val
    void update(int u, int l, int r, int ql, int qr, T val) {
        if (ql <= l && r <= qr) {
            sum[u] += val * (r - l + 1);
            lazy[u] += val;
            return;
        }
        push_down(u, l, r);
        int mid = (l + r) >> 1;
        if (ql <= mid) update(u << 1, l, mid, ql, qr, val);
        if (qr > mid)  update(u << 1 | 1, mid + 1, r, ql, qr, val);
        push_up(u);
    }

    // 区间和查询: sum(a[ql...qr])
    T query(int u, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return sum[u];
        }
        push_down(u, l, r);
        int mid = (l + r) >> 1;
        T res = 0;
        if (ql <= mid) res += query(u << 1, l, mid, ql, qr);
        if (qr > mid)  res += query(u << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }

    // 便捷调用包装接口
    void update(int ql, int qr, T val) { update(1, 1, n, ql, qr, val); }
    T query(int ql, int qr) { return query(1, 1, n, ql, qr); }
};

避坑与优化要点¶

数组开 \(4N\)：如果线段树数组只开 \(2N\) 会导致运行时越界访问（RE）。理论最坏情况下需要开到大于等于 \(2^{\lceil \log_2 n \rceil + 1} \le 4n\) 的大小。
移位运算优先级：u << 1 | 1 中位或 | 的优先级低于加减法，但高于比较。使用 u << 1 和 u << 1 | 1 代表左右子节点，速度优于乘除法。
标记下传时机：只要存在对子树的访问（无论更新还是查询），必须在递归子树前调用 push_down。

LeetCode 经典真题精选与题解提示¶

LeetCode 307 - 区域和检索 - 数组可修改 (Range Sum Query - Mutable) 中等
提示

单点修改与区间求和模板题。
- 核心操作为单点更新 update(index, val) 和区间查询 sumRange(left, right)。
- 既可用线段树实现，也可以用更加轻量的树状数组（Fenwick Tree）解决，单次操作复杂度均为 \(\mathcal{O}(\log n)\)。
LeetCode 218 - 天际线问题 (The Skyline Problem) 困难
提示

区间最值维护与坐标离散化 / 扫描线。
- 收集所有建筑物的左右端点并离散化映射到离散坐标轴上。
- 按照建筑高度从小到大或者利用扫描线处理，区间修改对应区间高度更新（取 \(\max\)）。线段树维护区间最大高度，支持快速查询各关键转折点的高度。
LeetCode 715 - Range 模块 (Range Module) 困难
提示

动态开点线段树 / 区间赋值覆盖。
- 坐标范围高达 \(10^9\)，无法预先建树，适合使用动态开点线段树（指针或动态数组开点）或平衡树/std::set 维护不重叠区间（珂朵莉树/ODT思想）。
- 维护区间覆盖标志：\(1\) 表示完全被跟踪，\(0\) 表示未被跟踪。addRange 对应区间置 1，removeRange 对应区间置 0，queryRange 查询区间是否全为 1。
LeetCode 2286 - 预订会议室 III (Booking Concert Tickets in Groups) 困难
提示

线段树上二分 (Segment Tree Binary Search)。
- 维护两棵线段树或同一线段树的两个属性：区间内剩余座位的最大值 \(\max\) 和区间内剩余座位的总和 \(\text{sum}\)。
- gather(k, maxRow)：在线段树上二分查找在行号 \([0, \text{maxRow}]\) 内第一个剩余座位 \(\ge k\) 的行；
- scatter(k, maxRow)：先区间查询 \([0, \text{maxRow}]\) 内的总剩余座位是否 \(\ge k\)，若满足则从左往右贪心填充并更新线段树节点。