什么是线段树?

线段树

概述

线段树（Segment Tree）是一种二叉树数据结构，通常用于解决与区间或者段相关的问题。它主要用于处理一维区间的查询和更新操作，例如，查找区间内的最小值、最大值、和、平均值等。线段树是一种灵活而强大的数据结构，特别适用于需要频繁查询和更新区间信息的场景。

线段树的基本思想是将一个区间划分成多个子区间，每个节点表示一个子区间的信息，然后递归地构建这个二叉树。通常情况下，线段树是一颗平衡二叉树，每个叶子节点表示数组中的一个元素，而每个非叶子节点表示对应区间的一些信息，如最小值、最大值、和等。

基本的线段树节点结构如下：

struct SegmentTreeNode {
    int start, end;
    int data; // 存储区间信息，可以是最小值、最大值、和等
    SegmentTreeNode* left;
    SegmentTreeNode* right;
    
    SegmentTreeNode(int s, int e, int d) : start(s), end(e), data(d), left(nullptr), right(nullptr) {}
};

1
2
3
4
5
6
7
8
9

线段树的构建过程是递归的，每个节点的区间范围由其左右子节点的区间合并而来。线段树的查询和更新操作也是递归的，通过递归地访问树的节点，以实现对区间信息的查询和更新。

线段树常见的应用包括范围查询、区间更新、区间最值等问题。由于其高效的查询和更新性能，线段树在解决一维区间问题上被广泛应用。

代码示例

一个典型的应用线段树的问题是区间查询。假设有一个长度为 n 的数组，初始时所有元素都是0。支持两种操作：

1. 更新操作（Update）： 将数组中的某个元素加上一个特定的值。
2. 查询操作（Query）： 查询数组中某个区间的元素和。

使用线段树可以高效地实现这个问题。以下是一个简单的例子：

#include 
#include 

using namespace std;

// 线段树节点结构
struct SegmentTreeNode {
    int start, end;
    int sum; // 存储区间元素和
    SegmentTreeNode* left;
    SegmentTreeNode* right;
    
    SegmentTreeNode(int s, int e) : start(s), end(e), sum(0), left(nullptr), right(nullptr) {}
};

// 构建线段树
SegmentTreeNode* buildSegmentTree(vector& nums, int start, int end) {
    if (start > end) return nullptr;

    SegmentTreeNode* root = new SegmentTreeNode(start, end);

    if (start == end) {
        root->sum = nums[start];
    } else {
        int mid = start + (end - start) / 2;
        root->left = buildSegmentTree(nums, start, mid);
        root->right = buildSegmentTree(nums, mid + 1, end);
        root->sum = root->left->sum + root->right->sum;
    }

    return root;
}

// 区间查询
int query(SegmentTreeNode* root, int qStart, int qEnd) {
    if (!root || qStart > root->end || qEnd < root->start) return 0; // 无交集
    if (qStart <= root->start && qEnd >= root->end) return root->sum; // 完全包含

    int mid = root->start + (root->end - root->start) / 2;
    return query(root->left, qStart, min(qEnd, mid)) + query(root->right, max(qStart, mid + 1), qEnd);
}

// 单点更新
void update(SegmentTreeNode* root, int index, int value) {
    if (!root || index < root->start || index > root->end) return; // 无交集
    if (root->start == root->end) {
        root->sum += value;
        return;
    }

    int mid = root->start + (root->end - root->start) / 2;
    if (index <= mid) {
        update(root->left, index, value);
    } else {
        update(root->right, index, value);
    }

    root->sum = root->left->sum + root->right->sum;
}

int main() {
    vector nums = {1, 3, 5, 7, 9, 11};

    // 构建线段树
    SegmentTreeNode* root = buildSegmentTree(nums, 0, nums.size() - 1);

    // 查询区间[1, 4]的和
    cout << "Sum in range [1, 4]: " << query(root, 1, 4) << endl;

    // 更新元素，将索引为2的元素加上3
    update(root, 2, 3);

    // 查询更新后的区间[1, 4]的和
    cout << "Updated sum in range [1, 4]: " << query(root, 1, 4) << endl;

    return 0;
}
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
65
66
67
68
69
70
71
72
73
74
75
76
77

在这个例子中，我们使用线段树实现了区间查询和单点更新。 buildSegmentTree 函数用于构建线段树， query 函数用于查询区间和， update 函数用于单点更新。这是线段树的一个简单用例，但线段树的应用远不止于此，可以处理更复杂的问题。

leetcode例题参考 307. 区域和检索 - 数组可修改