线段树

概念讲解

什么是线段树？

线段树是一种支持区间修改和区间查询的二叉树数据结构。

核心思想

• 每个节点代表一个区间
• 叶子节点是单个元素
• 父节点的区间 = 左右子区间之和

基本操作

建树

1234567891011121314151617181920const int N = 100005;
int a[N];
struct Node {
    int sum, lazy;
} tree[4 * N];

void pushUp(int p) {
    tree[p].sum = tree[2*p].sum + tree[2*p+1].sum;
}

void build(int p, int l, int r) {
    if (l == r) {
        tree[p].sum = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);
    pushUp(p);
}

lazy 标记

12345678910void pushDown(int p, int l, int r) {
    if (tree[p].lazy) {
        int mid = (l + r) / 2;
        tree[2*p].lazy += tree[p].lazy;
        tree[2*p+1].lazy += tree[p].lazy;
        tree[2*p].sum += tree[p].lazy * (mid - l + 1);
        tree[2*p+1].sum += tree[p].lazy * (r - mid);
        tree[p].lazy = 0;
    }
}

区间修改

123456789101112void update(int p, int l, int r, int ql, int qr, int c) {
    if (ql <= l && r <= qr) {
        tree[p].sum += c * (r - l + 1);
        tree[p].lazy += c;
        return;
    }
    pushDown(p, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) update(2*p, l, mid, ql, qr, c);
    if (qr > mid) update(2*p+1, mid+1, r, ql, qr, c);
    pushUp(p);
}

区间查询

123456789int query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[p].sum;
    pushDown(p, l, r);
    int mid = (l + r) / 2;
    int sum = 0;
    if (ql <= mid) sum += query(2*p, l, mid, ql, qr);
    if (qr > mid) sum += query(2*p+1, mid+1, r, ql, qr);
    return sum;
}

时间复杂度

考点分析

初赛考查方式

1. 程序阅读： 线段树操作
2. 编程题： 区间问题

常见考点

• lazy 标记
• pushDown
• 区间修改

例题精讲

例题 1：区间修改

题目： 区间加，区间求和。

解答：

12update(1, 1, n, l, r, c);  // [l, r] 加 c
int sum = query(1, 1, n, l, r);  // [l, r] 的和

练习题

1. lazy 标记的作用是什么？

2. pushDown 的时机是什么？

12345678void update(int p, int l, int r, int ql, int qr, int c) {
    if (ql <= l && r <= qr) {
        // 完全包含，直接更新
        return;
    }
    pushDown(p, l, r);  // 访问子节点前下传
    // ...
}

3. 线段树和树状数组的区别是什么？

易错点

⚠️ 注意：

1. 数组要开 4 倍大小
2. 操作前要 pushDown
3. 操作后要 pushUp
4. lazy 标记要清零