线段树 (Segment Tree) 模板详解

线段树 (Segment Tree) 模板详解

1. 简介

线段树是一种用于处理区间查询和修改操作的树形数据结构。它能够在 O(log n) 的时间复杂度内完成单点修改和区间查询操作。本模板采用了模板编程的方式，支持自定义信息类型，实现了灵活且高效的区间操作。

主要特点：

  • 支持自定义信息类型和合并操作
  • 单点修改时间复杂度 O(log n)
  • 区间查询时间复杂度 O(log n)
  • 支持区间第一个/最后一个满足条件的位置查询

2. 实现原理

2.1 基本结构

线段树的核心是将区间划分为多个子区间：

  1. 每个节点代表一个区间
  2. 左右子节点分别代表区间的左右半部分
  3. 叶子节点代表单个元素

2.2 核心策略

  1. 信息合并：

    • 通过自定义的 Info 类型实现信息的存储
    • 使用运算符重载 operator+ 定义区间信息的合并方式

  2. 区间管理：

    • 使用完全二叉树存储区间信息
    • 动态维护区间信息的更新和查询

  3. 二分策略：

    • 利用二分思想处理区间查询
    • 实现查找第一个/最后一个满足条件的位置

3. 模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    
    // 构造函数
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    
    // 初始化函数
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    
    // 节点信息更新
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    
    // 单点修改
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    
    // 区间查询
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    
    // 查找第一个满足条件的位置
    template<class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    
    // 查找最后一个满足条件的位置
    template<class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

4. 函数说明

4.1 构造和初始化

1
2
3
SegmentTree()
SegmentTree(int n_, Info v_ = Info())
SegmentTree(std::vector<T> init_)
  • 支持默认构造、大小初始化和数组初始化
  • 可以指定初始值类型和默认值

4.2 核心操作

1
2
3
4
void modify(int p, const Info &v)
Info rangeQuery(int l, int r)
int findFirst(int l, int r, F pred)
int findLast(int l, int r, F pred)
  • modify: 单点修改
  • rangeQuery: 区间查询
  • findFirst/findLast: 查找满足条件的位置

5. 时间复杂度分析

  • 初始化：O(n)

    • 建树过程：O(n)
    • 空间分配：O(n)

  • 核心操作：O(log n)

    • 单点修改：O(log n)
    • 区间查询：O(log n)
    • 条件查找：O(log n)

  • 空间复杂度：O(n)

    • 使用数组存储完全二叉树

6. 应用场景

  1. 区间求和/最值问题
  2. 区间统计查询
  3. 动态维护序列信息
  4. 区间更新和查询
  5. 在线处理区间操作

7. 使用示例

7.1 区间求和

1
2
3
4
5
6
7
8
9
10
11
struct Sum {
    long long sum = 0;
    Sum operator+(const Sum &rhs) const {
        return {sum + rhs.sum};
    }
};

// 使用示例
SegmentTree<Sum> st(n);
st.modify(i, {val});  // 修改单点值
auto sum = st.rangeQuery(l, r).sum;  // 查询区间和

7.2 区间最值

1
2
3
4
5
6
7
8
9
10
11
struct Max {
    int val = -1e9;
    Max operator+(const Max &rhs) const {
        return {std::max(val, rhs.val)};
    }
};

// 使用示例
SegmentTree<Max> st(n);
st.modify(i, {val});  // 修改单点值
auto max_val = st.rangeQuery(l, r).val;  // 查询区间最大值

8. 注意事项

  1. Info 类型必须定义 operator+ 运算符
  2. 查询区间为左闭右开 [l, r)
  3. 修改操作会自动维护祖先节点信息
  4. 初始化时需要合理估计空间大小

9. 总结

线段树是一个强大而灵活的数据结构，通过合理的设计可以解决多种区间查询和修改问题。本模板通过模板编程的方式提供了高度的可定制性，同时保持了优秀的性能表现。